[Lemon-user] Using Lemon for online algorithms

[CW]

I think it was more of a weakness in my coding skill than it was a
weakness in the documentation.  Now that I think about it, it makes
perfect sense.  I did read that tutorial page, but it didn't click as
thinking of it as a type.  It's really completely my fault.  Sorry
about that.

Corey

2010/4/7 Kovács Péter <kpeter at inf.elte.hu>:
> Hi,
>
>> I hope, it helps to understand the meaning of graph adaptors. And
>> sorry for the weaknesses of the documentation.
>
> I don't think that the documentation of the graph adaptors is weak.
> The library documentation is intended to be a reference manual, so it should
> not contain extensive explanations. However, there is a compact description
> of using graph adaptors in the corresponding module:
> http://lemon.cs.elte.hu/pub/doc/1.2/a00514.html
>
> On the other hand, the LEMON tutorial explain graph adaptors in details with
> several examples and images.
> http://lemon.cs.elte.hu/pub/tutorial/sec_graph_adaptors.html
> I do find it a strong part of the tutorial. Moreover, there is an entire
> subsection about the subgraph adaptors. I also sent a link for this in my
> first email.
>
> Regards,
> Peter
>
>
>
> 2010.04.08. 7:10 keltezéssel, Balazs Dezso írta:
>>
>> 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
>>>
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>