[Lemon-user] Using Lemon for online algorithms

[Kovács Péter]

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