gaimc : Graph Algorithms In Matlab Code

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

Description

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.

Functions
  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 : http://github.com/dgleich/gaimc/tree/master

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
MatlabBGL

• MATLAB release: MATLAB 7.5 (R2007b)

[Jeremy Kozdon]

 

[Forrest Bao]

 

[Leon]

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( ....
end
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);
    end
    if any(ai)<0, error('gaimc:clustercoeffs',...
            ['only positive edge weights allowed\n' ...
             'try clustercoeffs(A,0) for an unweighted comptuation']);
    end

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']);
        end
    else [rp ci]=sparse_to_csr(A);
    end

Hope that helps,
L.

[Alok]

David/all:

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

Thanks for the great work.