[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.
Best,
T.