[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Question regarding graph.bfs

From: Tamás Nepusz
Subject: Re: [igraph] Question regarding graph.bfs
Date: Tue, 24 Jul 2012 21:52:16 +0200

> I have a question regarding the new graph.bfs function in igraph. I  
> want to find all paths between two vertices in a directed graph.  
> However, I’m not sure if I can really do this with the graph.bfs  
> function of igraph

No, you can't, because BFS will find the shortest paths only. Finding all the 
possible paths between two vertices is a completely different problem, and the 
first step is to decide what you mean by finding _all_ the possible paths, 
since once you have a cycle in the graph, any two vertices which can be 
connected by going through at least one vertex of the cycle will have 
infinitely many paths between them (since you can just traverse the cycle 
infinitely many times). It is likely that you need a more restrictive 
definition; e.g., finding all the paths between two vertices that do not go 
through the same edge (or the same vertex) twice.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]