[Lemon-user] Using Lemon for online algorithms

[Kovács Péter]

Hi,

> Hello everyone, I'm not a very experienced coder, but I'm trying to
> implement an online algorithm in LEMON using its min-weight bipartite
> matching algorithms, and I'm running into an issue.

To be precise, LEMON does not provide bipartite matching algorithms yet. 
However, if you build a proper graph, you can use flow algorithms 
instead of the required matching algorithms. As far as I understand, you 
used this method.

 > I hate to send
> this out to an entire mailing list but I can't figure out why this is
> happening and I was hoping maybe someone out there has seen this
> before.  Feel free to delete this if you don't care.  :)

Any questions related to LEMON are welcomed here.

> I have graphs g, h, and i.  G is initially defined with all of the
> nodes and arcs for the entire simulation (it's used for reference), H
> and I are initially defined with all of the nodes but none of the
> edges (they're added as execution progresses).

Basically, different graph instances can assign different IDs for the 
graph items. Be aware about this if you work with more graph structures 
whose items are related to each other. In this case, you must add the 
nodes in _exactly_ the same order to all the three instances and you 
must not modify the node set after that. This ensures that the node set 
of g, h and i are exactly the same. However, this approach is still 
somewhat unsafe. It is not recommended to use e.g. a node of g in terms 
of the graph h or i if they are separate structures (not subgraphs). See 
an other suggestion below.

> 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

 > I'm using NetworkSimplex as the matching algorithm,
> and I'm working around the "graph can't change once NetworkSimplex is
> declared" by doing the following:
>
>          delete mine;
>          mine = new NetworkSimplex<ListDigraph, int, float>(i);
>          mine->costMap(onlineweight).supplyMap(onlinecapacity).run();

It seems to be good. Does it return the results you expect?

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

> I get the following output (at different places for different test
> input, and I can't find a common reason as to why it's happening).
> The lines above and below the text is to ensure that g.source(a) and
> g.target(a) match i.source(tempArc) and i.target(tempArc), so as to
> verify that edges are being added correctly (all of that output is
> just debug statements that I've been using to try to verify the
> problem).
>
> 1.1.17.60 0.28745-0 12.2109
> Inside the loop, next arriving node is 1.1.17.60
> Which should be the same as 1.1.17.60
> 1.1.17.60 0.28745-0 12.2109
> 1.1.17.60 0.28745-7 25.2109
> Inside the loop, next arriving node is 1.1.17.60
> Which should be the same as 1.1.17.60
> 1.1.17.60 0.28745-7 25.2109
> 1.1.17.60 0.28745-6 23.2109
> Inside the loop, next arriving node is 1.1.17.60
> Which should be the same as 1.1.17.60
> 1.1.17.60 0.28745-6 23.2109
> 1.1.17.60 0.28345-9 29.2109
> Inside the loop, next arriving node is 1.1.17.60
> Which should be the same as 1.1.17.60
> 1.1.17.60 0.28345-9 29.2109
> 1.1.17.60 0.28345-8 27.2109
> Inside the loop, next arriving node is 1.1.17.60
> Which should be the same as 1.1.17.60
>
> And then it hangs here.  So as you can see, it works fine for a number
> of edges, and then it just stops at some point that happens in every
> test case, but at a different point.  There's no common theme that I
> can tell, like "The first time I try to add edges after I delete
> edges, it freezes" or anything like that.  Additionally, it also works
> in its entirety for previous nodes.  In this particular case,
> 1.1.17.60 is the 4th node to arrive, and up until this point, it
> worked fine.
>
> Here's an example of the output for the previously arriving node:
>
> 38.188.24.240 0.28345-0 21.0599
> Inside the loop, next arriving node is 38.188.24.240
> Which should be the same as 38.188.24.240
> 38.188.24.240 0.28345-0 21.0599
> 38.188.24.240 0.28345-4 28.0599
> Inside the loop, next arriving node is 38.188.24.240
> Which should be the same as 38.188.24.240
> 38.188.24.240 0.28345-4 28.0599
>
> Running matching algorithm...
> Done running matching algorithm...
> Flow 38.188.24.240 0.28345-0 21.0599 8.94008
> Flow 1.1.206.153 0.27945-0 0.178309 29.8217
>
> Which is the correct behavior.
>
> So anyway, if anyone has any insight on why this might be happening,
> or wants to see more of the code because possibly there's a relevant
> part that I didn't include or whatever, please let me know.  For
> everyone else, I apologize for spamming you.
>
> Thank you,
> Corey Worrell

Regards,
Peter