Message Boards Message Boards

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

Azhar Uddin Mohammed
Posted 10 years ago

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

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

Attachments:
POSTED BY: Azhar Uddin Mohammed
5 Replies
Sort By:
Dana DeLouis
Dana DeLouis
Posted 10 years ago

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)
POSTED BY: Dana DeLouis
Bill Simpson
Bill Simpson
Posted 10 years ago

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.
POSTED BY: Bill Simpson
Bill Simpson
Bill Simpson
Posted 10 years ago

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}}
POSTED BY: Bill Simpson

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

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

Attachments:
POSTED BY: Azhar Uddin Mohammed
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract