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

Posted 6 years ago
10500 Views
|
5 Replies
|
0 Total Likes
|
 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}] 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: Answer
5 Replies
Sort By:
Posted 6 years ago
 This uses your EdgeLabels and the list of paths from your example. Can use adapt this to get what you want? In:= 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= {{A, C}, {A, B, D}} Answer
Posted 6 years ago
 This is perfect what you have done. Got it. Thanks a ton. But is there not a way to list all paths displaying edges? Answer
Posted 6 years ago
 I have applied your technique to my notebook uploaded. But I am getting combinations of edges and vertices. Attachments: Answer
Posted 6 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. Answer
Posted 6 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) Answer