File Exchange

image thumbnail

gaimc : Graph Algorithms In Matlab Code

version (650 KB) by David Gleich
Efficient pure-Matlab implementations of graph algorithms to complement MatlabBGL's mex functions.


Updated 16 May 2009

No License

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 :

Cite As

David Gleich (2020). gaimc : Graph Algorithms In Matlab Code (, MATLAB Central File Exchange. Retrieved .

Comments and Ratings (12)

Geoff Stanley

John Correa

Buenas tardes disculpen como puedo modificar el codigo y en que linea para hacer el algoritmo que asigne el minimo peso y la suma igual de el minimo

lei zhang

thank you very much!

Tianlong ma

thank you

dipanka tanu


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

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



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

Thanks for the great work.


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,

Forrest Bao

Jeremy Kozdon

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

Inspired by: MatlabBGL

Inspired: Jorsorokin/HDBSCAN, FGT - Fold Geometry Toolbox

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!