Быстрый способ найти всех соседей вершины в графе


Я ищу самый быстрый способ найти всех соседей вершины в неориентированном графе. Пожалуйста, улучшить код, если это возможно.

neighbours[g_Graph, v_] :=
 Module[
  {vl = VertexList[g],
   pos},
  pos = Position[vl, v][[1, 1]];
  Pick[VertexList[g], AdjacencyMatrix[g][[pos]], 1]
 ]

Мне это нужно для быстрой работы и для разреженных и плотных графиков.

  1. Важно, чтобы выполнение этого решения, которое он использует SparseArrayС.
  2. Это является узким местом в моем приложении. Поскольку мой график постоянно меняется, пытаясь заранее вычислить соседей или с помощью мемоизации будет значительно усложнять.

Я бы хотел подчеркнуть, что скорость имеет важное значение здесь. Вот график, чтобы проверить на:

max = 4000;
c = 0.3;

tg = RandomGraph[{max, Round[c max^2]}];

neighbours[tg, 1]; // Timing


1278
3
задан 8 июня 2011 в 09:06 Источник Поделиться
Комментарии