title: Karger's Algorithm
body: <p>I'm trying to implement the min-cut Karger's algorithm in Java. For this, I created a Graph class which stores a SortedMap, with an integer index as key and a Vertex object as value, and an ArrayList of Edge objects. Edges stores the index of its incident vertices. Than I merge the vertices of some random edge until the number of vertices reach 2. I repeat this steps a safe number of times. Curiously, in my output I get 2x the number of crossing edges. I mean, if the right answer is 10, after execute n times the algorithm (for n sufficient large), the min of these execution results is 20, what makes me believe the implementation is almost correct.
     This is the relevant part of code:</p>
  
  <pre><code>    void mergeVertex(int iV, int iW) {
  
      for (int i = 0; i &lt; edges.size(); i++) {
          Edge e = edges.get(i);
          if (e.contains(iW)) {
              if (e.contains(iV)) {
                  edges.remove(i);
                  i--;
              } else {
                  e.replace(iW, iV);
              }
          }
      }
  
      vertices.remove(iW);
  }
  
  public int kargerContraction(){
  
      Graph copy = new Graph(this);
      Random r = new Random();
      while(copy.getVertices().size() &gt; 2){
          int i = r.nextInt(copy.getEdges().size());
          Edge e = copy.getEdges().get(i);
          copy.mergeVertex(e.getVertices()[0], e.getVertices()[1]);
      }
  
      return copy.getEdges().size()/2;
  }
  </code></pre>