On Thursday, 20. May 2010 21:32:51 Trevor Harmon wrote:
On May 19, 2010, at 12:19 AM, Cedric Laczny wrote:
I have a graph with quite some information stored in its vertices and edges. Now I would like to perform some analyses on the general overall topology of the graph. Therefore I don't need this "big graph" but only a graph that has the same number of nodes and matching edges to the "big graph".
I am wondering if this is a case of premature optimization. Are you sure that removing these many properties attached to the vertices and edges would actually speed up the analysis? I would expect there to be little if any difference. Also, it is possible that the task of creating the duplicate graph would offset any speed gains there might be in the subsequent analysis.
Indeed, this is a good point. Copying the graph with copy_graph() takes O(|V| +|E|). Most of the algorithms I know/use will be linear or nearly linear, so this won't affect much of th asymptotic runtime. However, in reality this might indeed slow-up the whole thing. As said in the response to Jeremiah Willcock, I have two concerns on working on the original graph. First, the properties there are bundled properties and I don't know, neither do I if it's possible in general, how to add properties later on. Because second, I might implement different algorithms that may have special requirements (e.g. multiple flags) and always doing these adjustments on the original graph is something I don't know of if this would be a good/"nice" idea. In any case, I agree with you that _not_ doing all this copying would be favorable, as it is in most such cases. So if you have an idea, I will be happy to hear about. Best, Cedric
Trevor
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users