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

[Alpár Jüttner]

Hi,

Just for the sake of completeness:

If you want to iterate backward over the nodes/edges of a path found by
bfs from node s to node t, then you can either:

        for(Node n=t;n!=INVALID;n=bfs.predNode(t)) {}
        ...
        for(Arc a=bfs.predArc(t);a!=INVALID;a=bfs.predNode(g.target(a)))
        {}
        
or (for the arcs only)

        typedef Bfs<ListDigraph>::Path BfsPath;
        BfsPath p = bfs.path(t);
        for(BfsPath::RevArcIt a(p);a!=INVALID;a++) {}
                
        
Note that this p in an "implicit path", i.e. the nodes/edges are not
physically copied. Therefore it is as efficient as the above example.

If you want to iterate forward, then the easiest way is probably this:

        #include<lemon/path.h>
        Path p = bfs.path(t);
        for(Path::ArcIt a(p);a!=INVALID;a++) {}

Regards,
Alpar
        


On Thu, 2010-06-24 at 21:39 +0200, Kovács Péter wrote:
> 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(u) << " pred arc: " << g.id(bfs.predArc(u)) << "\n";
> 
>    for (GraphType::NodeIt u(g); u != INVALID; ++u)
>      cout << g.id(u) << " pred node: " << 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(it) << " pred arc: " << 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
> 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user