On Mon, Mar 16, 2009 at 5:30 PM, Michael Fawcett <michael.fawcett@gmail.com> wrote:
On Mon, Mar 16, 2009 at 5:15 PM, Juan Antonio Farré Basurte <jafb@tinet.org> wrote:
Please try not to top post per guidelines. I've lost the attributions unfortunately, but fixed the formatting a little.
I meant for OutEdgeList, however I went back and tried vecS for EdgeList as well and all my tests still passed and my program output was still correct. Perhaps this was corrected in code but the docs weren't updated?
I don't think so... I'm working with version 1.38 and I had a std::map with edge_descriptor keys. I passed this map, wrapped as an associative_property_map, and added to a dynamic_properties object, to graph-reading functions. When I traversed the map contents to do something useful with it, looks like the descriptors where invalid. In some cases it just looked to do nothing. In other cases I got segmentation fault. When I changed to listS, everything worked all right. In the documentation it just says that it's "not guarranted" to work. And looks to be true. Works in some cases and not in others.
It sounds like something assumes that those descriptors will not be invalidated unless removed. Maybe Andrew can chime in?
I would guess it's working for me by accident since I'm never removing anything from the graphs I create. I'll make sure to keep my usage to listS for now.
Reposting with subject line changed. --Michael Fawcett
I would guess it's working for me by accident since I'm never removing anything from the graphs I create. I'll make sure to keep my usage to listS for now.
Be forewarned: num_edges()/num_vertices() with listS is O(n). Andrew Sutton andrew.n.sutton@gmail.com
On Tue, Mar 17, 2009 at 11:42 AM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
I would guess it's working for me by accident since I'm never removing anything from the graphs I create. I'll make sure to keep my usage to listS for now.
Be forewarned: num_edges()/num_vertices() with listS is O(n).
So what's the recommendation? The Known Bugs page says that anything other than listS is not guaranteed to work for EdgeList, but if std::list has O(n) size(), then num_edges()/num_vertices() becomes O(n)? Or were you talking about OutEdgeList? Are there *known* cases where vecS is bug-free when used for the EdgeList? In my case, I know the total number of edges ahead of time, and no edges or vertices will ever be removed. --Michael Fawcett
So what's the recommendation? The Known Bugs page says that anything other than listS is not guaranteed to work for EdgeList, but if std::list has O(n) size(), then num_edges()/num_vertices() becomes O(n)?
Or were you talking about OutEdgeList?
Both. Any selector of listS will cause corresponding functions that use size() to be linear. I'm just giving a reminder since it's bitten me before :) On a side note, there are two new graph classes in trunk ([un]directed_graph) that wrap listS selected adjacency lisst and provide O(1) num_* and *degree functions. They also provide builtin index maps and functinality for renumbering vertices/edges. They aren't really documented yet and certainly won't be part of the release for a while.
Are there *known* cases where vecS is bug-free when used for the EdgeList? In my case, I know the total number of edges ahead of time, and no edges or vertices will ever be removed.
I think the general rule is that if you don't need to remove anything, you can use vecS wherever you want. It's the removals that really kill the adjacency list. Andrew Sutton andrew.n.sutton@gmail.com
On Tue, Mar 17, 2009 at 11:56 AM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
So what's the recommendation? The Known Bugs page says that anything other than listS is not guaranteed to work for EdgeList, but if std::list has O(n) size(), then num_edges()/num_vertices() becomes O(n)?
Or were you talking about OutEdgeList?
Both. Any selector of listS will cause corresponding functions that use size() to be linear. I'm just giving a reminder since it's bitten me before :)
I'll keep that in mind, thanks.
On a side note, there are two new graph classes in trunk ([un]directed_graph) that wrap listS selected adjacency lisst and provide O(1) num_* and *degree functions. They also provide builtin index maps and functinality for renumbering vertices/edges. They aren't really documented yet and certainly won't be part of the release for a while.
Looking forward to this. We subclassed adjacency_list and made our own undirected_graph, but I'd like to stop using it and use yours.
Are there *known* cases where vecS is bug-free when used for the EdgeList? In my case, I know the total number of edges ahead of time, and no edges or vertices will ever be removed.
I think the general rule is that if you don't need to remove anything, you can use vecS wherever you want. It's the removals that really kill the adjacency list.
Luckily our graphs are immutable, so I'll continue to use vecS for OutEdgeList and start using it for EdgeList as well. Thanks, --Michael Fawcett P.S. sorry for the subject line mess up.
Hello, I need to convert any bidirectional graph into an adjacency_list<vecS,vecS,directedS>, but looks like the copy constructor cannot handle it (needs the same type in input). I don't see any simple way to convert any directed graph into an adjacency_list<vecS,vecS,directedS>. Is there any more-or-less-simple way to do it that I don't know? May be there is a way to copy graphs constrained not by the concrete type of the graph, but only, may be, on graph concepts? Thanks, Juan
I need to convert any bidirectional graph into an adjacency_list<vecS,vecS,directedS>, but looks like the copy constructor cannot handle it (needs the same type in input). I don't see any simple way to convert any directed graph into an adjacency_list<vecS,vecS,directedS>. Is there any more-or-less-simple way to do it that I don't know? May be there is a way to copy graphs constrained not by the concrete type of the graph, but only, may be, on graph concepts? Thanks,
There's no direct conversion between *any* bidirectional graph and a directed adjancency_list. If you're talking about any bidirectional adjacency list and a directed one, you shouldn't actually need to convert them. As an alternative, you could use copy_graph. Andrew Sutton andrew.n.sutton@gmail.com
participants (3)
-
Andrew Sutton -
Juan Antonio Farré Basurte -
Michael Fawcett