4
$\begingroup$

In a graph $G$, for some $k$, I am looking to get a 0-1 matrix whose $ij^{\text{th}}$ entry is 1 whenever vertex $i$ has a path of length $k$ to vertex $j$ in $G$, and is otherwise zero.

I have been doing this with FindPath[graph,i,j,{k}], and entering all vertex pairs $ij$, then using Length to obtain a zero or one. But this takes a long time in large graphs, particularly when $k$ is large.

Considering a 1d random geometric graph, define the functions for building the graph:

edges6 = Function[{subsets, b}, 
   Pick[subsets, 
    UnitStep[
     RandomReal[{0, 1}, Length@subsets] - 
      Exp[-b (subsets[[All, 1]] - subsets[[All, 2]])^2]], 0]];
gr6[vert_, r0_] := 
  Graph[vert, UndirectedEdge @@@ edges6[Subsets[vert, {2}], 1/r0^2]];
makegraph2[nv_, coord_, width_, height_, r0_] := 
  Module[{pts, newvertices, newedges, edges, alledges, allpts, e1, e2,
     ew}, allpts = 
    Table[RandomReal[{-width/2, width/2}], {i, 1, nv}];
   allpts = Join[allpts, coord];
   (****Add edge weights****)
   pdg1 = gr6[allpts, r0]
   ];

and then run

gr = makegraph2[100, {0}, 10, 0.01, 0.5];
Length[FindPath[gr, #, Last@VertexList[gr], {6}]] & /@ VertexList[gr] // AbsoluteTiming

which gives

{0.657717, {1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}}

which is a list of 0's and 1's which determines the existence of a six-hop path from each node, to the node at $0$. I can try and speed it up with IGDistanceCounts, but this only gives shortest paths. Is there way to do it quicker than with FindPath?

$\endgroup$
4
$\begingroup$

Why not work with AdjacencyMatrix instead? For example:

KPaths[g_, k_] := Module[{a, m},
    a = AdjacencyMatrix[g];
    m = 1 - IdentityMatrix[Length[a]];
    Nest[Unitize[(a . #) m]&, a, k-1]
]       

Comparison:

SeedRandom[1];
gr=makegraph2[100,{0},10,0.01,0.5];
last = Length[FindPath[gr,#,Last@VertexList[gr],{6}]]&/@VertexList[gr]; //AbsoluteTiming
last

{0.104942, Null}

{0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1,
0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0,
1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0}

r = KPaths[gr, 6]; //AbsoluteTiming
r[[-1]] //Normal

last == r[[-1]]

{0.002574, Null}

{0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1,
0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0,
1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0}

True

Note that KPaths does all of the vertices instead of just the last vertex.

$\endgroup$
5
  • $\begingroup$ Ok very nice, thank you. How do you get round the idea that the powers of the adjacency matrix gives the walks of length k, rather than the paths? I always thought the powers can only count walks, which repeat edges and vertices. So it is possible for these two lists to differ, if have a walk of length 6, but no path of length 6, e.g. by traversing a path of length 4, then moving forward and pack along one edge. $\endgroup$ – apkg Jan 12 at 18:11
  • $\begingroup$ @apkg That's why I multiply by the matrix m, which is 1 - IdentityMatrix[Length[a]]. This basically zeros out the diagonal after every "power". $\endgroup$ – Carl Woll Jan 12 at 18:14
  • $\begingroup$ So that cancels out the walks? Leaving only the paths? $\endgroup$ – apkg Jan 12 at 18:14
  • $\begingroup$ @apkg Yes, I think so. $\endgroup$ – Carl Woll Jan 12 at 18:16
  • $\begingroup$ Why does the diagonal matter? I assume it is to stop the path, at any stage, running between itself and itself? Then this has the effect on the powers of A of not counting paths which repeat a vertex. $\endgroup$ – apkg Jan 12 at 18:19
2
$\begingroup$

A method using SparseArray`SparseArrayRemoveDiagonal to remove the diagonal:

ClearAll[urd, kPaths1, kPaths2]

urd = Unitize @* SparseArray`SparseArrayRemoveDiagonal;

kPaths1[g_, k_] := Module[{a = AdjacencyMatrix @ g}, Nest[urd[a.#] &, a, k - 1]]

Example:

SeedRandom[1];

gr = makegraph2[100, {0}, 10, 0.01, 0.5];

r1 = kPaths1[gr, 6]; // RepeatedTiming // First
0.00078

In comparison, Carl's KPaths we get

r = KPaths[gr, 6]; // RepeatedTiming // First
0.0017

All three methods give the same result:

r == r1
True
$\endgroup$
4
  • $\begingroup$ They don't always give the same result, try SeedRandom[7]. I think the diagonal needs to be removed after each dot product. $\endgroup$ – Carl Woll Jan 12 at 20:31
  • $\begingroup$ Thank you @Carl. Looks like moving urd inside Nest and MatrixPower fixes the issue and does not have significant effect on timings. $\endgroup$ – kglr Jan 12 at 20:56
  • $\begingroup$ kPaths2 still gives an answer different from both kPaths1 and KPaths when using SeedRandom[7]. $\endgroup$ – Carl Woll Jan 12 at 23:04
  • $\begingroup$ Thank you again @Carl. Deleted kPaths2. $\endgroup$ – kglr Jan 12 at 23:27

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.