It seems there is no Matlab implementation of the Tarjan algorithm. However, I managed to use a java library (jar file) inside matlab which can produce the 3-connected components of a graph. This library is jBPT which implements the SPQR trees and can give the 3-connected components with O(m) time. Here is the link to that library: http://code.google.com/p/jbpt/downloads/list.
Download the last one (at the moment it is jbpt-0.2.363.jar). There is a class called TCTree which is in charge of generating those components. First add the jar file into your matlab classpath by using below code:
javaaddpath('dir/jbpt-0.2.363.jar')
in above replace dir with the full path of the jar file. For me to make it work I have written a java class which accepts a matlba matrix (in[][] in java) as the adjacency matrix of the graph and the result is an ArrayList of components in which each component is itself and ArrayList of integers (labels of vertices in that 3-connected component). Here is TriComps java class:
package tricomponents;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import org.jbpt.algo.tree.tctree.TCSkeleton;
import org.jbpt.algo.tree.tctree.TCTree;
import org.jbpt.algo.tree.tctree.TCTreeNode;
import org.jbpt.algo.tree.tctree.TCType;
import org.jbpt.graph.Edge;
import org.jbpt.graph.Graph;
import org.jbpt.hypergraph.abs.Vertex;
public class TriComps {
public ArrayList getTricomps(int[][] ad){
int n = ad.length;
Graph graph = new Graph();
List<Vertex> vertices = new ArrayList<Vertex>();
for (int i = 0; i < ad.length; i++){
vertices.add(new Vertex(Integer.valueOf(i + 1).toString()));
}
graph.addVertices(vertices);
for (int i = 0; i < ad.length - 1; i++) {
for (int j = i + 1; j < ad[i].length; j++) {
if (ad[i][j] == 1)
graph.addEdge(vertices.get(i), vertices.get(j));
}
}
TCTree tcTree = new TCTree(graph);
Collection<TCTreeNode> treenodes = tcTree.getTCTreeNodes();
ArrayList components = new ArrayList<>();
if (treenodes == null || treenodes.size() == 0){
ArrayList cmp = new ArrayList<>();
for (Vertex vertex : vertices)
cmp.add(Integer.valueOf(vertex.toString()));
components.add(cmp);
}
for (TCTreeNode tcTreeNode : treenodes) {
TCSkeleton sk = tcTreeNode.getSkeleton();
if (tcTreeNode.getType() == TCType.RIGID || tcTreeNode.getType()
== TCType.POLYGON){
ArrayList cmp = new ArrayList<>();
for (Vertex vertex : ((Collection<Vertex>)sk.getVertices()))
cmp.add(Integer.valueOf(vertex.toString()));
components.add(cmp);
}
}
return components;
}
}
Now it is straight forward to call this class in matlab. I first get the biconnected components of the graph using matlab_bgl library (which is available on internet). Then I produce 3-connected components for each of biconnected components. The result is a cell array of components where each component is a vector of vertices. Here is the function doing all that work:
function [ comps ] = triconnected_components(ad)
%Using an external java library computes the triconnected components of a
%graph whose adjacency matrix is ad.
%Developed by Alireza
% javaaddpath('trcomps.jar');
import tricomponents.*;
if exist('matlab_bgl', 'dir') ~= 7
addpath(genpath('../../../LocalizationByMerging/src/matlab_bgl'))
end
[~,cmpad] = biconnected_components(sparse(ad));
cmpad = full(cmpad);
bisz = max(max(cmpad));
bicomps = cell(1, bisz);
for i = 1 : size(cmpad, 1)
cmpids = cmpad(i, cmpad(i,:) > 0);
if isempty(cmpids)
continue;
end
for idx = unique(cmpids)
bicomps{idx} = union(bicomps{idx}, i);
end
end
comps = cell(1, bisz);
trn = 1;
for k = 1 : bisz
if size(bicomps{k}, 2) <= 2 %a single edge is neither 2-connected nor globally rigid.
continue;
end
biad = ad(bicomps{k}, bicomps{k});
trc = TriComps;
compsjava = trc.getTricomps(biad);
for i = 0 : compsjava.size - 1
cmp = zeros(1, compsjava.get(i).size);
for j = 0 : compsjava.get(i).size - 1
cmp(j + 1) = compsjava.get(i).get(j);
end
comps{trn} = bicomps{k}(cmp);
trn = trn + 1;
end
end
end
Let me know if you have problem with calling java classes from within Matlab. Remember that the current version of jBPT is compiled in java 1.7 and your matlab must also have the same version of JVM (most times this is the default behavior).
