[Lemon-user] Code snippet to iterate over a map ?

[Kovács Péter]

Dear Diego,

Consider to use ConstMapIt instead of MapIt, since you have a constant 
reference for the PredMap.

The only difference between ConstMapIt and MapIt is that using MapIt, 
*it can also be modified.

Regards,
Peter

2010.06.24. 23:07 keltezéssel, Diego Taylor írta:
> Hi Péter,
>
> Thank for your prompt response. I tried to follow the "MapIt route"
> without success, the compilation gives:
>
> scheduler.cc: In member function ‘void
> DAGScheduler::put(lemon::ListDigraphBase::Node)’:
> scheduler.cc:48: error: no matching function for call to
> ‘lemon::MapExtender<lemon::DefaultMap<lemon::DigraphExtender<lemon::ListDigraphBase>,
> lemon::ListDigraphBase::Node, lemon::ListDigraphBase::Arc>
>  >::MapIt::MapIt(const
> lemon::DigraphExtender<lemon::ListDigraphBase>::NodeMap<lemon::ListDigraphBase::Arc>&)’
> /usr/local/include/lemon/bits/map_extender.h:95: note: candidates are:
> lemon::MapExtender<_Map>::MapIt::MapIt(const lemon::MapExtender<_Map>&,
> const typename _Map::Key&) [with _Map =
> lemon::DefaultMap<lemon::DigraphExtender<lemon::ListDigraphBase>,
> lemon::ListDigraphBase::Node, lemon::ListDigraphBase::Arc>]
> /usr/local/include/lemon/bits/map_extender.h:91: note:
> lemon::MapExtender<_Map>::MapIt::MapIt(lemon::MapExtender<_Map>&) [with
> _Map = lemon::DefaultMap<lemon::DigraphExtender<lemon::ListDigraphBase>,
> lemon::ListDigraphBase::Node, lemon::ListDigraphBase::Arc>]
> /usr/local/include/lemon/bits/map_extender.h:89: note:
> lemon::MapExtender<_Map>::MapIt::MapIt(lemon::Invalid) [with _Map =
> lemon::DefaultMap<lemon::DigraphExtender<lemon::ListDigraphBase>,
> lemon::ListDigraphBase::Node, lemon::ListDigraphBase::Arc>]
> /usr/local/include/lemon/bits/map_extender.h:87: note:
> lemon::MapExtender<_Map>::MapIt::MapIt() [with _Map =
> lemon::DefaultMap<lemon::DigraphExtender<lemon::ListDigraphBase>,
> lemon::ListDigraphBase::Node, lemon::ListDigraphBase::Arc>]
> /usr/local/include/lemon/bits/map_extender.h:80: note:
> lemon::MapExtender<lemon::DefaultMap<lemon::DigraphExtender<lemon::ListDigraphBase>,
> lemon::ListDigraphBase::Node, lemon::ListDigraphBase::Arc>
>  >::MapIt::MapIt(const
> lemon::MapExtender<lemon::DefaultMap<lemon::DigraphExtender<lemon::ListDigraphBase>,
> lemon::ListDigraphBase::Node, lemon::ListDigraphBase::Arc> >::MapIt&)
> make: *** [dgraph] Error 1
>
> The line is:
> ---------- o ----------
> const Bfs<ListDigraph>::PredMap& predMap = bfs.predMap();
> typedef ListDigraph::NodeMap<ListDigraph::Arc> PM;
>
> for(PM::MapIt it(predMap); it != INVALID; ++it) {}
> ---------- o ----------
>
> Thank you,
> Diego
>
> 2010/6/24 Kovács Péter <kpeter at inf.elte.hu <mailto:kpeter at inf.elte.hu>>
>
>     Hi,
>
>     If you would like to iterate over all nodes, then you can simply use
>     NodeIt:
>
>     for (GraphType::NodeIt u(g); u != INVALID; ++u)
>     cout << g.id <http://g.id>(u) << " pred arc: " << g.id
>     <http://g.id>(bfs.predArc(u)) << "\n";
>
>     for (GraphType::NodeIt u(g); u != INVALID; ++u)
>     cout << g.id <http://g.id>(u) << " pred node: " << g.id
>     <http://g.id>(bfs.predNode(u)) << "\n";
>
>     If your PredMap is a standard NodeMap<Arc>, then you can also use
>     its MapIt or ConstMapIt iterator type (though it is not documented
>     yet as far as I know):
>
>     typedef GraphType::NodeMap<GraphType::Arc> PredMap;
>     PredMap pred = bfs.predMap();
>     for (PredMap::MapIt it(pred); it != INVALID; ++it)
>     cout << g.id <http://g.id>(it) << " pred arc: " << g.id
>     <http://g.id>(*it) << "\n";
>
>     On the other hand, if you would like to iterate over the visited
>     nodes only (for efficiency reasons), then you could either
>     1. run the algorithm step-by-step and do the required operations
>     meantime (consider to use init(), addSource(), emptyQueue(),
>     nextNode(), processNextNode() functions) or
>     2. run the algorithm at once using run(), but use a special
>     ProcessedMap to keep track the visited nodes (consider to use e.g.
>     LoggerBoolMap for this purpose):
>     http://lemon.cs.elte.hu/pub/doc/1.2/a00515.html#g21ca379ec2c92eccd71b76df0a9eee8c
>     Once you stored the nodes in a container, you can easily iterate
>     over them and you can obtain pred values using predNode(), predArc()
>     or predMap().
>
>     I hope that I could answer your questions.
>
>     Best regards,
>     Peter
>
>
>
>         Hi,
>
>         I can't get the map iterator from predMap to work after a bfs (don't
>         know the syntaxis for that). How can I iterate over all results
>         including nodes (keys) and values? I couldn't find an example
>         either. A
>         small code snippet will be more than helpful.
>
>
>         Thank You,
>         Diego
>
>
>