Opened 18 years ago
Last modified 11 years ago
#373 reopened Feature Requests
LEDA graph adaptors for undirected graphs
Reported by: | Douglas Gregor | Owned by: | Jeremiah Willcock |
---|---|---|---|
Milestone: | To Be Determined | Component: | graph |
Version: | Boost 1.39.0 | Severity: | Not Applicable |
Keywords: | Cc: | ich@… |
Description (last modified by )
The LEDA graph adaptors in the BGL seem to work properly for directed graphs (the LEDA type GRAPH<...>), but there are no corresponding adaptors for the undirected LEDA graph type (UGRAPH<...>). Undirected LEDA graphs follow a very different model than the undirected graphs in the BGL, which will require some special machinery. The LEDA type UGRAPH<...> is actually just a class derived from GRAPH<...> that applies the "make_undirected()" member function upon initialization. make_undirected() moves all of the in-edges of each vertex to the out-edges list. This has several unfortunate consequences: 1) The in-degree of an undirected LEDA graph is always zero, even when the out-degree is greater than zero. The in_edges list is therefore empty. 2) When traversing the list of out-edges for a vertex u, the edges returned may have u as their target but not their source. This breaks an important invariant in the BGL, which mandates that source(e, g)==u if e came from out_edges(u, g). Similarly for in-edges. Thus, an undirected LEDA graph adaptor will need to introduce special adaptors for the out_edge_iterator and in_edge_iterator types, which return a new edge_descriptor type for LEDA that can swap the source and target of a LEDA edge as needed. Additionally, graph-mutating operations (such as add_edge) may need to ensure that the graph remains undirected, as if make_undirected() had been called.
Change History (6)
comment:1 by , 15 years ago
Owner: | changed from | to
---|---|
Severity: | → Optimization |
Status: | assigned → new |
comment:2 by , 14 years ago
Description: | modified (diff) |
---|---|
Owner: | changed from | to
comment:3 by , 13 years ago
Milestone: | → Boost 1.40.0 |
---|---|
Owner: | changed from | to
Severity: | Optimization → Not Applicable |
Status: | new → assigned |
Version: | None → Boost 1.39.0 |
Does this issue still apply to the current SVN HEAD? If so, do you have a patch available?
comment:4 by , 13 years ago
Resolution: | None → wontfix |
---|---|
Status: | assigned → closed |
I am closing all of the LEDA-related bugs unless someone else is willing to fix them.
comment:5 by , 11 years ago
Cc: | added |
---|---|
Milestone: | Boost 1.40.0 → To Be Determined |
Resolution: | wontfix |
Status: | closed → reopened |
Documentation: http://www.algorithmic-solutions.info/leda_manual/ugraph.html#Undirected_Graphs
This seems worthwhile and quite easy to solve. Besides, I think when having undirected graph support, we can make clear that the "normal" adapter for LEDA graphs expects directed graphs.
Note:
See TracTickets
for help on using tickets.
Assigned to "doug_gregor" instead of nonexistent user "dgregor"