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)
• Published M Files: Compare performance of gaimc to matlab_bgl, Demo of gaimc - 'Graph Algorithms In Matlab Code', The US airport network

Other Files

gaimc/bfs.m,
gaimc/bipartite_matching.m,
gaimc/clustercoeffs.m,
gaimc/Contents.m,
gaimc/convert_sparse.m,
gaimc/corenums.m,
gaimc/csr_to_sparse.m,
gaimc/demo/airports.m,
gaimc/demo/demo.m,
gaimc/demo/html/airports.png,
gaimc/demo/html/airports_01.png,
gaimc/demo/html/airports_02.png,
gaimc/demo/html/airports_03.png,
gaimc/demo/html/airports_04.png,
gaimc/demo/html/airports_05.png,
gaimc/demo/html/demo.png,
gaimc/demo/html/demo_01.png,
gaimc/demo/html/demo_02.png,
gaimc/demo/html/demo_03.png,
gaimc/demo/html/demo_04.png,
gaimc/demo/html/demo_05.png,
gaimc/demo/html/demo_06.png,
gaimc/demo/html/demo_07.png,
gaimc/demo/html/demo_08.png,
gaimc/demo/html/demo_eq02910.png,
gaimc/demo/html/demo_eq74756.png,
gaimc/demo/html/demo_eq85525.png,
gaimc/demo/html/demo_eq91421.png,
gaimc/demo/html/performance_comparison_simple.png,
gaimc/demo/html/performance_comparison_simple_01.png,
gaimc/demo/performance_comparison.m,
gaimc/demo/performance_comparison_simple.m,
gaimc/dfs.m,
gaimc/dijkstra.m,
gaimc/dirclustercoeffs.m,
gaimc/graph_draw.m,
gaimc/graphs/airports.mat,
gaimc/graphs/all_shortest_paths_example.mat,
gaimc/graphs/bfs_example.mat,
gaimc/graphs/bgl_cities.mat,
gaimc/graphs/celegans.mat,
gaimc/graphs/clique-10.mat,
gaimc/graphs/clr-24-1.mat,
gaimc/graphs/clr-25-2.mat,
gaimc/graphs/clr-26-1.mat,
gaimc/graphs/clr-27-1.mat,
gaimc/graphs/cores_example.mat,
gaimc/graphs/cs-stanford.mat,
gaimc/graphs/dfs_example.mat,
gaimc/graphs/dominator_tree_example.mat,
gaimc/graphs/kt-3-2.mat,
gaimc/graphs/kt-3-7.mat,
gaimc/graphs/kt-6-23.mat,
gaimc/graphs/kt-7-2.mat,
gaimc/graphs/line-7.mat,
gaimc/graphs/matching_example.mat,
gaimc/graphs/max_flow_example.mat,
gaimc/graphs/minnesota.mat,
gaimc/graphs/padgett-florentine.mat,
gaimc/graphs/tapir.mat,
gaimc/graphs/tarjan-biconn.mat,
gaimc/largest_component.m,
gaimc/load_gaimc_graph.m,
gaimc/mst_prim.m,
gaimc/scomponents.m,
gaimc/sparse_to_csr.m,
gaimc/test/dijkstra_perf.m,
gaimc/test/prim_mst_perf.m,
gaimc/test/test_bfs.m,
gaimc/test/test_bipartite_matching.m,
gaimc/test/test_corenums.m,
gaimc/test/test_csr_to_sparse.m,
gaimc/test/test_dfs.m,
gaimc/test/test_examples.m,
gaimc/test/test_largest_component.m,
gaimc/test/test_load_gaimc_graph.m,
gaimc/test/test_main.m,
gaimc/test/test_sparse_to_csr.m

[Jeremy Kozdon]