[Lemon-user] Run algorithm on SubDigraph but use (original) Digraph maps

[Alpar Juttner]

Hi,

The class Dijkstra has three template parameters:

template<typename GR, typename LEN, typename TR>
class lemon::Dijkstra< GR, LEN, TR >;

The first one is the type of the graph, while the second one specifies
the type of the length map. It defaults to GR::ArcMap<int>.

So, if you want to use anything else than SubDigraph::ArcMap<int> you
must give it explicitly, like this:

Dijkstra<SubDigraph, Digraph::ArcMap<int> > dijkstra_alg3(sub_dg,
length);

This will work, because the LEN object can be any kind of map that
returns a value when its operator[] is called with a GR::Arc.
And SubDigraph::Arc converts to Digraph::Arc, so everything is fine.

The type of the length values are also obtained from the second
template parameter, they defaults to LEN::Value. But it can also be
changed using the third template parameter (TR).

When using the function type interface, it sets the second template
parameter appropriately. That's why you didn't have problems.

Regards,
Alpár


On Thu, 2017-01-26 at 17:59 +0000, David Franz Koza wrote:
> Dear all,
>  
> I’m trying to get a better understanding of lemon graph adaptors in
> combination with algorithms (function vs class interface). I have a
> Digraph and a corresponding SubDigraph. I would like to run an
> algorithm (e.g. Dijkstra) on the SubDigraph, but use the original
> Digraph maps as input. This is what I tried:
>  
> using namespace lemon;
> typedef SmartDigraph Digraph;
> typedef lemon::SubDigraph<Digraph, Digraph::NodeMap<bool>,
> Digraph::ArcMap<bool>> SubDigraph;
>  
> Digraph g;
> Digraph::Node s = g.addNode();
> // add further nodes here...
> Digraph::NodeMap<bool> node_filter(g);
> Digraph::ArcMap<bool> arc_filter(g);
> Digraph::ArcMap<int> length(g);
> // fill above maps with values...
> Digraph::NodeMap<int> dist(g);
>  
> // this works:
> Dijkstra<Digraph> dijkstra_alg(g, length);
>  
> // create a SubDigraph of g based on node_filter and arc_filter maps:
> SubDigraph sub_dg(g, node_filter, arc_filter);
>            
> // this would work, but requires a new map defined over the
> SubDigraph:
> SubDigraph::ArcMap<int> length_sub(sub_dg);
> Dijkstra<SubDigraph> dijkstra_alg2(sub_dg, length_sub);     
>  
> // this gives an error:
> Dijkstra<SubDigraph> dijkstra_alg3(sub_dg, length);
> // when using the function interface, this works:
> dijkstra(subDigraph(g, node_filter, arc_filter),
> length).distMap(dist).run(s);
>  
> Why can I use subDigraph() (which returns a SubDigraph adaptor) in
> the dijkstra function interface together with maps of the original
> graph, and why does the line above using the class interface not
> work? Am I not using the class interface correctly or, in other
> words, how can I use the Dijkstra class interface for a SubDigraph
> while using the original Digraph maps?
>  
> Thanks,
> David
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user