[Lemon-user] Iterate through weighted edges

[Gabor Retvari]

On Monday 14 February 2011 12:32:09 Alpár Jüttner wrote:

> > I want to create a graph with weighted edges and iterate through
> > outgoing edges of a given node with ascending weights.
> 
> Unfortunately you must somehow sort the edges by hand in this case.

Dear all,

It occurred to me earlier that using STL algorithms with LEMON would be pretty 
nice indeed. This would solve the above issues as well. Some of the most used 
STL algorithms (like "find", "copy", etc.) are reimplemented in LEMON over 
LEMON maps ("mapCopy", "mapFind", etc.), but the lack of a good "sort", 
"count", "replace", etc. is a real pain. You constantly need to copy out maps 
into a std::vectors or similar, call the STL algorithm and then plug the 
result back to LEMON somehow.

I once started to write an iterator adaptor class that would make a LEMON 
nodemap or arcmap look to STL like a standard STL iterator. This would make it 
possible to seamlessly call STL algorithms, like "sort", directly to LEMON 
maps without the need to copy the maps out into STL containers. I achieved 
some sort of advance, but my lack of time and C++ skills inhibited me to 
decide whether the fact that it does not work is due to that I coded the idea 
badly, or it is straight out impossible to do what I want.

I attach the code I could come up with to this mail in the hope that someone 
more knowledgeable than me would find it useful, or finish it up, or at least 
explain me why the idea I tried to implement does not work. In fact, I only 
did the ForwardIterator, so "sort" is not expected to work but "find" and 
"copy" are. Doing the RandomAccessIterator is another matter, of course.

The idea is to have an iterator adaptor class that, given a graph 'g', a 
nodemap 'm(g)' and a node iterator 'n(g)', would make it possible to declare

node_map_it it(m, n);

and then 'it' would return the node the cursor is at, and '*it' would give the 
map's value associated with this node. The same for arcs.

What I have so far is:

1. STL copy into output iterator works

  copy (arc_map_it<int>(w, ArcIt(g)), 
        arc_map_it<int>(w, INVALID), 
        ostream_iterator<int>(cout, "\n"));

2. STL copy into std::list does not seem to work (compiles but does not print 
anything at all)

  list<int> l;
  copy(arc_map_it<int>(w, ArcIt(g)),
       arc_map_it<int>(w, INVALID),
       l.begin());

  copy (l.begin(), l.end(), ostream_iterator<int>(cout, "\n"));

3. STL find halfway works: finds the value but does not return the 
corresponding node

  arc_map_it<int> it = find(arc_map_it<int>(w, ArcIt(g)), 
                            arc_map_it<int>(w, INVALID), 
                            42);
  // this writes 42 as expected
  cout << "Map value found: " << *it << endl;

  // cannot get this to compile
  //  cout << "Node id with weight 42: " << g.id(it) << endl;


I am open to comments, should you have any idea how to improve it further. I 
really would like to see something similar in LEMON.

Best regards,
Gabor


-- 
Gábor Rétvári, Ph.D.
Research Fellow, BME-TMIT
Phone: +36-1-463-1060
Fax: +36-1-463-1763
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.cpp
Type: text/x-c++src
Size: 3351 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20110216/fe6b3cbb/attachment.cpp>