Re: [igraph] minimum cut; undirected graph

[Gabor Csardi]

Greg, thanks, this is really great. You're right, it is easy to 
calculate the cut by storing the merges. Actually i chose another
way, i just store the merges in a vector and the place of the minimum
cut, ie. in which step it happened and then after we have the minimum cut
it is quite easy to replay the stored merge history, etc.

So i've submitted the igraph_mincut function to the repository,
the prototype looks like this: 

int igraph_mincut(const igraph_t *graph,
                  igraph_integer_t *value,
                  igraph_vector_t *partition,
                  igraph_vector_t *partition2,
                  igraph_vector_t *cut,
                  const igraph_vector_t *capacity);

partition and partition2 are the vertex ids of the two partitions
and cut contains the edge ids of the edges in the cut. These are only
calculated if they're not NULL, so it is possible to calculate 'cut' only.
(Of course this function does not (yet) work for directed graphs.)

Is this ok?

Bests, and thanks again,
Gabor

On Sat, Mar 31, 2007 at 01:21:03PM -0700, gregory benison wrote:
> >
> >If you check the paper and have some ideas on how to add the min-cut
> >calculation, that would help.
> >
> 
> Since the algorithm is based on merging nodes, and then finding the
> minimum cut by cutting off just one of these (composite) nodes, I
> think the minimum cut can be found by arranging to remember which
> nodes have been merged.  The attached file is the example from the
> Stoer and Wagner paper.
> 
> Greg
> 
[...]

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK