2
$\begingroup$

Suppose I have an undirected graph

G = Graph[{1 <-> 2, 2 <-> 3, 2 <-> 4, 3 <-> 4}, 
     EdgeLabels -> {1 <-> 2 -> A, 2 <-> 3 -> B, 2 <-> 4 -> C, 3 <-> 4 -> D}]

enter image description here

I used FindPath[G, 1, 4, Infinity, All] and got the result as

{{1, 2, 4}, {1, 2, 3, 4}}

Although this result is true, I want this result to display possible paths in terms of edges, and not vertices. For above example, I want the result to be

{{A, C}, {A, B, D}}

Is there any way to do this? Actually, I have a large graph with 107 possible paths from source node to destination node, and I want to identify those paths with respect to edges.

Application as suggested in comment:

el = {1 <-> 2 -> a, 2 <-> 3 -> b, 3 <-> 4 -> c, 4 <-> 5 -> d, 
  2 <-> 6 -> e, 4 <-> 6 -> f, 5 <-> 7 -> g, 6 <-> 7 -> h, 
  2 <-> 8 -> i, 6 <-> 9 -> j, 7 <-> 10 -> k, 8 <-> 9 -> l, 
  8 <-> 11 -> m, 9 <-> 10 -> n, 9 <-> 12 -> o, 10 <-> 13 -> p, 
  11 <-> 12 -> q, 11 <-> 14 -> r, 11 <-> 15 -> s, 12 <-> 13 -> t, 
  13 <-> 14 -> u, 14 <-> 15 -> v}
