BGL and reversing / moving edges
G'day, I was hoping someone might be able to tell me if they've run into any situations using BGL where they needed to move (or reverse (i.e. flip the source and target)) an edge within a graph implemented as an adjacency_list. I'm working on an implementation of an algorithm for max. weight bipartite matching ("the assignment problem"), and one of the assumptions in the algorithm is that non-matched edges are directed from one subgraph, A, to the other subgraph, B, and matched edges are directed the other way. Over the course of growing the matching, a simple way to add and remove edges from the candidate set is just to reverse the edge, thus the need for some way to reverse the edge within BGL. I don't think I can just remove and then re-add the edge in the other direction, primarily because doing so will (I believe) invalidate any edge_descriptors referring to that edge. In particular, there are property maps keeping track of the weight of edges, the predecessors of certain nodes, etc. that use edge descriptors as keys. I've spent a fair bit of time reading the documentation and looking through the implementation of adjacency_lists (incl. edge_list_impl), and I'm not really sure of a way to either move an edge directly within a graph, or even to create a new edge from another s.t. they have the same edge_descriptor (in general a bad thing, probably). Anyone have any thoughts on this? Thanks, -Josh
You could use hash_setS or setS for the Edge_list. This will allow you to remove edges and add edges without invalidating edge iterators or edge descriptors.
This is an interesting idea -- I do have the requirement that parallel edges are allowed (think of the point of the algorithm as reducing a muti-graph to a standard graph, s.t. the sum of all edge weights is maximal), so neither hash_setS nor setS would work. But, multisets appear to be an option, using the mutisetS selector. I think you're suggesting that I can use one of these other edgelist implementatations, then remove and re-add the edge. However, I'm not sure this is quite what I'm looking for, since in addition to not invalidating other iterators / descriptors (those other than the one I'm trying to reverse), it's critical that I not invalidate the edge descriptor for the edge I'm trying to reverse, since it's still going to be in the graph, and property maps will refer to it. What I think I really need is a way to move the edge within the graph (or at least remove the edge and re-add it, in a way that guarantees that the re-added edge has the same edge_descriptor as the original edge). Tracing through the implementation a bit of add_edge, I have an idea on how to do this, but it involves a fair bit of hacking and is not terribly clean (and probably doesn't work!): you could directly go into the edge_desc_impl class (really it's superclass edge_base) [from detail/edge.hpp] and swap the m_source and m_target members directly, then remove the edge from the source vertex edge list, create a StoredEdge instance and insert it into the target edge list. But I'm not sure how to link this new stored edge with the old edge_descriptor. Does this help clear things up? Again, thanks for the reply. -Josh --- In Boost-Users@y..., "Matthias Kronenberger" <mkronen@r...> wrote:
You could use hash_setS or setS for the Edge_list. This will allow you to remove edges and add edges without invalidating edge iterators or edge descriptors.
Quick clarification -- I really didn't mean to say that I want edge iterators to be stable -- that doesn't really make much sense, since I'm changing the link structure of the graph. Instead, I'm really focusing on having a stable edge_descriptor, since that is refered to by long-lived entities (e.g. property maps). Thanks, -Josh --- In Boost-Users@y..., "joshrose" <joshrose@y...> wrote:
This is an interesting idea -- I do have the requirement that parallel edges are allowed (think of the point of the algorithm as reducing a muti-graph to a standard graph, s.t. the sum of all edge weights is maximal), so neither hash_setS nor setS would work. But, multisets appear to be an option, using the mutisetS selector. I think you're suggesting that I can use one of these other edgelist implementatations, then remove and re-add the edge.
However, I'm not sure this is quite what I'm looking for, since in addition to not invalidating other iterators / descriptors (those other than the one I'm trying to reverse), it's critical that I not invalidate the edge descriptor for the edge I'm trying to reverse, since it's still going to be in the graph, and property maps will refer to it. What I think I really need is a way to move the edge within the graph (or at least remove the edge and re-add it, in a way that guarantees that the re-added edge has the same edge_descriptor as the original edge).
Tracing through the implementation a bit of add_edge, I have an idea on how to do this, but it involves a fair bit of hacking and is not terribly clean (and probably doesn't work!): you could directly go into the edge_desc_impl class (really it's superclass edge_base) [from detail/edge.hpp] and swap the m_source and m_target members directly, then remove the edge from the source vertex edge list, create a StoredEdge instance and insert it into the target edge list. But I'm not sure how to link this new stored edge with the old edge_descriptor.
Does this help clear things up?
Again, thanks for the reply.
-Josh
--- In Boost-Users@y..., "Matthias Kronenberger" <mkronen@r...> wrote:
You could use hash_setS or setS for the Edge_list. This will allow you to remove edges and add edges without invalidating edge iterators or edge descriptors.
Well, edge descriptors are std::pair of vertex descriptors, so they should stay stable unless you mutate the vertex_list. Mutating(erasing vertices) the vertex_list in BGL really doesn't make much sense. Independt from the vertex_list container, all vertex remove operations take O(N), where N is the number of vertices in your graph. Most of the time, it is better to unlink the vertex and create a new vertex with the same edges. Only now, the edge descriptor for all relinked edges changes. ----- Original Message ----- From: "joshrose" <joshrose@yahoo.com> Newsgroups: gmane.comp.lib.boost.user Sent: Thursday, July 25, 2002 7:06 PM Subject: Re: BGL and reversing / moving edges
Quick clarification -- I really didn't mean to say that I want edge iterators to be stable -- that doesn't really make much sense, since I'm changing the link structure of the graph. Instead, I'm really focusing on having a stable edge_descriptor, since that is refered to by long-lived entities (e.g. property maps).
Thanks,
-Josh
--- In Boost-Users@y..., "joshrose" <joshrose@y...> wrote:
This is an interesting idea -- I do have the requirement that parallel edges are allowed (think of the point of the algorithm as reducing a muti-graph to a standard graph, s.t. the sum of all edge weights is maximal), so neither hash_setS nor setS would work. But, multisets appear to be an option, using the mutisetS selector. I think you're suggesting that I can use one of these other edgelist implementatations, then remove and re-add the edge.
However, I'm not sure this is quite what I'm looking for, since in addition to not invalidating other iterators / descriptors (those other than the one I'm trying to reverse), it's critical that I not invalidate the edge descriptor for the edge I'm trying to reverse, since it's still going to be in the graph, and property maps will refer to it. What I think I really need is a way to move the edge within the graph (or at least remove the edge and re-add it, in a way that guarantees that the re-added edge has the same edge_descriptor as the original edge).
Tracing through the implementation a bit of add_edge, I have an idea on how to do this, but it involves a fair bit of hacking and is not terribly clean (and probably doesn't work!): you could directly go into the edge_desc_impl class (really it's superclass edge_base) [from detail/edge.hpp] and swap the m_source and m_target members directly, then remove the edge from the source vertex edge list, create a StoredEdge instance and insert it into the target edge list. But I'm not sure how to link this new stored edge with the old edge_descriptor.
Does this help clear things up?
Again, thanks for the reply.
-Josh
--- In Boost-Users@y..., "Matthias Kronenberger" <mkronen@r...> wrote:
You could use hash_setS or setS for the Edge_list. This will allow you to remove edges and add edges without invalidating edge iterators or edge descriptors.
Thanks for the reply. I'm not quite sure I understand -- are edge descriptors guaranteed to be std::pairs of vertex descriptors? Perhaps I was looking in the wrong place, but tracing through a call to add_edge, I wind up in detail/edge.hpp, in the definition of a class called edge_desc_impl when a new edge is created. (called from add_edge (Config::vertex_descriptor, Config::vertex_descriptor, const Config::edge_property_type&, directed_graph_helper<Config>&) in adjacency_list.hpp) Since this is a multigraph, though, memberwise comparison of the source and target can't be enough to disambiguate one edge from another. (They could have the same source and target, but have quite different properties associated with them by the property maps). Is an edge_descriptor, then, the address of the std::pair object, if that is indeed what's representing edges? If so, then I need to reuse the existing edge descriptor object. Changing the m_source and m_target (or first and second, if it is indeed a non-const std::pair) is pretty straightforward, but I feel that that's probably not all that needs to be done -- somehow it needs to be removed from the old source edge list and added to the old target edge list. (On a somewhat related note, I'm not exactly sure what the m_eproperty member of edge_desc_impl is for, or if I'd need to update that in some way). Just to try to clarify, I'm not changing the vertex set of the graph in any way -- all I want to do is take an existing edge in the graph and move it to a different source / target pair (reversing being an example of this) in a way that doesn't invalidate property maps that refer to this edge. The non-invalidation of property maps is the most crucial part -- if the new edge got a different edge descriptor, but somehow all property maps were automagically updated to point to this new value, it would be just as useful as just keeping the edge descriptor the same (though I suspect not terribly realistic). I'm sorry if I'm not being terribly clear on this and for having a bit of trouble understanding, and I really appreciate the help. -Josh --- In Boost-Users@y..., "Matthias Kronenberger" <mkronen@r...> wrote:
Well, edge descriptors are std::pair of vertex descriptors, so they should stay stable unless you mutate the vertex_list. Mutating(erasing vertices) the vertex_list in BGL really doesn't make much sense. Independt from the vertex_list container, all vertex remove operations take O(N), where N is the number of vertices in your graph. Most of the time, it is better to unlink the vertex and create a new vertex with the same edges. Only now, the edge descriptor for all relinked edges changes.
----- Original Message ----- From: "joshrose" <joshrose@y...> Newsgroups: gmane.comp.lib.boost.user Sent: Thursday, July 25, 2002 7:06 PM Subject: Re: BGL and reversing / moving edges
Quick clarification -- I really didn't mean to say that I want edge iterators to be stable -- that doesn't really make much sense, since I'm changing the link structure of the graph. Instead, I'm really focusing on having a stable edge_descriptor, since that is refered to by long-lived entities (e.g. property maps).
Thanks,
-Josh
--- In Boost-Users@y..., "joshrose" <joshrose@y...> wrote:
This is an interesting idea -- I do have the requirement that parallel edges are allowed (think of the point of the algorithm as reducing a muti-graph to a standard graph, s.t. the sum of all edge weights is maximal), so neither hash_setS nor setS would work. But, multisets appear to be an option, using the mutisetS selector. I think you're suggesting that I can use one of these other edgelist implementatations, then remove and re-add the edge.
However, I'm not sure this is quite what I'm looking for, since in addition to not invalidating other iterators / descriptors (those other than the one I'm trying to reverse), it's critical that I not invalidate the edge descriptor for the edge I'm trying to reverse, since it's still going to be in the graph, and property maps will refer to it. What I think I really need is a way to move the edge within the graph (or at least remove the edge and re-add it, in a way that guarantees that the re-added edge has the same edge_descriptor as the original edge).
Tracing through the implementation a bit of add_edge, I have an idea on how to do this, but it involves a fair bit of hacking and is not terribly clean (and probably doesn't work!): you could directly go into the edge_desc_impl class (really it's superclass edge_base) [from detail/edge.hpp] and swap the m_source and m_target members directly, then remove the edge from the source vertex edge list, create a StoredEdge instance and insert it into the target edge list. But I'm not sure how to link this new stored edge with the old edge_descriptor.
Does this help clear things up?
Again, thanks for the reply.
-Josh
--- In Boost-Users@y..., "Matthias Kronenberger" <mkronen@r...> wrote:
You could use hash_setS or setS for the Edge_list. This will allow you to remove edges and add edges without invalidating edge iterators or edge descriptors.
Hi Josh, On Thu, 25 Jul 2002, joshrose wrote: joshro> joshro> However, I'm not sure this is quite what I'm looking for, since in joshro> addition to not invalidating other iterators / descriptors (those joshro> other than the one I'm trying to reverse), it's critical that I joshro> not invalidate the edge descriptor for the edge I'm trying to joshro> reverse, since it's still going to be in the graph, and property joshro> maps will refer to it. What I think I really need is a way to joshro> move the edge within the graph (or at least remove the edge and joshro> re-add it, in a way that guarantees that the re-added edge has the joshro> same edge_descriptor as the original edge). Are you using internal property maps for the edges? Is so you, when you removed, and then add an edge, you could first read out all the property info, and then write it into the new edge. If you are using an external map for edges... how are you doing the lookup? You aren't using the edge_descriptor itself as the key are you? That is bad... instead you could add an integer ID internal property for edges, and then use that to do lookups. joshro> Tracing through the implementation a bit of add_edge, I have an joshro> idea on how to do this, but it involves a fair bit of hacking and joshro> is not terribly clean (and probably doesn't work!): you could joshro> directly go into the edge_desc_impl class (really it's superclass joshro> edge_base) [from detail/edge.hpp] and swap the m_source and joshro> m_target members directly, then remove the edge from the source joshro> vertex edge list, create a StoredEdge instance and insert it into joshro> the target edge list. But I'm not sure how to link this new joshro> stored edge with the old edge_descriptor. I suppose I could add the following function: reverse_edge(edge_descriptor e, graph& g) which would do what you are describing. However, if the property copying solution described above works for you, I'd rather not add the reverse_edge function. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Thanks for the suggestion to use edge indices rather than descriptors -- I'll give that a shot. And thanks for helping me out! -Josh --- In Boost-Users@y..., Jeremy Siek <jsiek@c...> wrote:
Hi Josh,
On Thu, 25 Jul 2002, joshrose wrote: joshro> joshro> However, I'm not sure this is quite what I'm looking for, since in joshro> addition to not invalidating other iterators / descriptors (those joshro> other than the one I'm trying to reverse), it's critical that I joshro> not invalidate the edge descriptor for the edge I'm trying to joshro> reverse, since it's still going to be in the graph, and property joshro> maps will refer to it. What I think I really need is a way to joshro> move the edge within the graph (or at least remove the edge and joshro> re-add it, in a way that guarantees that the re-added edge has the joshro> same edge_descriptor as the original edge).
Are you using internal property maps for the edges? Is so you, when you removed, and then add an edge, you could first read out all the property info, and then write it into the new edge.
If you are using an external map for edges... how are you doing the lookup? You aren't using the edge_descriptor itself as the key are you? That is bad... instead you could add an integer ID internal property for edges, and then use that to do lookups.
joshro> Tracing through the implementation a bit of add_edge, I have an joshro> idea on how to do this, but it involves a fair bit of hacking and joshro> is not terribly clean (and probably doesn't work!): you could joshro> directly go into the edge_desc_impl class (really it's superclass joshro> edge_base) [from detail/edge.hpp] and swap the m_source and joshro> m_target members directly, then remove the edge from the source joshro> vertex edge list, create a StoredEdge instance and insert it into joshro> the target edge list. But I'm not sure how to link this new joshro> stored edge with the old edge_descriptor.
I suppose I could add the following function:
reverse_edge(edge_descriptor e, graph& g)
which would do what you are describing. However, if the property copying solution described above works for you, I'd rather not add the reverse_edge function.
Cheers, Jeremy
---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@o... C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
(Apologize for being a bit confused about the property map library, but hopefully this posting doesn't smack too much of ignorance) One quick followup, though -- if I do follow the approach of an external property map keyed by edge id, won't I wind up having to do a potentially expensive lookup on the edge id every time I need to access properties keyed by edges? The reason I was going to originally use edge descriptors is that they're immediately available during the graph traversal at constant additional cost -- the algorithm involves a modified version of Dijkstra's shortest paths algo extended to multigraphs. (If I understand correctly, the standard Dijk algo in BGL doesn't handle mutigraphs, since it records predecessors as vertices, rather than edges.) By adding a lookup, I'm adding (at least) a log (E) factor to all operations that involve accessing edge properties, in particular to looking up edge weights -- in fact, the standard BGL Dijk algo seems to get around this precisely by using an weight_map keyed by edge_descriptors! (again, if I understand correctly). Since this lookup happens deep in the traversal, the potential effect on running time is probably quite noticable, esp. since for my application (statistical machine translation), each subgraph in the bipartite graph can have on the order of 500,000 nodes, and the graph can contain an order of magnitude larger number of edges. I think your suggestion about using the edge id and an extra level of indirection will help me achieve a correct solution for now, and I'll go ahead in that direction. Depending on the performance of the algo (this only needs to be run once in the beginning of a pipeline to bootstap a machine learning process), I'll look into ways to remove the extra lookup cost by using edge_descriptors as keys. Just a suggestion, though, that it would help at least one person out to have some sort of a move_edge function that could move an edge within a graph while maintaining edge properties and the descriptor (grin). If I do wind up writing something along these lines, perhaps I'll try to figure out the whole submission process for BGL. Thanks again. --- In Boost-Users@y..., "joshrose" <joshrose@y...> wrote:
Thanks for the suggestion to use edge indices rather than descriptors -- I'll give that a shot. And thanks for helping me out!
-Josh --- In Boost-Users@y..., Jeremy Siek <jsiek@c...> wrote:
Hi Josh,
On Thu, 25 Jul 2002, joshrose wrote: joshro> joshro> However, I'm not sure this is quite what I'm looking for, since in joshro> addition to not invalidating other iterators / descriptors (those joshro> other than the one I'm trying to reverse), it's critical that I joshro> not invalidate the edge descriptor for the edge I'm trying to joshro> reverse, since it's still going to be in the graph, and property joshro> maps will refer to it. What I think I really need is a way to joshro> move the edge within the graph (or at least remove the edge and joshro> re-add it, in a way that guarantees that the re-added edge has the joshro> same edge_descriptor as the original edge).
Are you using internal property maps for the edges? Is so you, when you removed, and then add an edge, you could first read out all the property info, and then write it into the new edge.
If you are using an external map for edges... how are you doing the lookup? You aren't using the edge_descriptor itself as the key are you? That is bad... instead you could add an integer ID internal property for edges, and then use that to do lookups.
joshro> Tracing through the implementation a bit of add_edge, I have an joshro> idea on how to do this, but it involves a fair bit of hacking and joshro> is not terribly clean (and probably doesn't work!): you could joshro> directly go into the edge_desc_impl class (really it's superclass joshro> edge_base) [from detail/edge.hpp] and swap the m_source and joshro> m_target members directly, then remove the edge from the source joshro> vertex edge list, create a StoredEdge instance and insert it into joshro> the target edge list. But I'm not sure how to link this new joshro> stored edge with the old edge_descriptor.
I suppose I could add the following function:
reverse_edge(edge_descriptor e, graph& g)
which would do what you are describing. However, if the property copying solution described above works for you, I'd rather not add the reverse_edge function.
Cheers, Jeremy
---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@o... C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Hi Josh, On Fri, 26 Jul 2002, joshrose wrote: joshro> One quick followup, though -- if I do follow the approach of an joshro> external property map keyed by edge id, won't I wind up having to joshro> do a potentially expensive lookup on the edge id every time I need joshro> to access properties keyed by edges? The reason I was going to No, the internal property maps supplied by adjacency_list all have constant time lookup. They are typically implemented by a pointer dereference and struct access, or via an array lookup. joshro> shortest paths algo extended to multigraphs. (If I understand joshro> correctly, the standard Dijk algo in BGL doesn't handle joshro> mutigraphs, since it records predecessors as vertices, rather than joshro> edges.) Yes, I'm afraid none of the BGL algorithms handle multigraphs. This would be a great direction to extend the BGL. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Hi Boost-Users, I am a PhD student in Operations Research (OR) and am new to boost/graph. For my research, I am solving some classical integer programs (IP), which often require solving subproblems with common graph structures. I was curious, who out there is using BGL in a similiar manner and if they would be willing to share their experiences/code off or on-line. There are already several algorithms in BGL which are commonly used in IP (shortest path, min spanning tree, etc). In addition, scanning old postings (July 2002), I noticed someone was working on bipartite matching. A repository of these tools seems like it would be a great addition to BGL (especaily for those working on IP). BTW, I am heavily involved in another open-source project called COIN-or, which provides several open-source tools for OR-types (www.coin-or.org) - I think some kind of integration between COIN and BGL could be great. Thanks in advance, Matthew Galati -- Matthew Galati ISE Lehigh University 610.758.4042 (Office) 610.882.0779 (Home) http://sagan.ie.lehigh.edu/mgalati/
participants (4)
-
Jeremy Siek -
joshrose -
Matthew Galati -
Matthias Kronenberger