[Edmonds-alg-users] Implementation questions

[Ali T. <ali...@gm...>]

This post attempts to answer some questions received about the current
implementation of edmonds-alg (version 1.0).

1) You decrement weights of edges incoming to a vertex while
contracting a cycle by actually accessing each of them and decreasing
the values. Why?  I think this is a great performance hit, especially
for dense graphs.  Tarjan's paper supposed to use union-find DS with
values so that the decrement is O(1) per vertex.

The implementation given in Tarjan's paper assumes the input graph is
sparse and uses a priority queue datastructure to keep track of the
incoming edges of the strongly connected components. Such an
implementation gives a time complexity of O(m log n) where m is the
number of edges and n is the number of vertices. For dense graphs the
time complexity becomes O(n^2 log n). In order to reduce this to
O(n^2), the incoming edges are instead kept sorted by their tails in a
list (as suggested in the same article by Tarjan). Also, for each
vertex v at most one edge whose tail is v is kept in the list, and if
there are several such edges then one with optimal weight is
kept. Therefore, during the merging of the lists the actual weight of
each edge must be known. The time complexity remains the same
irrespective of whether the weights are updated before or during the
merging of the lists.


2) I also could not understand your edge sort (not that it will be
necessary for the sparse implementation as I need either O(nlog n)
from 85', or original Tarjan's O(m log n)), but I'm still curious. (My
C++ is bad so this could explain  my problem).
Why you just don't go through all edges in order of their sources and
put them into buckets corresponding to the destinations - there is a
bucket for every node. This will be linear? Or is this what you are
doing? (May be a newbie question - I use
your work as my tutorial to boost).

Well, I'm using a standard radix sort algorithm to sort the edges. The
time complexity is linear for this algorithm.


3) P.S. Minor comment:
In test.cpp
   if (abs(max_weight) >= numeric_limits<int>::max() / n_vertices ||
       abs(min_weight) >= numeric_limits<int>::max() / n_vertices)
   {
       cerr << "weights too large\n";
       exit(1);
   }
checking min_weight seems not necessary.

Well, the whole thing seems a bit paranoid to me ;), but still... If we
are going to be paranoid, lets be properly paranoid: We're not
checking min_weight, we are checking the absolute value of min_weight
which could, in theory, be greater than the absolute value of max_weight.


4) Do you have a test case or some toy example of your implementation
with Vertex and vertex_idx_t being two different incompatible types?
I'm totally new to Boost and confused between the two. Both are used
to index into arrays. Also you declare a Vertex type but never use it
in the code.

In Boosts Graph Library (BGL) a vertex_descriptor (that I have
typedefed to Vertex) is not required to be an integral type. There
are, however, algorithms that need to treat vertices more or less as
integers. In general, these algorithms require the caller to provide a
property_map that maps the vertices to the integers 0, 1, ...,
n-1. The type of integer returned by the property map is
property_traits<property_map_type>::value_type which I have typedefed to
vertex_idx_t for readability and to save typing.

As for using a Vertex to index into arrays, that is simply a bug. I'd
appreciate it if you could point out where in the code a Vertex is
used to index into an array so that I can fix it.

BGL relies heavily on Boosts property_map concepts, so its worth while
getting acquainted with that section of Boost. If you still need an
example of an implementation where vertex_descriptor is not an
integral type, let me know and I will get to work on it.


5) Also an example of a sparse graph with weights stored
space efficiently (not in an array) on which I can run your algorithm
and test my changes will also help a lot.

Well, this depends a lot on how you would want to store your graphs in
the first place. Again, you need to understand Boosts property map
concepts. But get back to me if you really want an example and I'll
try to come up with something.

Also, if you modify the algorithm with good results, consider sending
a patch and/or a description of the changes and I'll try to
incorporate those into the code. This way other users can also benefit.

Cheers,
/Ali