UndirectedEdge @@@ Partition[#, 2, 1] & /@ {{1, 2, 8, 11, 15}, {1, 2, 
    8, 11, 14, 15}, {1, 2, 8, 9, 12, 11, 15}, {1, 2, 6, 9, 12, 11, 
    15}, {1, 2, 6, 9, 8, 11, 15}, {1, 2, 8, 11, 12, 13, 14, 15}, {1, 
    2, 8, 9, 12, 13, 14, 15}, {1, 2, 8, 9, 12, 11, 14, 15}, {1, 2, 8, 
    9, 10, 13, 14, 15}, {1, 2, 6, 9, 12, 13, 14, 15}, {1, 2, 6, 9, 12,
     11, 14, 15}, {1, 2, 6, 9, 10, 13, 14, 15}, {1, 2, 6, 9, 8, 11, 
    14, 15}, {1, 2, 6, 7, 10, 13, 14, 15}, {1, 2, 8, 9, 12, 13, 14, 
    11, 15}, {1, 2, 8, 9, 10, 13, 14, 11, 15}, {1, 2, 8, 9, 10, 13, 
    12, 11, 15}, {1, 2, 6, 9, 12, 13, 14, 11, 15}, {1, 2, 6, 9, 10, 
    13, 14, 11, 15}, {1, 2, 6, 9, 10, 13, 12, 11, 15}, {1, 2, 6, 7, 
    10, 13, 14, 11, 15}, {1, 2, 6, 7, 10, 13, 12, 11, 15}, {1, 2, 6, 
    7, 10, 9, 12, 11, 15}, {1, 2, 6, 7, 10, 9, 8, 11, 15}, {1, 2, 3, 
    4, 6, 9, 12, 11, 15}, {1, 2, 3, 4, 6, 9, 8, 11, 15}, {1, 2, 8, 11,
     12, 9, 10, 13, 14, 15}, {1, 2, 8, 9, 10, 13, 12, 11, 14, 15}, {1,
     2, 8, 9, 6, 7, 10, 13, 14, 15}, {1, 2, 6, 9, 10, 13, 12, 11, 14, 
    15}, {1, 2, 6, 9, 8, 11, 12, 13, 14, 15}, {1, 2, 6, 7, 10, 13, 12,
     11, 14, 15}, {1, 2, 6, 7, 10, 9, 12, 13, 14, 15}, {1, 2, 6, 7, 
    10, 9, 12, 11, 14, 15}, {1, 2, 6, 7, 10, 9, 8, 11, 14, 15}, {1, 2,
     6, 4, 5, 7, 10, 13, 14, 15}, {1, 2, 3, 4, 6, 9, 12, 13, 14, 
    15}, {1, 2, 3, 4, 6, 9, 12, 11, 14, 15}, {1, 2, 3, 4, 6, 9, 10, 
    13, 14, 15}, {1, 2, 3, 4, 6, 9, 8, 11, 14, 15}, {1, 2, 3, 4, 6, 7,
     10, 13, 14, 15}, {1, 2, 3, 4, 5, 7, 10, 13, 14, 15}, {1, 2, 8, 9,
     6, 7, 10, 13, 14, 11, 15}, {1, 2, 8, 9, 6, 7, 10, 13, 12, 11, 
    15}, {1, 2, 6, 7, 10, 13, 12, 9, 8, 11, 15}, {1, 2, 6, 7, 10, 9, 
    12, 13, 14, 11, 15}, {1, 2, 6, 4, 5, 7, 10, 13, 14, 11, 15}, {1, 
    2, 6, 4, 5, 7, 10, 13, 12, 11, 15}, {1, 2, 6, 4, 5, 7, 10, 9, 12, 
    11, 15}, {1, 2, 6, 4, 5, 7, 10, 9, 8, 11, 15}, {1, 2, 3, 4, 6, 9, 
    12, 13, 14, 11, 15}, {1, 2, 3, 4, 6, 9, 10, 13, 14, 11, 15}, {1, 
    2, 3, 4, 6, 9, 10, 13, 12, 11, 15}, {1, 2, 3, 4, 6, 7, 10, 13, 14,
     11, 15}, {1, 2, 3, 4, 6, 7, 10, 13, 12, 11, 15}, {1, 2, 3, 4, 6, 
    7, 10, 9, 12, 11, 15}, {1, 2, 3, 4, 6, 7, 10, 9, 8, 11, 15}, {1, 
    2, 3, 4, 5, 7, 10, 13, 14, 11, 15}, {1, 2, 3, 4, 5, 7, 10, 13, 12,
     11, 15}, {1, 2, 3, 4, 5, 7, 10, 9, 12, 11, 15}, {1, 2, 3, 4, 5, 
    7, 10, 9, 8, 11, 15}, {1, 2, 3, 4, 5, 7, 6, 9, 12, 11, 15}, {1, 2,
     3, 4, 5, 7, 6, 9, 8, 11, 15}, {1, 2, 8, 11, 12, 9, 6, 7, 10, 13, 
    14, 15}, {1, 2, 8, 9, 6, 7, 10, 13, 12, 11, 14, 15}, {1, 2, 8, 9, 
    6, 4, 5, 7, 10, 13, 14, 15}, {1, 2, 6, 7, 10, 13, 12, 9, 8, 11, 
    14, 15}, {1, 2, 6, 7, 10, 9, 8, 11, 12, 13, 14, 15}, {1, 2, 6, 4, 
    5, 7, 10, 13, 12, 11, 14, 15}, {1, 2, 6, 4, 5, 7, 10, 9, 12, 13, 
    14, 15}, {1, 2, 6, 4, 5, 7, 10, 9, 12, 11, 14, 15}, {1, 2, 6, 4, 
    5, 7, 10, 9, 8, 11, 14, 15}, {1, 2, 3, 4, 6, 9, 10, 13, 12, 11, 
    14, 15}, {1, 2, 3, 4, 6, 9, 8, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 
    6, 7, 10, 13, 12, 11, 14, 15}, {1, 2, 3, 4, 6, 7, 10, 9, 12, 13, 
    14, 15}, {1, 2, 3, 4, 6, 7, 10, 9, 12, 11, 14, 15}, {1, 2, 3, 4, 
    6, 7, 10, 9, 8, 11, 14, 15}, {1, 2, 3, 4, 5, 7, 10, 13, 12, 11, 
    14, 15}, {1, 2, 3, 4, 5, 7, 10, 9, 12, 13, 14, 15}, {1, 2, 3, 4, 
    5, 7, 10, 9, 12, 11, 14, 15}, {1, 2, 3, 4, 5, 7, 10, 9, 8, 11, 14,
     15}, {1, 2, 3, 4, 5, 7, 6, 9, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 7,
     6, 9, 12, 11, 14, 15}, {1, 2, 3, 4, 5, 7, 6, 9, 10, 13, 14, 
    15}, {1, 2, 3, 4, 5, 7, 6, 9, 8, 11, 14, 15}, {1, 2, 8, 9, 6, 4, 
    5, 7, 10, 13, 14, 11, 15}, {1, 2, 8, 9, 6, 4, 5, 7, 10, 13, 12, 
    11, 15}, {1, 2, 6, 4, 5, 7, 10, 13, 12, 9, 8, 11, 15}, {1, 2, 6, 
    4, 5, 7, 10, 9, 12, 13, 14, 11, 15}, {1, 2, 3, 4, 6, 7, 10, 13, 
    12, 9, 8, 11, 15}, {1, 2, 3, 4, 6, 7, 10, 9, 12, 13, 14, 11, 
    15}, {1, 2, 3, 4, 5, 7, 10, 13, 12, 9, 8, 11, 15}, {1, 2, 3, 4, 5,
     7, 10, 9, 12, 13, 14, 11, 15}, {1, 2, 3, 4, 5, 7, 6, 9, 12, 13, 
    14, 11, 15}, {1, 2, 3, 4, 5, 7, 6, 9, 10, 13, 14, 11, 15}, {1, 2, 
    3, 4, 5, 7, 6, 9, 10, 13, 12, 11, 15}, {1, 2, 8, 11, 12, 9, 6, 4, 
    5, 7, 10, 13, 14, 15}, {1, 2, 8, 9, 6, 4, 5, 7, 10, 13, 12, 11, 
    14, 15}, {1, 2, 6, 4, 5, 7, 10, 13, 12, 9, 8, 11, 14, 15}, {1, 2, 
    6, 4, 5, 7, 10, 9, 8, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 6, 7, 10, 
    13, 12, 9, 8, 11, 14, 15}, {1, 2, 3, 4, 6, 7, 10, 9, 8, 11, 12, 
    13, 14, 15}, {1, 2, 3, 4, 5, 7, 10, 13, 12, 9, 8, 11, 14, 15}, {1,
     2, 3, 4, 5, 7, 10, 9, 8, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 7, 
    6, 9, 10, 13, 12, 11, 14, 15}, {1, 2, 3, 4, 5, 7, 6, 9, 8, 11, 12,
     13, 14, 15}} /. el

