[Lemon-user] Using Lemon for online algorithms

[CW]

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_subgraphs
>

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