Re: [igraph] minimum cut; undirected graph in R

[Vincent Matossian]

 Quick follow-up on returning the 'cut' in the mincut function, I did not find an R interface to the C function that returns the actual edges cut, did I miss it?

I patched together a function to add to 
rinterface.c, but much of writing R extensions is cryptic to me that it will need double checking, sorry...it appears to work though.

SEXP R_igraph_mincut_edges(SEXP graph, SEXP pcapacity) {
  
  igraph_t g;
  igraph_vector_t capacity;
  igraph_integer_t res;
  igraph_vector_t partition, partition2;
  igraph_vector_t cut;
  SEXP result,names;
  
  IGRAPH_VECTOR_INIT_FINALLY(&cut, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&partition, 0);
  IGRAPH_VECTOR_INIT_FINALLY(&partition2, 0);
  R_igraph_before();
  
  R_SEXP_to_igraph(graph, &g);
  R_SEXP_to_vector(pcapacity, &capacity);

  igraph_mincut(&g, &res, &partition, 
              &partition2, &cut, &capacity);

  PROTECT(result=NEW_LIST(2));
  PROTECT(names=NEW_CHARACTER(2));
  SET_VECTOR_ELT(result, 0, NEW_NUMERIC(1));
  SET_VECTOR_ELT(result, 1, NEW_NUMERIC(igraph_vector_size(&cut)));
  SET_STRING_ELT(names, 0, CREATE_STRING_VECTOR("res"));
  SET_STRING_ELT(names, 1, CREATE_STRING_VECTOR("cut"));
  SET_NAMES(result, names);
  REAL(VECTOR_ELT(result, 0))[0]=res;
  igraph_vector_copy_to(&cut, REAL(VECTOR_ELT(result, 1)));

  igraph_vector_destroy(&cut);
  igraph_vector_destroy(&partition);
  igraph_vector_destroy(&partition2);
  IGRAPH_FINALLY_CLEAN(3);

  R_igraph_after();
  UNPROTECT(2);
  return result;
}

The corresponding function in flow.R I called graph.mincut.edgesis a simplified version of graph.mincut (into which it could be integrated actually) :

graph.mincut.edges <- function(graph, capacity=NULL){
  if (!is.igraph(graph)) {
    stop("Not a graph object")
  }
  if (is.null(capacity)) {
    if ("capacity" %in% list.edge.attributes(graph)) {
      capacity <- E(graph)$capacity
    } else {
      stop("capacity argument is not given and no `capacity' attribute")
    }
  }
  capacity <- as.numeric(capacity)

  .Call("R_igraph_mincut_edges", graph, capacity, PACKAGE="igraph")
}

Thanks again,

Cheers,

 Vincent

On 4/1/07, gregory benison <address@hidden > wrote:

>
> 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?
>

Yes, that's great - thanks for putting it in!

Greg

======================
Gregory Benison
Oregon State University
(541)-737-1876
gbenison at gmail dot com
======================


_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help