How do I get all possible paths in terms of edges, and not vertices?

Questions
, , , , , ,
1

Hi everyone,

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}]

Graph4.jpg
Graph4.jpg360×171 2.99 KB

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. Please help. Thank you.

2

This uses your EdgeLabels and the list of paths from your example. Can use adapt this to get what you want?

In[1]:= edgerule = {1 <-> 2 -> A, 2 <-> 3 -> B, 2 <-> 4 -> C, 3 <-> 4 -> D} /. UndirectedEdge -> List; 
Map[Partition[#, 2, 1] &, {{1, 2, 4}, {1, 2, 3, 4}}] /. edgerule

Out[1]= {{A, C}, {A, B, D}}
3

This is perfect what you have done. Got it. Thanks a ton. But is there not a way to list all paths displaying edges?

4

I have applied your technique to my notebook uploaded. But I am getting combinations of edges and vertices.

5

If you study the result you should notice that it is correctly translating verticies …,3,5,… but not translating verticies …,5,3,… Within the graph functions provided by Mathematica it understands your edges are undirected. But the simple pattern matching that I showed did not consider this. Try this on your paths

edgerule = {1 <-> 2 -> A, 2 <-> 3 -> B, 3 <-> 4 -> C, 4 <-> 5 -> D, 2 <-> 6 -> E, 4 <-> 6 -> F, 5 <-> 7 -> H, 6 <-> 7 -> I,
  2 <-> 8 -> J, 6 <-> 9 -> K, 7 <-> 10 -> L, 8 <-> 9 -> M, 8 <-> 11 -> N, 9 <-> 10 -> O, 9 <-> 12 -> P, 10 <-> 13 -> Q,
  11 <-> 12 -> R, 11 <-> 14 -> S, 11 <-> 15 -> T, 12 <-> 13 -> U, 13 <-> 14 -> V, 14 <-> 15 -> W} /. UndirectedEdge -> List;
edgerule = Flatten[edgerule /. Rule[List[h_, t_], l_] -> {Rule[List[h, t], l], Rule[List[t, h], l]}];

That expands your edgerule to include paths going in either direction between two verticies. Then

Map[Partition[#, 2, 1] &, ...yourvertexsolution...]/. edgerule

should give you the solution labeled as you desire.

Study the details of this method carefully until you can fully understand the ideas used. That will help you in the future.

6

Hi.

path = FindPath[g,1,4,Infinity,All]
{{1,2,4},{1,2,3,4}}

rules = PropertyValue[g,EdgeLabels]
{3<->4->D,2<->4->C,1<->2->A,2<->3->B}

EdgeList/@(PathGraph/@path) /.rules
{{A,C},{A,B,D}}

As a side note, notice that you are using variables with a Capital letter for the edge labels. Also notice that in both replies, the solution has the letter C & D in black. The other letters are in light blue. The black letters are built-in functions. If you had a larger graph, you would be using letters like N which is also a built in variable.
Did you mean to use Letters?
Just an idea with the thought of having a larger graph. You could use Subscript also…etc

g=Graph[{1<->2,2<->3,2<->4,3<->4}];

MyEdges = Thread[Rule[EdgeList[g], CharacterRange["A", "D"]]]

g = SetProperty[g, EdgeLabels -> MyEdges];

Just to be different:

Graph[g, VertexLabels -> Table[i -> Placed["Name", Center], {i, 4}], 
 VertexSize -> 0.1]

HTH
Dana
(Mathematica 10.2)