1
$\begingroup$

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?

enter image description here

$\endgroup$
2
$\begingroup$
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]]]

enter image description here

$\endgroup$
  • $\begingroup$ It is an excellent solution (though my programming knowledge is not sufficient to fully digest it). Thank you very much. $\endgroup$ – Tugrul Temel Oct 6 '18 at 14:38
  • $\begingroup$ @Tebernus, my pleasure. Thank you for the accept. $\endgroup$ – kglr Oct 6 '18 at 14:38
  • $\begingroup$ 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. $\endgroup$ – Tugrul Temel Oct 6 '18 at 14:50
  • $\begingroup$ 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. $\endgroup$ – Tugrul Temel Oct 6 '18 at 17:28
  • $\begingroup$ @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 $\endgroup$ – kglr Oct 6 '18 at 18:55

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.