Graphs and Minimum Cuts(Karger's Min-Cut Algorithm)

Graphs

Two ingredients

1. vertices (nodes) v

2. edges(undirected or directed)

Examples: road networks, the web, social networks

The minimum Cut problem

Input: undirected graph G = (V, E) (parallel edges allowed)

Goal: compute a cut with fewest number of Crossing edges (a min cut)

Sparse vs. Dense Graphs

let n = # of vertices, m = # of edges

In most applications, m is Omega(n) and O(n^2)

In a "sparse graph", m is O(n) or close to it

In a "dense graph", m is closer to Theta(n^2)

Two ways to represent a Graph

1. The Adjacency Matrix

2. The Adjacency List

Which one is better? Depends on graph density and operation needed.

Random Contraction Algorithm

while there are more than 2 vertices:

-pick a remaining edge(u, v) uniformly at random

-merge(or "contract") u and v into a single vertex

-remove self-loops

return cut represented by final 2 vertices

Karger's Min-Cut Algorithm -------Random Contraction Algorithm(Python code):

import random

import copy

import time

def contract(ver, e):

    while len(ver) > 2: #create a new graph every time (not efficient)

        ind = random.randrange(0, len(e))

        [u, v] = e.pop(ind)   #pick a edge randomly

        ver.remove(v)    #remove v from vertices

        newEdge = list()

        for i in range(len(e)):

            if e[i][0] == v: e[i][0] = u

            elif e[i][1] == v: e[i][1] = u

            if e[i][0] != e[i][1]: newEdge.append(e[i])   # remove self-loops

        e = newEdge

    return(len(e))  #return the number of the remained edges 

if __name__ == '__main__':

    f = open('kargerMinCut.txt')

    _f = list(f)

    edges = list()          #initialize vertices and edges

    vertices = list()

    for i in range(len(_f)):     #got 2517 different edges

        s = _f[i].split()

        vertices.append(int(s[0]))

        for j in range(1, len(s)):

            if [int(s[j]), int(s[0])] not in edges:

                edges.append([int(s[0]), int(s[j])])  

    result = list()

    starttime = time.clock()

    for i in range(2000):  #we take n^2logn times so that the Pr(allfail) <= 1/n where n is the number of vertics

        v = copy.deepcopy(vertices)   #notice: deepcopy

        e = copy.deepcopy(edges)

        r = contract(v, e)

        result.append(r)

    endtime = time.clock()

    #print(result)

    print(min(result))

    print(endtime - starttime)

巴特西

Graphs and Minimum Cuts(Karger's Min-Cut Algorithm)

最新文章

热门文章