function kargerStein() {
    var _this$byGroup = this.byGroup(),
        nodes = _this$byGroup.nodes,
        edges = _this$byGroup.edges;

    edges.unmergeBy(function (edge) {
      return edge.isLoop();
    });
    var numNodes = nodes.length;
    var numEdges = edges.length;
    var numIter = Math.ceil(Math.pow(Math.log(numNodes) / Math.LN2, 2));
    var stopSize = Math.floor(numNodes / sqrt2);

    if (numNodes < 2) {
      error('At least 2 nodes are required for Karger-Stein algorithm');
      return undefined;
    } // Now store edge destination as indexes
    // Format for each edge (edge index, source node index, target node index)


    var edgeIndexes = [];

    for (var i = 0; i < numEdges; i++) {
      var e = edges[i];
      edgeIndexes.push([i, nodes.indexOf(e.source()), nodes.indexOf(e.target())]);
    } // We will store the best cut found here


    var minCutSize = Infinity;
    var minCutEdgeIndexes = [];
    var minCutNodeMap = new Array(numNodes); // Initial meta node partition

    var metaNodeMap = new Array(numNodes);
    var metaNodeMap2 = new Array(numNodes);

    var copyNodesMap = function copyNodesMap(from, to) {
      for (var _i3 = 0; _i3 < numNodes; _i3++) {
        to[_i3] = from[_i3];
      }
    }; // Main loop


    for (var iter = 0; iter <= numIter; iter++) {
      // Reset meta node partition
      for (var _i4 = 0; _i4 < numNodes; _i4++) {
        metaNodeMap[_i4] = _i4;
      } // Contract until stop point (stopSize nodes)


      var edgesState = contractUntil(metaNodeMap, edgeIndexes.slice(), numNodes, stopSize);
      var edgesState2 = edgesState.slice(); // copy
      // Create a copy of the colapsed nodes state

      copyNodesMap(metaNodeMap, metaNodeMap2); // Run 2 iterations starting in the stop state

      var res1 = contractUntil(metaNodeMap, edgesState, stopSize, 2);
      var res2 = contractUntil(metaNodeMap2, edgesState2, stopSize, 2); // Is any of the 2 results the best cut so far?

      if (res1.length <= res2.length && res1.length < minCutSize) {
        minCutSize = res1.length;
        minCutEdgeIndexes = res1;
        copyNodesMap(metaNodeMap, minCutNodeMap);
      } else if (res2.length <= res1.length && res2.length < minCutSize) {
        minCutSize = res2.length;
        minCutEdgeIndexes = res2;
        copyNodesMap(metaNodeMap2, minCutNodeMap);
      }
    } // end of main loop
    // Construct result


    var cut = this.spawn(minCutEdgeIndexes.map(function (e) {
      return edges[e[0]];
    }));
    var partition1 = this.spawn();
    var partition2 = this.spawn(); // traverse metaNodeMap for best cut

    var witnessNodePartition = minCutNodeMap[0];

    for (var _i5 = 0; _i5 < minCutNodeMap.length; _i5++) {
      var partitionId = minCutNodeMap[_i5];
      var node = nodes[_i5];

      if (partitionId === witnessNodePartition) {
        partition1.merge(node);
      } else {
        partition2.merge(node);
      }
    }

    var ret = {
      cut: cut,
      partition1: partition1,
      partition2: partition2
    };
    return ret;
  }
function kargerStein() {
    var _this$byGroup = this.byGroup(),
        nodes = _this$byGroup.nodes,
        edges = _this$byGroup.edges;

    edges.unmergeBy(function (edge) {
      return edge.isLoop();
    });
    var numNodes = nodes.length;
    var numEdges = edges.length;
    var numIter = Math.ceil(Math.pow(Math.log(numNodes) / Math.LN2, 2));
    var stopSize = Math.floor(numNodes / sqrt2);

    if (numNodes < 2) {
      error('At least 2 nodes are required for Karger-Stein algorithm');
      return undefined;
    } // Now store edge destination as indexes
    // Format for each edge (edge index, source node index, target node index)


    var edgeIndexes = [];

    for (var i = 0; i < numEdges; i++) {
      var e = edges[i];
      edgeIndexes.push([i, nodes.indexOf(e.source()), nodes.indexOf(e.target())]);
    } // We will store the best cut found here


    var minCutSize = Infinity;
    var minCutEdgeIndexes = [];
    var minCutNodeMap = new Array(numNodes); // Initial meta node partition

    var metaNodeMap = new Array(numNodes);
    var metaNodeMap2 = new Array(numNodes);

    var copyNodesMap = function copyNodesMap(from, to) {
      for (var _i3 = 0; _i3 < numNodes; _i3++) {
        to[_i3] = from[_i3];
      }
    }; // Main loop


    for (var iter = 0; iter <= numIter; iter++) {
      // Reset meta node partition
      for (var _i4 = 0; _i4 < numNodes; _i4++) {
        metaNodeMap[_i4] = _i4;
      } // Contract until stop point (stopSize nodes)


      var edgesState = contractUntil(metaNodeMap, edgeIndexes.slice(), numNodes, stopSize);
      var edgesState2 = edgesState.slice(); // copy
      // Create a copy of the colapsed nodes state

      copyNodesMap(metaNodeMap, metaNodeMap2); // Run 2 iterations starting in the stop state

      var res1 = contractUntil(metaNodeMap, edgesState, stopSize, 2);
      var res2 = contractUntil(metaNodeMap2, edgesState2, stopSize, 2); // Is any of the 2 results the best cut so far?

      if (res1.length <= res2.length && res1.length < minCutSize) {
        minCutSize = res1.length;
        minCutEdgeIndexes = res1;
        copyNodesMap(metaNodeMap, minCutNodeMap);
      } else if (res2.length <= res1.length && res2.length < minCutSize) {
        minCutSize = res2.length;
        minCutEdgeIndexes = res2;
        copyNodesMap(metaNodeMap2, minCutNodeMap);
      }
    } // end of main loop
    // Construct result


    var cut = this.spawn(minCutEdgeIndexes.map(function (e) {
      return edges[e[0]];
    }));
    var partition1 = this.spawn();
    var partition2 = this.spawn(); // traverse metaNodeMap for best cut

    var witnessNodePartition = minCutNodeMap[0];

    for (var _i5 = 0; _i5 < minCutNodeMap.length; _i5++) {
      var partitionId = minCutNodeMap[_i5];
      var node = nodes[_i5];

      if (partitionId === witnessNodePartition) {
        partition1.merge(node);
      } else {
        partition2.merge(node);
      }
    }

    var ret = {
      cut: cut,
      partition1: partition1,
      partition2: partition2
    };
    return ret;
  }
