Graph Partitioning Using Balanced Mincut

From CLAIRlib

Jump to: navigation, search

In this tutorial, you will use a Balanced Mincut algorithm to partition a graph into two balanced partitions.

Contents

Network

For the purpose of this tutorial, we will use the following example graph (shown in edgelist format) 

graph.el

1 2 2
1 5 3
5 2 2
5 6 3
2 6 2
2 3 3
6 7 1
3 7 2
3 4 4
7 4 2
7 8 3
4 8 2

Read the network

Start by reading the network from the file and creating a Clair::Network instance 

use Clair::Network::Reader::Edgelist;
my $reader = new Clair::Network::Reader::Edgelist();
my $net = $reader->read_network("graph.el");

Create Clair::Network::Mincut Instance

Then, create an instance of Clair::Network::Mincut 

use Clair::Network::Mincut;
my $mincut = new air::Network::Mincut($net);

Run the algorithm

Now, you can simply run the partitioning algorithm using 

my ($a,$b,$w) = $mincut->mincut();

This will return three values,

  • $a: A reference to an array containing the nodes of the first partition
  • $b: A reference to an array containing the nodes of the second partition
  • $w: The weight of the computed minimum cut.

You can print the nodes of the two partitions using the Dumper 

use Data::Dumper;
print "Partition A:\n";
print Dumper(@$a);
print "Partition B:\n";
print Dumper(@$b);

Code

The code used in this tutorial is 

#!/usr/bin/perl 
use Clair::Network::Reader::Edgelist;
use Clair::Network::Mincut; 
use Data::Dumper;
 
my $reader = new Clair::Network::Reader::Edgelist();
my $net = $reader->read_network("graph.el");
my $mincut = new air::Network::Mincut($net);
my ($a,$b,$w) = $mincut->mincut();
print "Partition A:\n";
print Dumper(@$a);
print "Partition B:\n";
print Dumper(@$b);

Results

The output after running the code should be something like 

Partition A:
$VAR1 = '4';
$VAR2 = '3';
$VAR3 = '7';
$VAR4 = '8';

Partition B:
$VAR1 = '6';
$VAR2 = '1';
$VAR3 = '5';
$VAR4 = '2';
Retrieved from "http://www.clairlib.org/index.php/Graph_Partitioning_Using_Balanced_Mincut"