[Lemon-user] SubDigraph and ListDigraph

[Alpár Jüttner]

On Tue, 2011-10-25 at 06:57 -0700, Todorov, Vladimir wrote:
> Hi,
> 
> It would have been nice if it actually  inherited the ListDigraph ....
> In such a case it would have been much easier to apply the same methods
> to the ListDigraph and the SubDigraph simply by casting the SubDigraph
> pointer into a ListDigraph one...  Thus, the interface would have
> remained the same.

This is not an option. A design like this would require that the whole
interface is written using virtual functions. This is not acceptable
because of the _huge_ running time overhead it would cause. There are
two reasons for that.
     1. The virtual function call is much slower than a regular one.
     2. More importantly, using virtual functions prevent inlining and
        therefore the further optimization of the inlined code. For
        example,  when you iterate through the arcs of the graph, of
        query the id of a node, all the necessary machine instructions
        will directly be inserted into your code with no function call
        at all. Remember, even a non-virtual function call is a very
        expensive operation.

Of course, the second reason is valid only if compiler optimization
(e.g. -O2 on gcc) is turned on. Always do it (except for debugging)! An
optimized code can easily be 10 times faster than a non-optimized one.
In fact, this is true for any code that uses STL (e.g. std::vector<>).

>  Now I need to double my code in order to be able to
> work with a ListDigraph and a particular subset of it....

A Peter pointed out, you don't, instead use template functions.

Of course it still increases the size of the executable, but you
basically shouldn't worry about it. The graph related codes are
typically very small. If an executable code is big, then it is because
of the system and third party libraries or the auxiliary data (such as
the debug info).

> 
> Regards,
> 
> Vladimir
> 
> -----Original Message-----
> From: Alpár Jüttner [mailto:alpar.juttner at gmail.com] On Behalf Of Alpár Jüttner
> Sent: Tuesday, October 25, 2011 3:40 PM
> To: Todorov, Vladimir
> Cc: lemon-user at lemon.cs.elte.hu
> Subject: Re: [Lemon-user] SubDigraph and ListDigraph
> 
> Hi,
> > 
> > I ran into a problem where I cannot convert a SubDigraph into a 
> > ListDigraph. I use the SubDigraph to construct a subgraph of my 
> > original ListDigraph. Now, how can I use the newly constructed 
> > SubDigraph as a ListDigraph…?
> 
> SubDigraph (and every other graph adaptor) doesn't create a physical graph structure in the memory, but instead it "simulates" the desired graph using the original graph and the auxiliary data. In spite of this, you can use it directly with any graph algorithm.
> 
> If you still need to "convert" it to a ListDigraph, you must make a copy of it, most practically by using the digraphCopy() utility, e.g.:
> 
> 
> ListDigraph g;
> ListDigraph::NodeMap<bool> n_filter(g);
> ListDigraph::ArcMap<bool> a_filter(g);
> ...
> SubDigraph<ListDigraph> sub_g(g,n_filter,a_filter); ...
> ListDigraph g2;
> digraphCopy(sub_g,g2);
> 
> Regards,
> Alpar
> 
>