[Lemon-user] number of STATE_TREE vars at end of network simplex (on connected graph)
Alpár Jüttner
alpar at cs.elte.hu
Tue Mar 9 15:00:35 CET 2010
On Tue, 2010-03-09 at 08:01 -0500, Matthew Galati wrote:
> Thanks Alpár,
>
> It would seem that we want the tree arcs in the final spanning tree
> (to maintain optimality). I see that you are putting them first in the
> arcs object. Looking at kruskals, it first sorts that object.
Not really. You can use kruskal in two different ways.
* You can pass the arc cost in a Graph::ArcMap<NumType>. In this
case the algorithm sets up an std::vector<
std::pair<Arc,NumType> >, puts all the arcs and costs into it,
then _sorts_ the vector according the costs, then proceed as for
the second case.
* You can give an std::vector< std::pair<Arc,NumType> > directly
to kruskal(). Then it will _not_ sort it but will assume it is
already sorted. Thus, it picks the arcs one-by-one and adds to
the chosen arcs if it is does not form a cycle. The cost are
only used for counting the total cost of the solution and for
nothing else.
Rational: Sorting is a costly operational, in fact it is costlier than
finding the minimum spanning tree afterward. Therefore you have an
option to skip the sorting if you have already know the right order.
> How can you be sure that those arcs are chosen first by Kruskal's -
> since the algorithm will choose based on weight? To be safe, maybe we
> should put an artificially low weight on those tree arcs in the arcs
> object?
Yes, you can set them 0 for the 'not-on-border' arcs and to 1 for the
others. But you can safely assume that kruskal() works as detailed
above.
The fact that the second mode does not use the cost (just sums the
values) makes it possible for finding the min.cost tree according to a
cost function and computing its cost according to another.
Regards,
Alpar
>
>
>
>
> 2010/3/9 Alpár Jüttner <alpar at cs.elte.hu>
> Hmmm. I didn't noticed before, that the bases in the two
> representations
> aren't necessarily the same. Shouldn't NetworkSimplex provide
> this
> functionality built-in?
>
> Anyway, you can reconstruct the basis quite easily from the
> solution
> without having to touch the network simplex implementation.
>
> For this you have to select the arcs the flow of which are
> neither at
> the lower nor at the upper bound, then you have to extend
> these arcs to
> a spanning tree. You can do it in almost linear time with
> Kruskal alg,
> like this:
>
> int A=countArcs(g);
> ///This will contain <arc,cost> pairs. We don't use the second
> value
> ///but only the order. Kruskal will pick up the arcs starting
> from the
> ///beginning of this vector.
> std::vector<std::pair<Graph::Arc,int> > arcs(A);
> int b=0;
> int e=A-1;
> ///Fill the `arcs` with the edges,
> ///those are not on the boundary will come first
> for(Graph:ArcIt a(g);a!=INVALID;++a)
> if(lower[a]<flow[a] && flow[a]<upper[a])
> arcs[b++] = std::pair<Graph::Arc,int>(a,1);
> else arcs[e--] = std::pair<Graph::Arc,int>(a,1);
> ///This vector will contain the basis:
> std::vector<Arc> basis;
> ///Run kruskal. We don't know the size of the solution in
> advance,
> ///that's why we start with az empty vector and use the
> back_inserter
> kruskal(g,arcs,std::back_inserter(basis));
>
> See the kruskal doc for more details
> http://lemon.cs.elte.hu/pub/doc/1.1.2/a00443.html#ga0b63cab19a2f168772a13d7c59449eb
>
> Disclaimer: I haven't try to compile the code above, so you
> should
> except bugs/typos in it.
>
> Regards,
> Alpar
>
>
>
>
> On Tue, 2010-03-09 at 08:02 +0100, Kovács Péter wrote:
> > Dear Matt,
> >
> > In short, the network simplex algorithm works with an
> extended graph,
> > not the original one. This method causes the unexpected
> results.
> >
> > For more details, recall the notes I wrote in one of my
> previous emails:
> >
> > > One more note: the current implementation of the network
> simplex
> > > algorithm extends the graph with an artificial root node
> and several
> > > artificial arcs connected to this root node to quickly
> form a starting
> > > basis. So, the digraph is made (weakly) connected even if
> it was not
> > > connected. Then the algorithm operates on the new digraph
> with
> > > spanning trees, but at the end, the results are
> interpreted in terms
> > > of the original digraph, that's why we obtain a spanning
> forest, as
> > > Alpar wrote.
> >
> > So if you have a digraph with n nodes, then the algorithm
> extends it to
> > a digraph with n+1 nodes and operates on it with spanning
> trees (that
> > have n arcs). If you restrict these trees into the original
> arcs, then
> > you may get a forest, not a tree, even if your original
> digraph is
> > connected. (Some artificial arcs may remain in the basis at
> the end.)
> >
> > These internal data are not public, so you have to modify
> the
> > network_simplex.h file. E.g. you can paste the following
> lines at the
> > end of the start() function:
> >
> > int basic1 = 0;
> > for (int j = 0; j != _arc_num; j++) {
> > if (_state[j] == STATE_TREE) basic1++;
> > }
> > int basic2 = basic1;
> > for (int j = _arc_num; j != _all_arc_num; j++) {
> > if (_state[j] == STATE_TREE) basic2++;
> > }
> > std::cout << "Number of nodes: " << countNodes(_graph)
> << std::endl;
> > std::cout << "Number of basic arcs in the original
> graph: "
> > << basic1 << std::endl;
> > std::cout << "Number of basic arcs in the extended
> graph: "
> > << basic2 << std::endl;
> >
> > The results for your network are the following:
> >
> > Number of nodes: 1000
> > Number of basic arcs in the original graph: 995
> > Number of basic arcs in the extended graph: 1000
> >
> > If you do need a spanning tree, i.e. n-1 basic arcs in the
> original
> > digraph (supposing it is weakly connected), then you can
> extend the
> > obtained forest _arbitrarily_ to a spanning tree.
> >
> > I hope, I could made it clear.
> >
> > Best regards,
> > Peter
> >
> >
> > 2010.03.09. 2:45 keltezéssel, Matthew Galati írta:
> > > FYI - I tried updating to trunk version of
> network_simplex.h. I am now
> > > getting 995 basics at the end.
> > >
> > > ====================
> > >
> > > Hi - I have a new example of where the number of
> STATE_TREE vars is not what
> > >
> > >
> > > I had expected.
> > >
> > > The number of nodes=1000, the number of basics = 987 at
> the end of
> > > optimization. I checked and the graph is connected. Any
> ideas?
> > >
> > > The data is
> here:http://coral.ie.lehigh.edu/~magh/tmp/net.dimacs2
> <http://coral.ie.lehigh.edu/%7Emagh/tmp/net.dimacs2>
> > >
> > >
> > >
> > > Thanks,
> > > Matt
> > >
> > >
> >
>
> > _______________________________________________
> > Lemon-user mailing list
> > Lemon-user at lemon.cs.elte.hu
> > http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>
>
More information about the Lemon-user
mailing list