2
$\begingroup$

Consider the following C code:

m[3]=m[1]+m[2];
m[4]=m[1]*m[5];
m[6]=m[4]+m[1]+m[5];
m[7]=m[6]+m[5];

I've written some code to visualize how this code might be executed in parallel on an FPGA:

edges = {
    a[m1, m2] -> m3, 
    m1 -> a[m1, m2], 
    m2 -> a[m1, m2], 
    t[m1, m5] -> m4, 
    m1 -> t[m1, m5], 
    m5 -> t[m1, m5], 
    a[m1, m4, m5] -> m6, 
    m1 -> a[m1, m4, m5], 
    m4 -> a[m1, m4, m5], 
    m5 -> a[m1, m4, m5], 
    a[m5, m6, m3] -> m7, 
    m6 -> a[m5, m6, m3], 
    m5 -> a[m5, m6, m3], 
    m3 -> a[m5, m6, m3]
}

graph = Graph[edges, VertexLabels -> Automatic]

enter image description here

I would like to find the number of clock cycles to execute these steps in parallel. That is, I want to find the maximal graph distance between two vertices. In the picture, the bottleneck occurs from m5 (or m1) to m7. It takes 6 cycles to compute m7 because of the 6 execution steps along this long path.

What is the right way to find the longest path and its length?

I tried GraphDiameter[graph], but it was Infinity (maybe because it's directed?). A workaround might be to undirect my edges, but I thought I'd ask here first.

$\endgroup$
  • 3
    $\begingroup$ The diameter is the longest shortest path. It seems you want the longest possible path in an acyclic graph. Disregarding the fact that the graph is not strongly connected (which is why GraphDiameter gives Infinity), the longest shortest path is 5 here: from t[m1,m5] to m7. Getting from m1 to m7 is possible in only 4 steps (through m3). Thus you don't want the diameter. $\endgroup$ – Szabolcs Jan 18 '17 at 20:12
3
$\begingroup$

As Szabolcs pointed out, GraphDiameter isn't really what you are looking for. If the graph has no loops, then you can use the adjacency matrix to find the longest path in your graph.

step = 0;
m = AdjacencyMatrix[graph];
cur = m;
While[Total[Flatten[cur]] != 0, cur = cur.m; step = step + 1]
step
$\endgroup$
  • $\begingroup$ You can use Total[cur, 2] instead of Total[Flatten[cur]]. $\endgroup$ – Szabolcs Jan 18 '17 at 21:58
  • $\begingroup$ Thanks very much. For our viewers at home, if $m$ is the adjacency matrix, then $m^n_{i,j}$ is the number of $n$-length paths from vertex $i$ to vertex $j$. So exponentiating $m$ until it's all zeros is a way to find the smallest $n$ for which no $n$-length paths exist, and the longest path is one less than that. $\endgroup$ – ConvexMartian Jan 18 '17 at 22:47
0
$\begingroup$

Perhaps you could use FindPath. For example:

edges = {
    a[m1, m2] -> m3, 
    m1 -> a[m1, m2], 
    m2 -> a[m1, m2], 
    t[m1, m5] -> m4, 
    m1 -> t[m1, m5], 
    m5 -> t[m1, m5], 
    a[m1, m4, m5] -> m6, 
    m1 -> a[m1, m4, m5], 
    m4 -> a[m1, m4, m5], 
    m5 -> a[m1, m4, m5], 
    a[m5, m6, m3] -> m7, 
    m6 -> a[m5, m6, m3], 
    m5 -> a[m5, m6, m3], 
    m3 -> a[m5, m6, m3]
};

Max @* Map[Length] @ FindPath[edges, m1, m7, Length@edges, All]
Max @* Map[Length] @ FindPath[edges, m2, m7, Length@edges, All]
Max @* Map[Length] @ FindPath[edges, m5, m7, Length@edges, All]

7

5

7

$\endgroup$

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.