Bugs item #1168420, was opened at 2005-03-22 10:33 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168420&group_id=7586 Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Douglas Gregor (dgregor) Assigned to: Douglas Gregor (dgregor) Summary: LEDA graph adaptors for undirected graphs Initial Comment: 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. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1168420&group_id=7586 ------------------------------------------------------- This SF.net email is sponsored by: 2005 Windows Mobile Application Contest Submit applications for Windows Mobile(tm)-based Pocket PCs or Smartphones for the chance to win $25,000 and application distribution. Enter today at http://ads.osdn.com/?ad_id=6882&alloc_id=15148&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs