File Exchange

image thumbnail

Maximal Independent Sets using JGraphT

version 1.0.0.0 (1.2 KB) by Berk Birand
Compute all the maximal independent sets of a given graph using the JGraphT library.

0 Downloads

Updated 24 Mar 2010

View License

This file is essentially a wrapper around the JGraphT library, allowing it to be called from within Matlab on Matgraph graph objects. Since all the processing is done in Java, this is a very quick method for listing the maximal independent sets of a graph.

To use this file, first download the Matgraph library (http://www.ams.jhu.edu/~ers/matgraph/) which allows one to manipulate graph objects in Matlab. Then, you need to get the JGraphT Java library that contains Java algorithms that run on graphs (http://jgrapht.sourceforge.net/). In order to use these Java functions in Matlab, perform the following configuration steps:
Locate the classpath.txt file (its location can be found by typing 'which classpath.txt'.
Add the following line to the end of this file:
/path/jgrapht-0.7.3/lib
/path/jgrapht-0.7.3/build
where path is the location where you copied the JGraphT library.
Restart Matlab.
Type 'which org.matjgraph.MaximalCliques.getMaximalCliques' to make sure the class is loaded.

All you have to do now is put the Jmaximal.m file in a folder called '@graph' (since it will be called on Matgraph graph objects) that is in your path. Here's a sample use:

>> g = graph;
>> cycle(g,5);
>>Jmaximal(g)
ans =

1 1 0 0 0
0 0 1 1 0
1 0 0 0 1
0 1 1 0 0
0 0 0 1 1

As a speed comparison with my other file BKMaximal that does the same thing in Matlab, consider the following results obtained on a graph with 36 vertices and 252 edges:

Using BKMaximal:
Elapsed time is 47.721192 seconds.

Using JMaximal:
Elapsed time is 0.056165 seconds.

Comments and Ratings (1)

Dear Berk,

I tried to use your Jmaximal-function from

http://www.mathworks.com/matlabcentral/fileexchange/27074-maximal-independent-sets-using-jgrapht

but failed. I downloaded the jgrapht-0.7.3.zip from http://jgrapht.sourceforge.net/ and installed it in a subfolder in my MATLAB path.

As described I added the paths

$matlabroot/java/jar/jgrapht-0.7.3/lib
$matlabroot/java/jar/jgrapht-0.7.3/build

in the classpath.txt. Anyhow the path 'build' does not really exists, there is only a 'build.xml' in the /jgrapht-0.7.3/-folder, but I think it is not the same!?!

Then I tried further, but the command

which org.matjgraph.MaximalCliques.getMaximalCliques

fails with

'org.matjgraph.MaximalCliques.getMaximalCliques' not found.

I'm not sure if this is correct, since there is no file called 'matjgraph', but only a file called 'jgraph.jar' in the /jgrapht-0.7.3/lib-folder. On http://www.jgrapht.org/javadoc/ the package is called 'org.jgrapht'. What is correct?

On http://www.jgrapht.org/javadoc/ there is also no class called 'MaximalCliques', but only a class 'BronKerboschCliqueFinder'. In this class there is also no method defined which is called 'getMaximalCliques'. Instead there are two methods called getAllMaximalCliques and getBiggestMaximalCliques.

So if I adopt this different names and try something like:

which org.jgrapht.alg.BronKerboschCliqueFinder.getBiggestMaximalCliques

I still get an error that this is not found.

What am I doing wrong and why can't I use your Jmaximal-function. I running MATLAB 7.4.0.287 (R2007a) with Java 1.5.0_22

best regards, Mathias

MATLAB Release Compatibility
Created with R2008b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.


Learn About Live Editor