CODEWITHSUNDEEP
algorithmrandomgraph
Ole Gooner
Ole Gooner

Reputation: 567

Random contraction algorithm for finding Min Cuts in a graph

Okay so here's my algorithm for finding a Cut in a graph (I'm not talking about a min cut here)

Say we're given an adjacency list of a non-directed graph.

  1. Choose any vertice on the graph (let this be denoted by pivot)
  2. Choose any other vertice on the graph (randomly). (denote this by x)
  3. If the two vertices have an edge between them, then remove that edge from the graph. And dump all the vertices that x is connected to, onto pivot. (if not then go back to Step 2.
  4. If any other vertices were connected to x, then change the adjacency list so that now x is replaced by pivot. Ie they're connected to Pivot.
  5. If number of vertices is greater than 2 (go back to step 2)
  6. If equal to 2. Just count number of vertices present in adjacency list of either of the 2 points. This will give the cut

My question is, is this algorithm correct?

Upvotes: 4

Views: 5560

Answers (3)

dragonfly02
dragonfly02

Reputation: 3679

Agree that you should definitely remove self-loop. Also another point I want to add is after you randomly choose the first vertice, you don't have to randomly choose another node until you have one that is connected to the first node, you can simply choose from the ones that are connected to the first vertice because you know how many nodes are the first chosen one connects to. So a second random selection within a smaller range. This is just effectively randomly choosing an edge (determined by two nodes/vertices). I have some c# code implementing krager's algorithm you can play around. It's not the most efficient code (especially a more efficient data structure can be used) as I tested it on a 200 nodes graph, for 10000 iterations it takes about 30 seconds to run.

using System;
using System.Collections.Generic;
using System.Linq;

namespace MinCut
{
    internal struct Graph
    {
        public int N { get; private set; }
        public readonly List<int> Connections;
        public Graph(int n) : this()
        {
            N = n;
            Connections = new List<int>();
        }

    public override bool Equals(object obj)
    {
        return Equals((Graph)obj);
    }

    public override int GetHashCode()
    {
        return base.GetHashCode();
    }

    private bool Equals(Graph g)
    {
        return N == g.N;
    }
}

internal sealed class GraphContraction
{
    public static void Run(IList<Graph> graphs, int i)
    {
        var liveGraphs = graphs.Count;
        if (i >= liveGraphs)
        {
            throw new Exception("Wrong random index generation; index cannot be larger than the number of nodes");
        }
        var leftV = graphs[i];

        var r = new Random();
        var index = r.Next(0, leftV.Connections.Count);
        var rightV = graphs.Where(x=>x.N == leftV.Connections[index]).Single();

        foreach (var v in graphs.Where(x => !x.Equals(leftV) && x.Connections.Contains(leftV.N))) 
        {
            v.Connections.RemoveAll(x => x == leftV.N);
        }
        foreach (var c in leftV.Connections)
        {
            if (c != rightV.N)
            {
                rightV.Connections.Add(c);
                int c1 = c;
                graphs.Where(x=> x.N == c1).First().Connections.Add(rightV.N);
            }
        }
        graphs.Remove(leftV);
    }
}

}

Upvotes: -1

Stupi
Stupi

Reputation: 19

I'll only change your randomization.

After choosing first vertex, choose another from his adjacency list. Now you are sure that two vertices have the edge between them. Next step is finding the vertex from adjancecy list.

Upvotes: 1

john_science
john_science

Reputation: 6551

That is a nice explanation of Krager's Min-Cut Algorithm for undirected graphs.

I think there might one detail you missed. Or perhaps I just mis-read your description.

You want to remove all self-loops.

For instance, after you remove a vertex and run through your algorithm, Vertex A may now have an edge that goes from Vertex A to Vertex A. This is called a self-loop. And they are generated frequently in process of contracting two vertices. As a first step, you can simply check the whole graph for self-loops, though there are some more sophisticated approaches.

Does that make sense?

Upvotes: 1

Related Questions