mincut doesn't handle multiple components

[Donald Ephraim Curtis]

i realize that min-cut doesn't make sense on graphs with multiple components, but there should be some mechanism for erroring when this is the case. for example, the following code in python.

--

import igraph

g = igraph.Graph()

g.add_vertices(2)
g.add_edges([(0,1)])

print len(g.components())
print g.mincut([1000])

--

Outputs the following:

2
Graph cut (1 edges, 1 vs 2 vertices, value=0.0000)
>>>

I was modifying a graph by deleting some vertices (I thought my code would not create multiple components) and so i ran mincut and took me forever to figure out this weirdness. It's a bug in the sense that the output of the function doesn't make any sense. Better to return an error as opposed to continuing with invalid data.

[Gábor Csárdi (gabor.csardi)]

Does it make sense to return an empty edge set?

[Donald Ephraim Curtis (milkypostman)]

I think thats a solution. But more detailed,

If there are multiple components, lets say A, B, C for example, then the algorithm should return two partitions,

[A], [B,C]

and an empty edgeset with cut value of 0.

On Jun 16, 2011, at 16:21, Gábor Csárdi wrote:

> Does it make sense to return an empty edge set?
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/798432
>
> Title:
> mincut doesn't handle multiple components
>
> Status in The igraph library:
> Confirmed
>
> Bug description:
> i realize that min-cut doesn't make sense on graphs with multiple
> components, but there should be some mechanism for erroring when this
> is the case. for example, the following code in python.
>
> --
>
> import igraph
>
> g = igraph.Graph()
>
> g.add_vertices(2)
> g.add_edges([(0,1)])
>
> print len(g.components())
> print g.mincut([1000])
>
> --
>
> Outputs the following:
>
> 2
> Graph cut (1 edges, 1 vs 2 vertices, value=0.0000)
>>>>
>
> I was modifying a graph by deleting some vertices (I thought my code
> would not create multiple components) and so i ran mincut and took me
> forever to figure out this weirdness. It's a bug in the sense that
> the output of the function doesn't make any sense. Better to return
> an error as opposed to continuing with invalid data.
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/igraph/+bug/798432/+subscriptions

[Gábor Csárdi (gabor.csardi)]

Tamás, are you working on this? If not I can finish it....

[Gábor Csárdi (gabor.csardi)]

Actually, it was very easy, so I did it quickly, in revision #2837 (0.6-main).

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/215