Re: [igraph] problem about mincut

[Gábor Csárdi]

No, I cannot supply such a function. The minimum cut of a graph is
well defined, and sometimes happens to be unbalanced. I don't think
that igraph has what you are looking for.

Gabor

On Tue, Nov 11, 2014 at 10:05 AM, Jeffery <address@hidden> wrote:
> Gábor Csárdi
>       About the problem of mincut, I debug my code and find it's my fault.
> igraph_vector_t uses
> double type defaultly, but I use long int to store vector id. The error
> happens in such code:
>
> vector<long int> p_VecId;
> vector<long int> p_VecID2;
> igraph_vector_t p_Par2;
> ……
> p_VecID2.push_back( (*p_VecId)[VECTOR(p_Par2)[i]] );
>
> When I use the macor (VECTOR(name)[i]) to get a vector id from
> igraph_vector_t and push
> it to a long int vector, the double data is not converted to long int type
> correctly. Actually p_VecID2
> is pushed many zeres instead.
> It is resolved by doing data type convertion as
> p_VecID2.push_back( (*p_VecId)[(long int)(VECTOR(p_Par2)[i])] );
>
> As last email mentioned, I need do balanced mincut partition, namely the
> size of the first part
> is similar to or the same to  the second part after mincut partition. For
> example, the undirected graph
> 1--2--3--4--5--6--1 is a circle, the mincut value is 2, but the mincut edge
> set is not just one.
> Among the possible mincut edge sets, the balanced partitions such as
> (1-2,4-5) or (2-3,5-6)
> are accept.
> Could u supply such function?
>
>                                      Guopeng
>
>
>
>
>
>
>
> At 2014-11-05 23:42:01, "Gábor Csárdi" <address@hidden> wrote:
>>Hi, please send a full reproducible example. Gabor
>>
>>On Wed, Nov 5, 2014 at 10:20 AM, Jeffery <address@hidden> wrote:
>>> hello
>>> Recently i am trying to use igraph_mincut to get the min edge cut value
>>> and
>>> parition the graph to two parts.
>>> Although it can get the mincut value correctly, the vertex ids stored in
>>> igraph_vector_t partition and partition2
>>> make no sense becase they are full of zero.
>>> the function is defined as follow:
>>>
>>> int igraph_mincut(const igraph_t *graph,
>>> igraph_real_t *value,
>>> igraph_vector_t *partition,
>>> igraph_vector_t *partition2,
>>> igraph_vector_t *cut,
>>> const igraph_vector_t *capacity);
>>>
>>> I'm sure I have initialized the parameters, such as partition,partition2
>>> and
>>> cut .I debug the mincut function and i find that the lacal variable
>>> mincut_step is zero.
>>> The adjacency list of my test case is follow:
>>>
>>> 0 : 1 2
>>> 1 : 0 4
>>> 2 : 0 5
>>> 4 : 1 7
>>> 5 : 2 8
>>> 7 : 4 9
>>> 8 : 5 10 10
>>> 9 : 7 11
>>> 10 : 8 8 11 12 13
>>> 11 : 9 10 14
>>> 12 : 10 14 15
>>> 13 : 10 15
>>> 14 : 11 12 15
>>> 15 : 12 13 14
>>>
>>> the returned edgecut of igraph_mincut includes the edge 0-1 and 1-4, I
>>> accept. The first part after partition should only contain the vertex 1
>>> while
>>> the second part should include the other vertexs. However they are full
>>> of
>>> zero.
>>> So have u faced a similar situation ? How do i resolve it?
>>>
>>> p.s sometimes, the mincut of a graph is not unique and i want the
>>> function
>>> to do balanced partition, namely the vertex num of the first part is
>>> roughly
>>> equal to that of the second part. Could such function can be implemented
>>> in
>>> igraph_mincut?
>>>
>>> Thanks a lot.
>>>
>>>                           Guopeng.
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> address@hidden
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>
>>_______________________________________________
>>igraph-help mailing list
>>address@hidden
>>https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>