For the above code, I got the result

{{a, i, m, s}, {a, i, m, r, v}, {a, i, l, o, 12 <-> 11, s}, {a, e, j, 
  o, 12 <-> 11, s}, {a, e, j, 9 <-> 8, m, s}, {a, i, m, q, t, u, 
  v}, {a, i, l, o, t, u, v}, {a, i, l, o, 12 <-> 11, r, v}, {a, i, l, 
  n, p, u, v}, {a, e, j, o, t, u, v}, {a, e, j, o, 12 <-> 11, r, 
  v}, {a, e, j, n, p, u, v}, {a, e, j, 9 <-> 8, m, r, v}, {a, e, h, k,
   p, u, v}, {a, i, l, o, t, u, 14 <-> 11, s}, {a, i, l, n, p, u, 
  14 <-> 11, s}, {a, i, l, n, p, 13 <-> 12, 12 <-> 11, s}, {a, e, j, 
  o, t, u, 14 <-> 11, s}, {a, e, j, n, p, u, 14 <-> 11, s}, {a, e, j, 
  n, p, 13 <-> 12, 12 <-> 11, s}, {a, e, h, k, p, u, 14 <-> 11, 
  s}, {a, e, h, k, p, 13 <-> 12, 12 <-> 11, s}, {a, e, h, k, 10 <-> 9,
   o, 12 <-> 11, s}, {a, e, h, k, 10 <-> 9, 9 <-> 8, m, s}, {a, b, c, 
  f, j, o, 12 <-> 11, s}, {a, b, c, f, j, 9 <-> 8, m, s}, {a, i, m, q,
   12 <-> 9, n, p, u, v}, {a, i, l, n, p, 13 <-> 12, 12 <-> 11, r, 
  v}, {a, i, l, 9 <-> 6, h, k, p, u, v}, {a, e, j, n, p, 13 <-> 12, 
  12 <-> 11, r, v}, {a, e, j, 9 <-> 8, m, q, t, u, v}, {a, e, h, k, p,
   13 <-> 12, 12 <-> 11, r, v}, {a, e, h, k, 10 <-> 9, o, t, u, 
  v}, {a, e, h, k, 10 <-> 9, o, 12 <-> 11, r, v}, {a, e, h, k, 
  10 <-> 9, 9 <-> 8, m, r, v}, {a, e, 6 <-> 4, d, g, k, p, u, v}, {a, 
  b, c, f, j, o, t, u, v}, {a, b, c, f, j, o, 12 <-> 11, r, v}, {a, b,
   c, f, j, n, p, u, v}, {a, b, c, f, j, 9 <-> 8, m, r, v}, {a, b, c, 
  f, h, k, p, u, v}, {a, b, c, d, g, k, p, u, v}, {a, i, l, 9 <-> 6, 
  h, k, p, u, 14 <-> 11, s}, {a, i, l, 9 <-> 6, h, k, p, 13 <-> 12, 
  12 <-> 11, s}, {a, e, h, k, p, 13 <-> 12, 12 <-> 9, 9 <-> 8, m, 
  s}, {a, e, h, k, 10 <-> 9, o, t, u, 14 <-> 11, s}, {a, e, 6 <-> 4, 
  d, g, k, p, u, 14 <-> 11, s}, {a, e, 6 <-> 4, d, g, k, p, 13 <-> 12,
   12 <-> 11, s}, {a, e, 6 <-> 4, d, g, k, 10 <-> 9, o, 12 <-> 11, 
  s}, {a, e, 6 <-> 4, d, g, k, 10 <-> 9, 9 <-> 8, m, s}, {a, b, c, f, 
  j, o, t, u, 14 <-> 11, s}, {a, b, c, f, j, n, p, u, 14 <-> 11, 
  s}, {a, b, c, f, j, n, p, 13 <-> 12, 12 <-> 11, s}, {a, b, c, f, h, 
  k, p, u, 14 <-> 11, s}, {a, b, c, f, h, k, p, 13 <-> 12, 12 <-> 11, 
  s}, {a, b, c, f, h, k, 10 <-> 9, o, 12 <-> 11, s}, {a, b, c, f, h, 
  k, 10 <-> 9, 9 <-> 8, m, s}, {a, b, c, d, g, k, p, u, 14 <-> 11, 
  s}, {a, b, c, d, g, k, p, 13 <-> 12, 12 <-> 11, s}, {a, b, c, d, g, 
  k, 10 <-> 9, o, 12 <-> 11, s}, {a, b, c, d, g, k, 10 <-> 9, 9 <-> 8,
   m, s}, {a, b, c, d, g, 7 <-> 6, j, o, 12 <-> 11, s}, {a, b, c, d, 
  g, 7 <-> 6, j, 9 <-> 8, m, s}, {a, i, m, q, 12 <-> 9, 9 <-> 6, h, k,
   p, u, v}, {a, i, l, 9 <-> 6, h, k, p, 13 <-> 12, 12 <-> 11, r, 
  v}, {a, i, l, 9 <-> 6, 6 <-> 4, d, g, k, p, u, v}, {a, e, h, k, p, 
  13 <-> 12, 12 <-> 9, 9 <-> 8, m, r, v}, {a, e, h, k, 10 <-> 9, 
  9 <-> 8, m, q, t, u, v}, {a, e, 6 <-> 4, d, g, k, p, 13 <-> 12, 
  12 <-> 11, r, v}, {a, e, 6 <-> 4, d, g, k, 10 <-> 9, o, t, u, 
  v}, {a, e, 6 <-> 4, d, g, k, 10 <-> 9, o, 12 <-> 11, r, v}, {a, e, 
  6 <-> 4, d, g, k, 10 <-> 9, 9 <-> 8, m, r, v}, {a, b, c, f, j, n, p,
   13 <-> 12, 12 <-> 11, r, v}, {a, b, c, f, j, 9 <-> 8, m, q, t, u, 
  v}, {a, b, c, f, h, k, p, 13 <-> 12, 12 <-> 11, r, v}, {a, b, c, f, 
  h, k, 10 <-> 9, o, t, u, v}, {a, b, c, f, h, k, 10 <-> 9, o, 
  12 <-> 11, r, v}, {a, b, c, f, h, k, 10 <-> 9, 9 <-> 8, m, r, 
  v}, {a, b, c, d, g, k, p, 13 <-> 12, 12 <-> 11, r, v}, {a, b, c, d, 
  g, k, 10 <-> 9, o, t, u, v}, {a, b, c, d, g, k, 10 <-> 9, o, 
  12 <-> 11, r, v}, {a, b, c, d, g, k, 10 <-> 9, 9 <-> 8, m, r, 
  v}, {a, b, c, d, g, 7 <-> 6, j, o, t, u, v}, {a, b, c, d, g, 
  7 <-> 6, j, o, 12 <-> 11, r, v}, {a, b, c, d, g, 7 <-> 6, j, n, p, 
  u, v}, {a, b, c, d, g, 7 <-> 6, j, 9 <-> 8, m, r, v}, {a, i, l, 
  9 <-> 6, 6 <-> 4, d, g, k, p, u, 14 <-> 11, s}, {a, i, l, 9 <-> 6, 
  6 <-> 4, d, g, k, p, 13 <-> 12, 12 <-> 11, s}, {a, e, 6 <-> 4, d, g,
   k, p, 13 <-> 12, 12 <-> 9, 9 <-> 8, m, s}, {a, e, 6 <-> 4, d, g, k,
   10 <-> 9, o, t, u, 14 <-> 11, s}, {a, b, c, f, h, k, p, 13 <-> 12, 
  12 <-> 9, 9 <-> 8, m, s}, {a, b, c, f, h, k, 10 <-> 9, o, t, u, 
  14 <-> 11, s}, {a, b, c, d, g, k, p, 13 <-> 12, 12 <-> 9, 9 <-> 8, 
  m, s}, {a, b, c, d, g, k, 10 <-> 9, o, t, u, 14 <-> 11, s}, {a, b, 
  c, d, g, 7 <-> 6, j, o, t, u, 14 <-> 11, s}, {a, b, c, d, g, 
  7 <-> 6, j, n, p, u, 14 <-> 11, s}, {a, b, c, d, g, 7 <-> 6, j, n, 
  p, 13 <-> 12, 12 <-> 11, s}, {a, i, m, q, 12 <-> 9, 9 <-> 6, 
  6 <-> 4, d, g, k, p, u, v}, {a, i, l, 9 <-> 6, 6 <-> 4, d, g, k, p, 
  13 <-> 12, 12 <-> 11, r, v}, {a, e, 6 <-> 4, d, g, k, p, 13 <-> 12, 
  12 <-> 9, 9 <-> 8, m, r, v}, {a, e, 6 <-> 4, d, g, k, 10 <-> 9, 
  9 <-> 8, m, q, t, u, v}, {a, b, c, f, h, k, p, 13 <-> 12, 12 <-> 9, 
  9 <-> 8, m, r, v}, {a, b, c, f, h, k, 10 <-> 9, 9 <-> 8, m, q, t, u,
   v}, {a, b, c, d, g, k, p, 13 <-> 12, 12 <-> 9, 9 <-> 8, m, r, 
  v}, {a, b, c, d, g, k, 10 <-> 9, 9 <-> 8, m, q, t, u, v}, {a, b, c, 
  d, g, 7 <-> 6, j, n, p, 13 <-> 12, 12 <-> 11, r, v}, {a, b, c, d, g,
   7 <-> 6, j, 9 <-> 8, m, q, t, u, v}}
