[BGL] simple problem: how to detect connections in a dag?
Hi @boost, we have a rather simple problem here for which we however couldn't find a simple solution in the BGL. Probably because we aren't graph experts. We have a dag and two vertices in this dag. Now we just want to know if these vertices are connected (acrtually we don't need the path), that is if one vertex is in a parent chain of the other. Thanks in advance Olaf Krzikalla
we have a rather simple problem here for which we however couldn't find a simple solution in the BGL. Probably because we aren't graph experts. We have a dag and two vertices in this dag. Now we just want to know if these vertices are connected (acrtually we don't need the path), that is if one vertex is in a parent chain of the other.
You could use a function called edge(u, v, g) with u, v being vertex descriptors and g a graph. In a directed graph if u has v as the opposite end of an out edge, then this function will return the pair (e, true) with e being an edge descriptor. If v is not at the end of an out edge, then the function returns (x, false) with x being an invalid edge descriptor. Performance varies depending on the type of g. For adjacency lists, the operation completes in O(deg(u)), for adjacency matrices it's O(1). Andrew Sutton andrew.n.sutton@gmail.com
On Tue, 5 Jan 2010, Andrew Sutton wrote:
we have a rather simple problem here for which we however couldn't find a simple solution in the BGL. Probably because we aren't graph experts. We have a dag and two vertices in this dag. Now we just want to know if these vertices are connected (acrtually we don't need the path), that is if one vertex is in a parent chain of the other.
You could use a function called edge(u, v, g) with u, v being vertex descriptors and g a graph. In a directed graph if u has v as the opposite end of an out edge, then this function will return the pair (e, true) with e being an edge descriptor. If v is not at the end of an out edge, then the function returns (x, false) with x being an invalid edge descriptor.
Performance varies depending on the type of g. For adjacency lists, the operation completes in O(deg(u)), for adjacency matrices it's O(1).
I think the question was asking for a path of arbitrary length; in that case, breadth_first_search or depth_first_search would find the path. You can either check the color map or predecessor map to determine if a particular vertex was reached from your particular source vertex. -- Jeremiah Willcock
Hi @boost, Jeremiah Willcock schrieb:
I think the question was asking for a path of arbitrary length; Indeed. Maybe there is a better term for the property "directly or indirectly connected", isn't there?
in that case, breadth_first_search or depth_first_search would find the path. The problem here is that we need to stop the search once we've found a connection. But neither BFS visitors nor DFS visitors seems to give us a chance to cancel the search. The discover_vertex visitor could have this ability (I slightly remember that I had the problem to cancel a search in BGL some years ago and I wasn't able to solve it by then too).
Tia Olaf Krzikalla
Olaf Krzikalla wrote:
Hi @boost,
Jeremiah Willcock schrieb:
I think the question was asking for a path of arbitrary length; Indeed. Maybe there is a better term for the property "directly or indirectly connected", isn't there?
in that case, breadth_first_search or depth_first_search would find the path. The problem here is that we need to stop the search once we've found a connection. But neither BFS visitors nor DFS visitors seems to give us a chance to cancel the search. The discover_vertex visitor could have this ability (I slightly remember that I had the problem to cancel a search in BGL some years ago and I wasn't able to solve it by then too).
You can throw from discover_vertex visitor. - Volodya
in that case, breadth_first_search or depth_first_search would find the path. The problem here is that we need to stop the search once we've found a connection. But neither BFS visitors nor DFS visitors seems to give us a chance to cancel the search. The discover_vertex visitor could have this ability (I slightly remember that I had the problem to cancel a search in BGL some years ago and I wasn't able to solve it by then too).
You can throw from discover_vertex visitor. Somehow I was afraid of that answer. Is an early stop such an exceptional use case that exceptions are the proper solution? Or should I consider this rather a limitation of BGL (rendering it useless for us as I will not introduce exceptions as part of the normal execution path). I wonder if this problem occurs so infrequent that
Hi, Vladimir Prus schrieb: there is no real built-in solution. Best regards Olaf Krzikalla
You can throw from discover_vertex visitor.
Somehow I was afraid of that answer. Is an early stop such an exceptional use case that exceptions are the proper solution? Or should I consider this rather a limitation of BGL (rendering it useless for us as I will not introduce exceptions as part of the normal execution path). I wonder if this problem occurs so infrequent that there is no real built-in solution
Like I said before you, can build a visitor that keeps a reference to the BFS's internal queue and flush it when you want to terminate the search. It's not as efficient as throwing an exception since clearing the queue is O(n), but it should still work. You'd probably want to flush the queue on finish_vertex so you guarantee that you won't pick up any new vertices in the next loop. You could also rewrite the search algorithm to include an explicit stopping point. The core BFS implementation is probably only 20 lines of fairly straightforward code. Andrew Sutton andrew.n.sutton@gmail.com
I think the question was asking for a path of arbitrary length;
Indeed. Maybe there is a better term for the property "directly or indirectly connected", isn't there?
Transitively connected? in that case, breadth_first_search or depth_first_search would find the
path.
The problem here is that we need to stop the search once we've found a
connection. But neither BFS visitors nor DFS visitors seems to give us a chance to cancel the search. The discover_vertex visitor could have this ability (I slightly remember that I had the problem to cancel a search in BGL some years ago and I wasn't able to solve it by then too)
The most promising (i.e., least invasive) solution to prematurely stopping an algorithm has been to simply throw and catch an exception. Another trick was to give your visitor a reference to the queue and color map and then empty the queue and color any other vertices black to make the algorithm think that it's done. Andrew Sutton andrew.n.sutton@gmail.com
On Wed, 6 Jan 2010, Olaf Krzikalla wrote:
Hi @boost,
Jeremiah Willcock schrieb:
I think the question was asking for a path of arbitrary length; Indeed. Maybe there is a better term for the property "directly or indirectly connected", isn't there?
I believe for a directed path the term is "reachable". -- Jeremiah Willcock
Hi Olaf,
Olaf Krzikalla
Hi @boost,
We have a dag and two vertices in this dag. Now we just want to know if these vertices are connected (acrtually we don't need the path),
Some solutions have already been suggested. But: If you want to check more then one pair of vertices, whether they are connected, you could compute the transitive closure of the graph an check for edges in it. Documentation of transitive_closure: http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/transitive_closure.html Yours sincerely, Eric
participants (5)
-
Andrew Sutton -
eric＠boese-wolf.eu -
Jeremiah Willcock -
Olaf Krzikalla -
Vladimir Prus