function kargerStein ( ) { var _this$byGroup = this . byGroup ( ) , nodes = _this$byGroup . nodes , edges = _this$byGroup . edges ; edges . unmergeBy ( function ( edge ) { return edge . isLoop ( ) ; } ) ; var numNodes = nodes . length ; var numEdges = edges . length ; var numIter = Math . ceil ( Math . pow ( Math . log ( numNodes ) / Math . LN2 , 2 ) ) ; var stopSize = Math . floor ( numNodes / sqrt2 ) ; if ( numNodes < 2 ) { error ( 'At least 2 nodes are required for Karger-Stein algorithm' ) ; return undefined ; } // Now store edge destination as indexes // Format for each edge (edge index, source node index, target node index) var edgeIndexes = [ ] ; for ( var i = 0 ; i < numEdges ; i ++ ) { var e = edges [ i ] ; edgeIndexes . push ( [ i , nodes . indexOf ( e . source ( ) ) , nodes . indexOf ( e . target ( ) ) ] ) ; } // We will store the best cut found here var minCutSize = Infinity ; var minCutEdgeIndexes = [ ] ; var minCutNodeMap = new Array ( numNodes ) ; // Initial meta node partition var metaNodeMap = new Array ( numNodes ) ; var metaNodeMap2 = new Array ( numNodes ) ; var copyNodesMap = function copyNodesMap ( from , to ) { for ( var _i3 = 0 ; _i3 < numNodes ; _i3 ++ ) { to [ _i3 ] = from [ _i3 ] ; } } ; // Main loop for ( var iter = 0 ; iter <= numIter ; iter ++ ) { // Reset meta node partition for ( var _i4 = 0 ; _i4 < numNodes ; _i4 ++ ) { metaNodeMap [ _i4 ] = _i4 ; } // Contract until stop point (stopSize nodes) var edgesState = contractUntil ( metaNodeMap , edgeIndexes . slice ( ) , numNodes , stopSize ) ; var edgesState2 = edgesState . slice ( ) ; // copy // Create a copy of the colapsed nodes state copyNodesMap ( metaNodeMap , metaNodeMap2 ) ; // Run 2 iterations starting in the stop state var res1 = contractUntil ( metaNodeMap , edgesState , stopSize , 2 ) ; var res2 = contractUntil ( metaNodeMap2 , edgesState2 , stopSize , 2 ) ; // Is any of the 2 results the best cut so far? if ( res1 . length <= res2 . length && res1 . length < minCutSize ) { minCutSize = res1 . length ; minCutEdgeIndexes = res1 ; copyNodesMap ( metaNodeMap , minCutNodeMap ) ; } else if ( res2 . length <= res1 . length && res2 . length < minCutSize ) { minCutSize = res2 . length ; minCutEdgeIndexes = res2 ; copyNodesMap ( metaNodeMap2 , minCutNodeMap ) ; } } // end of main loop // Construct result var cut = this . spawn ( minCutEdgeIndexes . map ( function ( e ) { return edges [ e [ 0 ] ] ; } ) ) ; var partition1 = this . spawn ( ) ; var partition2 = this . spawn ( ) ; // traverse metaNodeMap for best cut var witnessNodePartition = minCutNodeMap [ 0 ] ; for ( var _i5 = 0 ; _i5 < minCutNodeMap . length ; _i5 ++ ) { var partitionId = minCutNodeMap [ _i5 ] ; var node = nodes [ _i5 ] ; if ( partitionId === witnessNodePartition ) { partition1 . merge ( node ) ; } else { partition2 . merge ( node ) ; } } var ret = { cut : cut , partition1 : partition1 , partition2 : partition2 } ; return ret ; }
Computes the minimum cut of an undirected graph Returns the correct answer with high probability
Computes the minimum cut of an undirected graph Returns the correct answer with high probability
Karger - Stein algorithm