# Symbolic identification of all the pathways from vertex s to vertex t in a directed graph

Suppose that we have a symbolic digraph, meaning that, except the vertex names, edges in the digraph G are all String.

vlst = {1, 2, 3, 4};
elst = {{1, 3} -> a3, {1, 4} -> a4, {2, 1} -> b1, {2, 3} ->
b3, {3, 2} -> c2, {4, 2} -> d2};
mat = {{0, 0, a3, a4}, {b1, 0, b3, 0}, {0, c2, 0, 0}, {0, d2, 0, 0}};
G = Graph[{{1, 3}, {1, 4}, {2, 1}, {2, 3}, {3, 2}, {4, 2}},
EdgeWeight -> {a3, a4, b1, b3, c2, d2}, DirectedEdges -> True];


An example of my question: Find all the paths from, say, vertex 1 to 2 together with EdgeWeight associated with the binary links in the pathway concerned. See the digraph below for the answer: the pathway, {1->3->2}, is the only pathway from 1 to 2, and the associated set of edge weights is {a3,c2}. The answer is then: {{1->3->2},{a3,c2}}.

I want to find all the pathways in G from a vertex s to t and their associated edge weight sets using a very large symbolic digraph.

How can I achieve this?

ClearAll[ew]
ew = Module[{g = #, e = DirectedEdge @@@ Partition[#, 2, 1] & /@ FindPath[##, ∞, All]},
Transpose[{e, PropertyValue[{g, #}, EdgeWeight] & /@ # & /@ e}]] &;


Example:

G = Graph[{{1, 3}, {1, 4}, {2, 1}, {2, 3}, {3, 2}, {4, 2}},
EdgeWeight -> {a3, a4, b1, b3, c2, d2}, DirectedEdges -> True,
VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"];

ew[G, 1, 2]


{{{1 -> 4, 4 -> 2}, {a4, d2}}, {{1 -> 3, 3 -> 2}, {a3, c2}}}

HighlightGraph[G, ew[G, 1, 2][[All, 1]]]


• It is an excellent solution (though my programming knowledge is not sufficient to fully digest it). Thank you very much. Oct 6 '18 at 14:38
• @Tebernus, my pleasure. Thank you for the accept.
– kglr
Oct 6 '18 at 14:38
• You even found out my mistake in the question: {1->3->2} is not the only pathway as you indicated that {1->4->2} is another one. Next time I should be much more careful about the problem statement. Oct 6 '18 at 14:50
• Some of my questions in MSE have very good answers, and therefore, I use them in my research papers, as well as in the formulation of follow up questions. If I use, for example, your code above, should I specifically refer to you as the source of information or should I just use it since your code is public information in the site. Oct 6 '18 at 17:28
• @Teberius, if you scroll to the bottom of the page, in fine print, it says contributions licensed under cc by-sa 3.0 with attribution required. rev 2018.10.5.31856
– kglr
Oct 6 '18 at 18:55