$\endgroup$
  • 1
    $\begingroup$ Put the edge labels specification in a symbol, e.g. el. Then, UndirectedEdge @@@ Partition[#, 2, 1] & /@ vl/. el where vl is the list of vertices lists. BTW - avoid using uppercase initials for your symbols, might clash with a built-in. $\endgroup$ – ciao Sep 28 '15 at 4:43
  • $\begingroup$ @ciao.. I applied the code as you said. But I am getting combination of vertices and edges as paths. Where am I going wrong? $\endgroup$ – Azhar Sep 28 '15 at 5:27
  • 1
    $\begingroup$ I don't know - works for me. Might you post a (short) example of input where it fails? $\endgroup$ – ciao Sep 28 '15 at 5:56
  • 1
    $\begingroup$ Change the el in the statement to Join[el, MapAt[Reverse, el, {All, 1}]]... give that a whirl (it was missing edges where vertex order is reversed). $\endgroup$ – ciao Sep 28 '15 at 7:37
  • 1
    $\begingroup$ Note that edges are represented as vertex pairs in Mathematica. Are you sure that you want the edge labels (which are only for display) and not the actual edges? Edge labels are good for display, but you will not be able to use them for any programming/data-processing task with Mathematica graph. $\endgroup$ – Szabolcs Sep 28 '15 at 10:59

Your Answer

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

Browse other questions tagged or ask your own question.