[Lemon-user] Using Lemon for online algorithms

[Balazs Dezso]

Hi,

> ListDigraph::NodeMap<string> onlinename(i);
> 
> I get the following errors:
> 
> /media/disk/wq2010/research/algmatching5.cpp|88|error: no matching
> function for call to
> ‘lemon::DigraphExtender<lemon::ListDigraphBase>::NodeMap<std::basic_string<
> char, std::char_traits<char>, std::allocator<char> >
> 
> >::NodeMap(lemon::FilterArcs<lemon::ListDigraph,
> 
> lemon::DigraphExtender<lemon::ListDigraphBase>::ArcMap<bool> >&)’|
> 
> /usr/local/include/lemon/bits/graph_extender.h|227|note: candidates
> are: lemon::DigraphExtender<Base>::NodeMap<_Value>::NodeMap(const
> lemon::DigraphExtender<Base>&, const _Value&) [with _Value =
> std::basic_string<char, std::char_traits<char>, std::allocator<char>
> 
> >, Base = lemon::ListDigraphBase]|
If you want to create a node map for the subgraph, you have to use the 
following type:

FilterArcs<ListDigraph>::NodeMap<string> onlinename(i);

The FilterArcs<ListDigraph> is the subgraph type, which is fully conform to 
the lemon::concept::Digraph type. You can also iterate over the arcs of this 
graph:

for (FilterArcs<ListDigraph>::NodeIt n(i); n != INVALID; ++n) {
  cout << onlinename[n] << endl;
}

I hope, it helps to understand the meaning of graph adaptors. And sorry for 
the weaknesses of the documentation.

Best regards, Balazs

On Thursday 08 April 2010 04:50:03 CW wrote:
> First of all, thank you so much for the quick response.  I appreciate
> it very much.  One more question and hopefully this will be it.
> 
> >> The basic gist of it is that nodes arrive and lock.  When they arrive,
> >> I iterate through G and add the relevant edges to I.  When they lock,
> >> I iterate through I and delete the relevant edges from I (and add the
> >> one that matched via the matching algorithm to H, but that's not
> >> important here).
> >
> > I think, it would be easier and safer to use subgraph adaptors. E.g.
> >
> >  ListDigraph g;
> >  // build g by adding nodes and arcs
> >  ListDigraph::ArcMap<bool> filter_h(g, false), filter_i(g, false);
> >  FilterArcs h(g, filter_h), i(g, filter_i);
> >
> > This code snippet creates a digraph g and two subgraphs of it: h and i,
> > which contain all the nodes of g and no arcs. You can show/hide arcs of
> > the original graph g in subgraphs h and i by modifying the bool values in
> > the corresponding filter arc maps. Using this approach, you can use the
> > nodes and arcs of g in terms of h and i safely, and you can even use the
> > node/arc maps of g along with the subgraphs h and i. For more
> > information, see:
> > http://lemon.cs.elte.hu/pub/tutorial/sec_graph_adaptors.html#sec_subgraph
> >s
> 
> This is a very good idea and it is a lot safer than my implementation
> because I am actually deleting nodes and edges in i (I forgot to
> mention that when I delete arcs I also delete the locking node and
> whatever target it matched to), so this is much better.  Thank you so
> much.  I am running into one problem though.  What is the return type
> of:
> 
> FilterArcs<ListDigraph> h(g, filter_h), i(g, filter_i);
> 
> I assume it's a ListDigraph, but the problem arises when I do
> something like the following:
> 
> ListDigraph::ArcMap<bool> filter_h(g, false), filter_i(g, false);
> FilterArcs<ListDigraph> h(g, filter_h), i(g, filter_i);
> 
> ListDigraph::NodeMap<string> onlinename(i);
> 
> I get the following errors:
> 
> /media/disk/wq2010/research/algmatching5.cpp|88|error: no matching
> function for call to
> ‘lemon::DigraphExtender<lemon::ListDigraphBase>::NodeMap<std::basic_string<
> char, std::char_traits<char>, std::allocator<char> >
> 
> >::NodeMap(lemon::FilterArcs<lemon::ListDigraph,
> 
> lemon::DigraphExtender<lemon::ListDigraphBase>::ArcMap<bool> >&)’|
> 
> /usr/local/include/lemon/bits/graph_extender.h|227|note: candidates
> are: lemon::DigraphExtender<Base>::NodeMap<_Value>::NodeMap(const
> lemon::DigraphExtender<Base>&, const _Value&) [with _Value =
> std::basic_string<char, std::char_traits<char>, std::allocator<char>
> 
> >, Base = lemon::ListDigraphBase]|
> 
> And so on (there's a couple more but you get the point).  Is this not
> a ListDigraph, but rather some sort of new type like ListSubDigraph or
> something?  I apologize if this was in the documentation, I didn't
> seem to see it.  The description for FilterArcs says "Creates a
> subdigraph for the given digraph with the given arc filter map.", but
> I wasn't sure if this meant that subdigraph was its own type or not,
> and I didn't seem to see any subgraph types listed in the Graph
> Structures data structures page.
> 
> >> Which seems to have worked fine so far.  The problem is this.  No
> >> matter what test input I generate, the program seems to freeze at some
> >> point while adding edges.  Everything else performs exactly how it's
> >> supposed to up until the point that it freezes, but in the following
> >> section of code (the line where it's freezing is marked):
> >>
> >>         for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
> >>         {
> >>             if ((g.source(a) == arrNode))
> >>             {
> >>                 cout<<  name[g.source(a)]<<  " "<<  name[g.target(a)]
> >> <<  " "<<  weight[a]<<  endl;
> >>                 cout<<  "Inside the loop, next arriving node is "<<
> >> onlinename[arrNode]<<  endl;
> >>                 cout<<  "Which should be the same as "<<
> >> name[g.source(a)]<<  endl;
> >>                 ListDigraph::Arc tempArc = i.addArc(arrNode,
> >> g.target(a)); //This line is freezing the program!!!!!!!!!!
> >>                 onlineweight[tempArc] = weight[a];
> >>                 cout<<  name[i.source(tempArc)]<<  " "<<
> >> name[i.target(tempArc)]<<  " "<<  onlineweight[tempArc]<<  endl;
> >>             }
> >>         }
> >
> > I think, the only reason for which the addArc() function can fail is that
> > the graph structure does not contain the given nodes. Are you sure that
> > the node set of g, h and i are exactly the same throughout these loops?
> > Could you check i.valid(arrNode) and i.valid(g.target(a)) before trying
> > to add the arc?
> 
> That was part of the reason for those outputs above and below the
> text, so I could make sure that the arcs were being added as I
> intended because I am actually deleting nodes from i (not from h or g,
> though).  i.valid(arrNode) and i.valid(g.target(a)) do return 1, even
> in the case where it's freezing.  However, since this is probably the
> wrong approach to take (due to the fact that I'm deleting nodes and
> arcs), once I get the subgraphs working hopefully it won't freeze
> anymore.
> 
> > Regards,
> > Peter
> 
> Thank you so very much,
> Corey
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>