2
$\begingroup$

Suppose I have an undirected graph G = Graph[{1 <-> 2, 2 <-> 3, 2 <-> 3, 3 <-> 4}]

enter image description here

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

{{1, 2, 3, 4}}

But the expected result is

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

Is there any way to get all possible paths even though any number of edges are present in between two same vertices?


Link to Wolfram Community cross post.

$\endgroup$
  • 1
    $\begingroup$ I don't have v10, so I can't test. But the standard way to do such things in graph theory is by creating a dummy vertex on each multiedge (or if you don't want to take care of it, on each edge) to differentiate them $\endgroup$ – Dr. belisarius Oct 9 '15 at 4:30
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 0) Browse the common pitfalls question 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – Dr. belisarius Oct 9 '15 at 5:01
4
$\begingroup$

First, to get this out of the way: I would not consider this a bug. FindPath returns a sequence of vertices, not a sequence of edges, which indicates the definition of path that is meant here. {{1,2,3,4},{1,2,3,4}} are of course the very same sequence of vertices, regardless of any edges inbetween, thus there is no reason for FindPath to return them multiple times.


If needed, you can take the multiplicities of edges into account like this.

First convert to a list of edges:

FindPath[graph, 1, 4, Infinity, All]
path = First[%]
(* {1, 2, 3, 4} *)

edgeSequence = Sort /@ UndirectedEdge @@@ Partition[path, 2, 1]
(* {1 <-> 2, 2 <-> 3, 3 <-> 4} *)

edgeMultiplicities = Counts[Sort /@ EdgeList[graph]]
(* <|1 <-> 2 -> 1, 2 <-> 3 -> 2, 3 <-> 4 -> 1|> *)

edgeMultiplicities /@ edgeSequence
(* {1, 2, 1} *)

Times @@ %
(* 2 *)

The result is that this path should be taken into account twice.

The Sort was necessary to canonicalize directed edges, and make sure that 1<->2 and 2<->1 are treated as the same.

$\endgroup$
  • $\begingroup$ Actually it won't work for FindPath[graph, 4, 1, Infinity, All] because of edgeSequence which defines objects like 4<->3 instead of 3<->4. Also the graph could contain directed edges, so a more universal solution would be : edgeSequence = Partition[path, 2, 1] ; edgeMultiplicities = Counts[EdgeList[graph] /. {DirectedEdge -> List, UndirectedEdge[a_, b_] :> Sequence[{a, b}, {b, a}]}]. Then it will work even for cases like Graph[{1 <-> 2, 2 <-> 3, 2 -> 3, 3 <-> 4}] $\endgroup$ – SquareOne Oct 9 '15 at 9:26
  • 1
    $\begingroup$ @SquareOne Thank you, you are completely right. Corrected now. What's ridiculous about my mistake is that I posted this yesterday: chat.stackexchange.com/transcript/message/24581195#24581195 Actually I wonder why DirectedEdges isn't Orderless ... $\endgroup$ – Szabolcs Oct 9 '15 at 9:54
1
$\begingroup$

If the aim to count the paths of certain length [including traversing same vertices/edges multiple times: see comment Szabolcs] (and it may not be) you could use AdjacencyMatrix, e.g.

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

then

np[g_, i_, j_, n_] := MatrixPower[AdjacencyMatrix[g], n][[i, j]]

so np[g,1,4,3] yields 2, np[g,2,2,3] yields 0 (as would any odd number of steps) but np[g,2,2,4] yields 29.

$\endgroup$
  • $\begingroup$ It's good to mention the usual caveat that this method does not exclude passing through the same vertices (or edges) multiple times. $\endgroup$ – Szabolcs Oct 9 '15 at 8:04
  • $\begingroup$ @Szabolcs thank you...yes I should have been more precise in language. Will edit to be precise. $\endgroup$ – ubpdqn Oct 9 '15 at 8:06

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.