I checked and the graph is, in fact, disconnected. It has 4 connected components. Does this somehow explain the fact that the number of basics is less than the number of rows? <br><br>Thanks,<br>Matt<br><br><br><br><div class="gmail_quote">

On Wed, Mar 3, 2010 at 3:51 PM, Matthew Galati <span dir="ltr"><<a href="mailto:magh@lehigh.edu">magh@lehigh.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

In this case, it probably is NOT connected. I will check and get back to you. This comes from a multicommodity flow problem - so the extracted network should be disconnected.<div><div></div><div class="h5"><br><br><br><br>

<div class="gmail_quote">On Wed, Mar 3, 2010 at 3:40 PM, Alpár Jüttner <span dir="ltr"><<a href="mailto:alpar@cs.elte.hu" target="_blank">alpar@cs.elte.hu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Hi,<br>
<br>
Just a short question: is your graph connected?<br>
<br>
Btw, I had a short look at lemon/network_simplex.h and I was surprised<br>
to see that _state is declared as BoolVector, but it can get three<br>
different values (STATE_TREE, STATE_LOWER, STATE_UPPER). Luckily,<br>
BoolVector is currently defined an std::vector<char>, but to me it looks<br>
quite dirty.<br>
<br>
Regards,<br>
Alpar<br>
<div><div></div><div><br>
<br>
On Wed, 2010-03-03 at 10:22 -0500, Matthew Galati wrote:<br>
> Hi. I am trying to form a basis to hand a standard LP simplex solver<br>
> (dual simplex) after running LEMON's network simplex. From my<br>
> understanding, network simplex forms the basis as a spanning tree,<br>
> which will have m-1 entries (where m = the number of rows = the number<br>
> of nodes in network). And the last element of the basis would normally<br>
> come from a basic "artificial variable" - which seems it can be found<br>
> by looking for the row with _pi[i] = 0.<br>
><br>
> I am running against a Dimacs format file. Net simplex solves the<br>
> problem fine, but at the end, I print out the number of arcs with<br>
> STATE_TREE (basic) and it is not what I had expected. There are 256<br>
> nodes in the network, but only 252 links that are set to basic.<br>
><br>
> Am I interpreting the basis incorrectly? Or might there be a bug?<br>
><br>
> Let me know if you want the dimacs file to repeat the issue I am<br>
> seeing.<br>
><br>
> Thanks,<br>
> Matt<br>
</div></div>> _______________________________________________<br>
> Lemon-user mailing list<br>
> <a href="mailto:Lemon-user@lemon.cs.elte.hu" target="_blank">Lemon-user@lemon.cs.elte.hu</a><br>
> <a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
<br>
<br>
</blockquote></div><br>
</div></div></blockquote></div><br>