igraph-help
[Top][All Lists]

Re: [igraph] Minimal edge cut sets in undirected graphs

 From: Louis Aslett Subject: Re: [igraph] Minimal edge cut sets in undirected graphs Date: Tue, 11 Sep 2012 13:32:47 +0100

```Thanks for the swift reply.  Unfortunately it is the collection of all
minimal cut sets which I need.  Not to worry, I just wanted to avoid
reinventing the wheel if it had been done.  I am thinking I'll
implement Abel and Bicker 1982 ("Determination of All Minimal Cut-Sets
between a Vertex Pair in an Undirected Graph", IEEE Trans.
Reliability) or something similar.  If you know of another
particularly good algorithm which I should be using instead please let
me know!

All the best,

Louis

On 11 September 2012 08:25, Tamás Nepusz <address@hidden> wrote:
>
> Hi Louis,
>
> If you only need a single solution, use graph.maxflow to find a maximum
> flow with equal edge capacities between your two given vertices. The \$cut
> element of the result object will give you the edges to remove. E.g.:
>
> g <- graph.full(5) + graph.full(5)
> g[1,6] <- 1
> graph.maxflow(g, 2, 7)\$cut
>
> Currently we have no function for enumerating all the possible maximum
> flows (equivalently, all the minimum edge cut sets) in undirected graphs.
>
> Best,--
> T.
>
>
> On Monday, 10 September 2012 at 18:25, Louis Aslett wrote:
>
> > Hi Gabor,
> >
> > Thanks for the igraph R package, I continue to enjoy using it a lot
> > lately! I've one problem at the moment which involves computing the
> > collection of minimal edge cut sets between two vertices for an undirected
> > graph. The R function stMincuts does the same thing for directed graphs. Is
> > there any means of using igraph to do this in the undirected case?
> >
> > All the best,
> >
> > Louis
> >
> > _______________________________________________
> > igraph-help mailing list
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
>
> _______________________________________________
> igraph-help mailing list