BreadthFirstScan for implicit Graph

Question

Many algorithms on graphs require only local knowledge at each step, e.g. for BFS at any point we only need to know the AdjacencyList of the vertex we are currently looking at. BFS is implemented in Mathematica in BreadthFirstScan, but I see no way to use it on an implicit graph, i.e. not a Graph object, but an object for which we can compute edges on-demand for any particular node.

More generally, is there any way to work with implicitly defined graphs in Mathematica? I've tried to trick it into accepting a "graph association", specifying the number of vertices and the function to use to compute neighbors of a vertex:

Unprotect@GraphQ;
GraphQ[Graph[a_Association]] := With[{}, Print@"call: GraphQ"; With[{}, Print@"call: GraphQ"; KeyExistsQ[a, "n"] && KeyExistsQ[a, "adj"]];
Protect@GraphQ;

Unprotect@VertexList;
VertexList[Graph[a_Association]] := With[{}, Print@"call: VertexList"; Range@a@"n"];
Protect@VertexList;

Unprotect@EdgeList;
EdgeList[Graph[a_Association]] := With[{}, Print@"call: EdgeList"; Flatten@Table[v \[DirectedEdge] # & /@ a["adj"]@v, {v, a@"n"}]];
Protect@EdgeList;

Unprotect@VertexCount;
VertexCount[Graph[a_Association]] := With[{}, Print@"call: VertexCount"; a@"n"];
Protect@VertexCount;

Unprotect@AdjacencyList;
AdjacencyList[Graph[a_Association], v_] := With[{}, Print@"call: AdjacencyList"; a["adj"]@v];
Protect@AdjacencyList;

Then, for example, the following would be an equivalent definition for CycleGraph@3:

cycle3 = Graph[<|"n" -> 3, "adj" -> ({Mod[# + 1, 3, 1], Mod[# - 1, 3, 1]} &)|>];

However, I haven't got this graph to work for any built-in function: the furthest I've got is seeing NeighborhoodGraph perform some calls to GraphQ, VertexList and EdgeList (why would it do this?), but most functions just somehow detect this is not a native Graph object... any ideas how to circumvent this?

PS: My use case involves a huge (~10^12 vertex) graph which I know has small connected components, which I'd like to explore.

Answer 1

I expect that what you are asking for is not possible. The graph functions very likely use internal functions instead of the public API. In fact, I expect many algorithms to be implemented in a low-level language like C or C++. Overriding the public API won't help.

As a workaround, you could implement BFS yourself.

bfs[neifun_, v0_] :=
 Module[{dist = <||>, q = CreateDataStructure["Queue"], v, d, neis},
  q["Push", v0];
  AssociateTo[dist, v0 -> 0];
  While[! q["EmptyQ"],
   v = q["Pop"];
   d = dist[v] + 1;
   neis = Select[neifun[v], Not@KeyMemberQ[dist, #] &];
   q["Push", #] & /@ neis;
   AssociateTo[dist, Thread[neis -> d]]
   ];
  dist
  ]

Here v0 is the starting vertex and neifun is a function that returns the neighbours of a vertex. The output is an association from reached vertices to their distance from v0.

Example:

SeedRandom[555];
g = RandomGraph[{10, 10}, GraphStyle -> "DiagramGold"]

bfs[AdjacencyList[g, #] &, 1]
(* <|1 -> 0, 9 -> 1, 10 -> 1, 3 -> 2, 2 -> 2, 8 -> 2, 6 -> 3, 7 -> 3|> *)

Answer 2

Breadth first search

Well, BFS can be implemented using a queue which in turn is easy to implement with Association. First, let's emulate a query function neigbors:

G = RandomGraph[{100, 200}];
adj = AdjacencyMatrix[G]["AdjacencyLists"];
neigbors[vertex_] := adj[[vertex]];

Not let's implement the queue:

iter = 0;
counter = 0;
visited = <||>;
queue = <||>;
push[vertex_] := AssociateTo[queue, ++counter -> vertex];
pop[] := If[Length[queue] > 0,
   Module[{key, return},
    key = Keys[queue][[1]];
    return = queue[key];
    KeyDropFrom[queue, key];
    return
    ],
   $Failed
   ];

Let's do the breadth first search starting at vertex 1:

vertex = 1;
While[vertex =!= $Failed,
  iter++;
  AssociateTo[visited, vertex -> iter];
  c = neigbors[vertex];
  unvisited = ReverseSort[Pick[c, Lookup[visited, c, -1], -1]];
  Scan[push, unvisited];
  
  vertex = pop[];
  ];

For example, this provides you with the vertices of the connected component of the start vertex in depth-first order:

 ordering = Keys[Sort[visited]]

Depth first search

Analogously, one can implement DFS by using a stack. The difference between a stack and a queue is just the end from which elements are popped. So just changing pop to the following should do:

pop[] := If[Length[queue] > 0,
   Module[{key, return},
    key = Keys[queue][[-1]];
    return = queue[key];
    KeyDropFrom[queue, key];
    return
    ],
   $Failed
   ];