5
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ No, you can't trick it to accept something that's not really a Graph. I see how this would be useful, but I am pretty sure this is not possible. $\endgroup$
    – Szabolcs
    Mar 30 at 9:26
  • $\begingroup$ Would a custom BFS implementation help you? $\endgroup$
    – Szabolcs
    Mar 30 at 10:03
  • $\begingroup$ Indeed one certainly could write custom implementations of (at least some of) the standard algorithms, but I was looking for a quicker way to interface with them directly, for performance and correctness reasons as well as prototyping speed... it looks like Mathematica could use an ImplicitGraph function :-/ $\endgroup$ Mar 30 at 12:30
  • 1
    $\begingroup$ I think implementing something like that is a lot more effort than you might think. I would not hold my breath. You can take a look at the Boost Graph Library (C++) which is designed to work on arbitrary graph representations. $\endgroup$
    – Szabolcs
    Mar 30 at 13:02
6
$\begingroup$

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"]

enter image description here

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

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
   ];
$\endgroup$
2
  • $\begingroup$ I was a bit lazier and used the new built-in queue :-) $\endgroup$
    – Szabolcs
    Mar 30 at 10:21
  • $\begingroup$ Yeah, is saw that right after I submitted! XD $\endgroup$ Mar 30 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.