Re: [Boost-users] Help on creating a custom InputIterator for boost graph adjacency_list()

Subject: Re: [Boost-users] Help on creating a custom InputIterator for boost graph adjacency_list()
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-05-21 04:20:44

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users