[Lemon-user] Using Lemon for online algorithms

[CW]

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.  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.  :)

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).

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'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();

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