Каков наилучший способ получения ближайших соседей на графике? - PullRequest
Новая
       39

Каков наилучший способ получения ближайших соседей на графике?

4 голосов
/ 12 июля 2011

Мне нужно вычислить что-то, значение которого задается следующим неэффективным псевдопифоническим кодом: 

def foo(a,b):
   tmp = 0
   for i in graph.nodes():
       for j in graph.nodes():
          tmp += c
          if (i and j are neighbors):
              tmp += a - c
          elif (i and j are next-neighbors):
              tmp += b - c
   return tmp

Другими словами, учитывая все пары узлов, foo = a * (E = количество ребер) + b * (EE = количество пар, которые не являются соседями, но имеют общего соседа) + c * (N (N-1) / 2 - EE - E).

Я пытался подумать о каком-то широком поиске, но не смог.

РЕДАКТИРОВАТЬ: больше информации

  • график не является статичным.Я постоянно добавляю и удаляю ребра, поэтому не могу рассчитать это только один раз.Я должен постоянно обновлять «список соседей».
  • Я храню график в виде матрицы смежности.

Ответы [ 3 ]

5 голосов
/ 13 июля 2011

Вот грубая идея. Но сначала несколько предположений: 1. неориентированный граф 2. постоянный счетчик вершин

Ваш график постоянно меняется. Поэтому необходимо эффективно обновлять количество соседей (ребер) и вторых соседей. Первый тривиален, поэтому давайте посмотрим на вторых соседей.

Согласно предложению @ Patrick, давайте поработаем с A^2 и посмотрим, как его можно эффективно обновить, не перезапуская каждый раз с нуля. A^2_ij - это число путей длины два от i до j, просто имейте в виду, что оно также будет иметь диагональные элементы, потому что всегда есть путь длиной два от вершины к себе. Если у вас есть A^2, вы можете легко подсчитать количество вторых соседей, поэтому давайте будем постоянно обновлять A^2 в памяти при изменении графика.

Как эффективно обновить A^2:

Когда вы добавляете / удаляете ребро, вы меняете A на матрицу B, в которой есть только две записи. Предположим, мы добавляем (а не удаляем) ребро. Тогда (A+B)^2 = A^2 + AB + BA + B^2.

Предположим, что добавленное ребро было (i,j).

  • B^2 тривиально: (B^2)_ii = (B^2)_jj = 1, остальное - 0.
  • AB = transpose(BA) поэтому нам нужно вычислить только один из двух, скажем BA. Получается, что строка i из BA является строкой j из A, а строка j из BA является строкой i из A, остальное равно нулю. Итак, снова, это быстро вычислить.

Удаление краев будет аналогичным.

Вам нужно только считать вторых соседей, поэтому вместо подсчета количества ненулевых недиагональных элементов, которые A^2 имеет на каждом шаге, с некоторой дополнительной работой вы можете посчитать, насколько количество ненулевых записей изменяется в A^2 при добавлении AB + BA.

EDIT

Все это объясняется на другом языке:

Давайте отследим количество путей длины два между любыми двумя вершинами в матрице M. Когда мы добавляем (удаляем) ребро между i и j, количество путей длины два будет увеличиваться (уменьшаться) на единицу между i и всеми соседями j, а также j и всеми Соседи i, поэтому M легко обновлять через O(n) раз после каждого изменения графика.

1 голос
/ 12 июля 2011

Если вы храните график в Матрице смежности A, вы можете найти все пути длины 2, умножив матрицу на себя (A^2), если это то, что вы спрашиваете.

Для предварительной обработки потребуется O (n ^ 3) времени, но затем вы можете выполнять поиск соседей и «соседей» в постоянное время.

0 голосов
/ 12 июля 2011

Получить список соседей вашего узла (node_main).Посетите каждого соседа.Добавьте каждого из своих соседей в список соседей , если не является одним из соседей узла_домена (или не является самим узлом_узла).Я что-то упустил?

...