No BSD License  

Highlights from
MatlabBGL

MatlabBGL

by

 

30 Apr 2006 (Updated )

MatlabBGL provides robust and efficient graph algorithms for Matlab using native data structures.

New features in MatlabBGL version 3.0

New features in MatlabBGL version 3.0

Although MatlabBGL 3.0 was never officially released, here are some of it's key features.

Contents

Better performance

We redid the backend interface to the BGL routines. This optimization gave a considerable performance increase.

test_benchmark on MatlabBGL 2.1

2008-10-07, Version 2.1, Matlab 2007b, boost 1.33.0,
  g++-3.4 (lib), gcc-? (mex)
       airfoil       west    cs-stan    minneso      tapir
large   0.223 s    0.024 s    0.390 s    0.073 s    0.046 s
  med     NaN s    0.955 s      NaN s      NaN s    6.621 s
small     NaN s    0.758 s      NaN s      NaN s      NaN s

test_benchmark on MatlabBGL 3.0

2008-10-07: Version 3.0, Matlab 2007b, boost 1.34.1,
  g++-4.0 (lib), gcc-? (mex)
       airfoil       west    cs-stan    minneso      tapir
large   0.183 s    0.017 s    0.222 s    0.048 s    0.037 s
  med     NaN s    0.593 s      NaN s      NaN s    3.901 s
small     NaN s    0.543 s      NaN s      NaN s      NaN s

 

Graph construction functions

MatlabBGL 2.1 had a few graph construction functions. MatlabBGL 3.0 adds the grid_graph function for line, grid, cube, and hyper-cube graphs

[G xy] = grid_graph(6,5); gplot(G,xy,'.-');

In more dimensions...

[G xyz] = grid_graph(6,5,3);
G = grid_graph(2,2,2,2);
G = grid_graph([3,3,3,3,3]);

 

Targeted search

The graph search algorithms now let you specify a target vertex that will stop the search early if possible.

A = grid_graph(50,50);
tic; d = bfs(A,1,struct()); toc
tic; d = bfs(A,1,struct('target',2)); toc
Elapsed time is 0.001523 seconds.
Elapsed time is 0.000704 seconds.

Also implemented for astar_search, shortest_paths, and dfs.


 

Edge weights

In Matlab, there is no way to create a sparse matrix with a structural non-zero (used for MatlabBGL edges) and a value of 0 (used for MatlabBGL weights). Consequently, it's impossible to run algorithms on graphs where the edge weights are 0.

Consequently, some algorithms now take an 'edge_weight' parameter that allows you to provide a different set of edge weights which allow structural non-zeros and 0 values.

This behavior is a bit complicated, so see the REWEIGHTED_GRAPHS example for more information.


 

Matching algorithms

While maximum cardinality bipartite matching is just a call to max-flow, general graph matching algorithms are not. MatlabBGL 3.0 contains the matching algorithms in Boost 1.34.0.

load('../graphs/matching_example.mat');
m = matching(A);
sum(m>0)/2 % matching cardinality should be 8
ans =

     8


 

New graph statistics

We added a few new statistics functions.

Test for a topological ordering of a graph (only applies to DAGs or directed acyclic graphs)

n = 10; A = sparse(1:n-1, 2:n, 1, n, n); % construct a simple dag
p = topological_order(A);

test_dag(A)
test_dag(cycle_graph(6)) % a cycle is not acyclic!
ans =

     1


ans =

     0

Core numbers can help identify important regions in a graph. MatlabBGL includes weighted and directed core numbers. Also, the algorithms return the removal time of a particular vertex, which gives interesting graph orderings.

% See EXAMPLES/CORE_NUMBERS_EXAMPLE

New algorithms for clustering_coefficients on weighted and directed graphs.

A = clique_graph(6) - cycle_graph(6); % A is a clique - a directed cycle
ccfs = clustering_coefficients(A)
B = sprand(A);
ccfs = clustering_coefficients(B)
C = A|A'; % now it's a full clique again
ccfs = clustering_coefficients(C)
ccfs =

    0.7600
    0.7600
    0.7600
    0.7600
    0.7600
    0.7600


ccfs =

    0.4543
    0.4064
    0.4363
    0.4310
    0.4109
    0.4180


ccfs =

     1
     1
     1
     1
     1
     1


 

Max-flow algorithms

Since Boost added the Kolmogorov max-flow function, we added the full collection of flow algorithms to MatlabBGL.

load('../graphs/max_flow_example.mat');

push_relabel_max_flow(A,1,8)
kolmogorov_max_flow(A,1,8)
edmunds_karp_max_flow(A,1,8)

max_flow(A,1,8,struct('algname','push_relabel'));
max_flow(A,1,8,struct('algname','kolmogorov'));
max_flow(A,1,8,struct('algname','edmunds_karp'));
ans =

     4


ans =

     4


ans =

     4


 

Dominator tree

Dominator trees are relations about presidence in certain types of graphs. These are also called flow-graphs.

load('../graphs/dominator_tree_example.mat');
p = lengauer_tarjan_dominator_tree(A,1);

 

New utility functions

MatlabBGL 3.0 introduces some new utility functions.

The output of a shortest path algorithm is a predecessor matrix. To convert these predecessor relationships to a path, use the path_from_pred function.

[A xy] = grid_graph(6,5); n= size(A,1);
[d dt pred] = bfs(A,1); %
path = path_from_pred(pred,n) % sequence of vertices to upper corner
path =

     1     2     3     4     5     6    12    18    24    30

Let's draw the path

gplot(A,xy,'r.-');
[px,py]=gplot(sparse(path(1:end-1),path(2:end),1,n,n),xy,'-');
hold on; plot(px,py,'-','LineWidth',2); hold off;

We can also create a full shortest path tree using the tree_from_pred function.

T = tree_from_pred(pred);
gplot(A,xy,'r.-');
[px,py]=gplot(T,xy,'-');
hold on; plot(px,py,'-','LineWidth',2); hold off;

Finally, there are a few new routines to make working with reweighted graphs easier. See EXAMPLES/REWEIGHTED_GRAPHS for information about the INDEXED_SPARSE and EDGE_WEIGHT_INDEX functions.


 
 

Contact us