Re: [Edmonds-alg-users] Implementation improvements

[Vladimir Y. <vol...@cs...>]

Hi Ali,

1. Yes certainly one cannot find branchings faster than one can read
the graph:-) Having O(n log n) algorithm will only improve your
implementation for dense graphs if you read a graph significantly
faster than compute the branchings and I don't know if this is the
case.
2. My implementation of cycle contractions using union-find failed on
your test. I'm now on vacation/conference in Europe for 3 weeks, so it
may take some time till I fix and post it.
3. The purpose of decrementing the edge weight of the edges in a cycle
is only in order to make all the weights equal, so that any
branching/arborescence can be replace by one having a single entry
into the cycle. Hence this least costly edge reduction is completely
unnecessary.
4. The main idea of O(n log n) algorithm is very similar to O(m log
n). The main difference is that in O(m log n) they did not use
Fibonacci heap which was not available then. In O(n log n) paper they
use Fibonacci heap to store sets of edges adjacent to nodes and also
notice that with Fibonacci heap one does not have to delete an item
from one heap in order to move to another, instead a whole tree can be
moved between heaps (nodes) in O(1). Then the only operation taking
log n time would be finding critical edges (computing MIN/MAX of the
heap) and there are at most n of this.
5. Thanks a lot for the examples for sparse graphs. They will realy help.

Best,
Vlad



On Fri, Aug 22, 2008 at 2:35 PM, Ali Tofigh <ali...@gm...> wrote:
> On Tue, Aug 19, 2008 at 07:48, Vladimir Yanovsky <vol...@cs...>
> wrote:
>>
>> Btw, Tarjan decreases the weight of all incoming edges by the
>> difference between the
>> cycle's edge weight and the weight of the cheapest edge in the cycle.
>> Subtracting the
>> weight of the cycle edge from the weights of all edges sharing with it
>> the target should
>> be good as well and will save additional arithmetic operation per
>> edge. By induction, this will
>> not causes any edge weights to become negative as result.
>
> This only works when finding maximum spanning arborescences. It does not
> work for maximum branchings, where the negative edge weights are essential
> for the algorithm to work. (Also, there is nothing that prevents the
> incoming graph from having negative edges in the first place.)
>
The purpose of

>>
>> Moreover,
>> the decrement
>> can be performed when we select a critical edge -not waiting the cycle
>> colapse stage- just decrease all the incoming edges
>> by its weight. The weights of edges on weakly connected components
>> then become zero. This is faster then going
>> through all cycle edges to decrement due to cache locality.
>
> We could do this optimization by treating the case of MSAs and maximum
> branchings separately. But I would rather get the code working for sparse
> graphs first, and do such optimizations later when we've gotten most of the
> bugs out of the way.
>
>> Regarding the O(VlogV) algorithm, it should be faster than O(V^2) even
>> for dense graphs.
>
> But dense graphs can never have better time complexity than O(|V|^2) simply
> because they have O(|V|^2) edges, and you always have to at least read the
> entire input! The time complexity of Tarjan's '86-paper is O(|V| log |V| +
> |E|).
>
>> I'll work
>> on its implementation as we get O(ElogV) ready - it's very similar and
>> the constants in O look low.
>
> If I remember correctly, the algorithm in the '86-paper isn't just a simple
> modification of the older algorithm. It is much more different than simply
> using modified F-heaps to keep track of incoming edges. The core data
> structures used in book-keeping are very different (again, this is just from
> memory). I remember thinking, while reading the '86-paper, that the constant
> in the time complexity may actually be quite large. I don't recall why I
> thought so, perhaps because there was so much book-keeping needed, or
> perhaps because I had read that F-heaps actually are not very fast in
> practice. This, however, is from "Introduction to algorithms" by Cormen et
> al 1989, so that information may be dated.
>
>>
>> Do you have some toy example of creating a sparse graph of V vertices,
>> initially no edges, so that I can add edges
>> myself and have your implementation  run on it? This will help a
>> lot in my understanding of the Boost related staff of the implementation.
>
> I have created an example on how to create a sparse graph using the
> adjacency_list class of BGL and calling edmonds_optimum_branching. It is now
> committed into the subversion repository at sourceforge. You'll find it in
> trunk/doc/examples. Let me know if you have problems compiling the code.
>
> Cheers,
> /Ali
>
>