No License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
gaimc : Graph Algorithms In Matlab Code

Join the 15-year community celebration.

Play games and win prizes!

» Learn more

5.0 | 6 ratings Rate this file 134 Downloads (last 30 days) File Size: 650 KB File ID: #24134 Version: 1.0
image thumbnail

gaimc : Graph Algorithms In Matlab Code


David Gleich (view profile)


Efficient pure-Matlab implementations of graph algorithms to complement MatlabBGL's mex functions.

| Watch this File

File Information

While MatlabBGL uses the Boost Graph Library for efficient graph routines,
gaimc implements everything in pure Matlab code. While the routines are
slower, they aren't as slow as I initially thought. Since people often
have problems getting MatlabBGL to compile on new versions of Matlab
or on new architectures, this library is then a complement to MatlabBGL.

See the published M-files for a few examples of the capabilities.

  depth first search (dfs)
  breadth first search (bfs)
  connected components (scomponents)
  maximum weight bipartite matching (bipartite_matching)
  Dijkstra's shortest paths (dijkstra)
  Prim's minimum spanning tree (mst_prim)
  clustering coefficients (clustercoeffs)
  directed clustering coefficients (dirclustercoeffs)
  core numbers (corenums)

The project is maintained at github :


Matlab Bgl inspired this file.

This file inspired Fgt Fold Geometry Toolbox.

MATLAB release MATLAB 7.5 (R2007b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (8)
07 Oct 2016 dipanka tanu  
26 Jul 2016 Zhe

Zhe (view profile)

Thanks for sharing this!
Which algorithm is used for the bipartite_matching?

Comment only
09 Jun 2014 Ernesto C├ęspedes Montero  
23 May 2013 Lingji Chen

Great work!

There seems to be a bug in dfs(): The line

else v=mod(u+i-1,n)+1; if d(v)>0, continue; end, end

should be

else v=mod(u+i-1-1,n)+1; if d(v)>0, continue; end, end

22 Jul 2011 Alok

Alok (view profile)


Under what license is this available? Can I use this for commercial purposes?

Thanks for the great work.

Comment only
25 Feb 2011 Leon

Leon (view profile)

Thanks for your excellent library! It's great to be able to see how you've solved the technical issues. Good work!

I believe there is a small bug in your clusteringcoeffs.m code, Tt occurs when you try and calculate unweighted clustering with a normal format network (not csr).

Calling clustercoeffs.m(A,0) always exits with

"Error in ==> clustercoeffs at 42
if any(ai)<0, error('gaimc:clustercoeffs',... "

This is because ai is not defined; the easy solution is to nest:
if any(ai) <0, error( ....
within the "if usew, [rp ci ai]..." loop.

your code (lines 39-45):
if usew, [rp ci ai]=sparse_to_csr(A);
else [rp ci]=sparse_to_csr(A);
if any(ai)<0, error('gaimc:clustercoeffs',...
['only positive edge weights allowed\n' ...
'try clustercoeffs(A,0) for an unweighted comptuation']);

proposed fix (lines 39-45)
if usew, [rp ci ai]=sparse_to_csr(A);
if any(ai)<0, error('gaimc:clustercoeffs',...
['only positive edge weights allowed\n' ...
'try clustercoeffs(A,0) for an unweighted comptuation']);
else [rp ci]=sparse_to_csr(A);

Hope that helps,

25 Nov 2010 Forrest Bao  
18 May 2009 Jeremy Kozdon  

Contact us