No BSD License  

Highlights from
MatlabBGL

4.87273

4.9 | 58 ratings Rate this file 327 Downloads (last 30 days) File Size: 8.72 MB File ID: #10922

MatlabBGL

by

 

30 Apr 2006 (Updated )

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

| Watch this File

File Information
Description

The MatlabBGL library fills a hole in Matlab's suite of algorithms. Namely, it provides a rich set of algorithms to work with graphs, as in graph theory graphs. The MatlabBGL package uses Matlab's native sparse matrix type as a graph and provides algorithms that work

The algorithms included are

Searching: breadth first search,depth first search, and astar (A*) search

Shortest Path Algorithms: Dijkstra's algorithm, the Bellman-Ford algorithm, Johnson's algorithm, and the Floyd-Warshall algorithm.

Minimum Spanning Trees: Prim's algorithm and Kruskal's algorithm.

Components: strongly connected components and biconnected components (and articulation points).

Flow Algorithms: Goldberg's push-relabel maximum-flow minimum-cut algorithm.

Statistics: Betweenness Centrality, Clustering Coefficients, and Edge Centrality

Graph Creation: Erdos Reyni (Gnp) Graph, Cycle Graph, Wheel Graph, Star Graph

Planar Graphs: Boyer-Myrvold planarity testing, Chrobak-Payne straight line drawing

Graph Layout: force directed layout, spring based layout, topology filling layout

Additional documentation and the MatlabBGL website are at the following URL:
http://www.stanford.edu/~dgleich/programs/matlab_bgl.

The package includes precompiled MEX files for Windows (32-bit and 64-bit), and Linux (32-bit and 64-bit for Matlab 2006b+), and MacOSX (32-bit Intel and 32-bit PPC).

The package includes source code to compile on other platforms as well. For issues, please use the matlab-bgl launchpad page: https://answers.launchpad.net/matlab-bgl/

Please contact me (see the website) if you have an issue with the software and I will help you try and resolve it. (If you need an old version, check my Stanford website for older codes.)

Precompiled for 64-bit Linux (Matlab R2006b+), 32-bit Linux (Matlab R14SP3+), 32-bit Windows (Matlab R2007a+), 32-bit Mac OS X PPC (Matlab 2007a+), 32-bit Mac OS X Intel (Matlab 2007a+). Compiled and tested on 64-bit Windows and Solaris and other versions of Matlab.

** For 64-bit Mac's with R2009b or higher, please see http://dgleich.wordpress.com/2010/07/08/matlabbgl-osx-64-bit/ for a set of files compiled for you. I'm hoping to start working on version 5.0 soon and won't be updating this version.

Acknowledgements

This file inspired Pmfg, Mat Plan Wdm V0.5, Gaimc : Graph Algorithms In Matlab Code, and Wg Plot Weighted Graph Plot (A Better Version Of Gplot).

MATLAB release MATLAB 7.4 (R2007a)
Other requirements A somewhat recent version of Matlab. See the testing matrix on the website.
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (89)
15 Sep 2014 John

Have a see see if it is good

12 Jul 2014 Nejc Ilc  
11 Jul 2014 isaac  
17 Jun 2014 Rodrigo

Thanks for the great toolbox. Are there instructions for building this revision or v5 from github? Not sure how to link this to the boost 1.54 libraries from Ubuntu.

25 Mar 2014 Weiyu

>> load graphs/padgett-florentine.mat
>> betweenness_centrality(A)
Undefined function 'betweenness_centrality_mex' for input arguments of type 'double'.

Error in betweenness_centrality (line 110)
bc = betweenness_centrality_mex(A,weight_arg);

Someone please help!
I was using betweenness centraility m.file trying to follow the example but i am sure they are under the same file.

25 Mar 2014 Weiyu  
27 Feb 2014 francesco

thanks for the great tool
(Force-directed graphs implementation)

11 Dec 2013 Smita

Has anyone used the fruchterman_reingold_force_directed_layout function in matlab. The last line calls fruchterman_reinyold_mex which does not seem to be included in the package.

18 Nov 2013 Aws

I can't rate this library, because i have a problem of installation. I need to use it, but the problem that even after set path it doesn't work on my pc: windows 7, 64 bits, someone can help me?

31 Aug 2013 naila

Hello!

I couldn't find the toolbox over the mentioned path. Please can any one help me?
if somebody have the toolbox please send me at my email id. That is Qurrat60@yahoo.com. I will be really very thankful to you

21 May 2013 Simon

I think I can do it with a reweighted graph and kamada_kawai_spring_layout. However, my edge weights vector is failing the following test in the MEX file:

if (!mxIsDouble(arg_ewopt) < nz) {
mexErrMsgIdAndTxt("matlab_bgl:invalidParameter",
"The reweight array must be of type double");

even though in Matlab the array is a double. I'm on 64 bit Matlab, and I'm guessing that the mex file 'thinks' I'm on 32.

Any ideas ?

21 May 2013 Simon

I can't work out if this excellent toolbox allows me to represent connection weights by the drawn edge length or not. Can anybody advise, please ?

19 Mar 2013 AlexV Mantzaris

a gem!

14 Mar 2013 Guillaume Vankeerberghen  
15 Feb 2013 Harri S

Thanks for the great toolbox.

I'm trying to solve a shortest path problem with A* using an implicit graph.

If I understood correctly, I should add a new vertex and its edges during the call of examine_vertex visitor. I just cant figure it out how to manipulate the graph inside the visitor.

I would be very happy if you could point me an example of using implicit graph with A*. I tried to google it with little success.

15 Nov 2012 Andrew Wind

Excellent toolbox! Really appreciate it.

Question: After I've solved an all_shortest_paths problem is there a way to add another small set of vertices and add to the previous solution or do I have to solve the entire set from scrath?

01 Sep 2012 Olivier Planchon

EXCELENT!
I had a 4.7 Giga bytes square matrix of 229 million rows/cols to process
The 'component' function processed this monster matrix, 'out of the box', in only 44 seconds.

I rated 5 stars with this only test, after less than an hour of use, but it has put an end to weeks of unsuccesful trials to process this data set.

15 Aug 2012 Charles Nelatury  
04 Aug 2012 Stephen Wu

Maybe I'm too dumb... but when I just copy the example code, it doesn't work already. Seems like I have to specified the 4th argument, which I thought it's not necessary.

I just copy the example code in your max_flow.m and below is the error:

??? Undefined function or method 'max_flow_mex' for input arguments of type 'double'.

Error in ==> max_flow at 78
flowval = max_flow_mex(A,u,v,lower(options.algname));

18 Jul 2012 Eoin  
02 Jul 2012 Robert  
02 Jul 2012 Robert

I'm having trouble using this with matlab 2012a. Has anyone else had any luck? I've also tried with the special mac compiled version at the link above.

29 Jun 2012 Mikael

Thanks for this excellent tool!

You proposed to speed up max_flow for the getting of residual network, does your offer continue ? I am very interested.

Thanks anyway this library is awsome!

18 Jun 2012 Joana

I use your toolbox in my work, and I would like to cite you in a recently accepted paper. How should I cite you? The editing services are requiring information for the reference Gleich 2006.
Thanks!

03 May 2012 Neeraj

Great work. Thanks for this

17 Apr 2012 Ujwal

Great Work!
Is there a way to restrict the distances calculated to a maximum threshold? I need this because I have a large graph and I don't need the distances for all points but only those within a certain neighbourhood.

29 Jan 2012 Derek O'Connor

Top Class, especially with newly-compiled mexw64 files for Windows 7 64-bit

17 Jan 2012 Ueli Rutishauser  
20 Nov 2011 Biaobin Jiang

Terrific!

18 Oct 2011 Mehdi Goudarzi

very nicely written code, thanks for all the effort you've put in.

27 Sep 2011 Liuxun Zhu  
20 Sep 2011 sdw

It‘s a good toolbox,thanks!

19 Jul 2011 Wendy

Hi David, I saw there was a discussion about the shortest_length calculation on 10 Feb 2010. I am having the same issue as Feixiong. Would you mind I having a copy of the temporary patched file for calculating shortest path if it's not too much bother? Thank you very much! -Wendy

25 Nov 2010 Nam Le  
14 May 2010 David Gleich

See this page for a discussion of compiling on 64-bit Macs with recent version of Matlab:

https://answers.launchpad.net/matlab-bgl/+question/69161

If you get a compiled version, please email me with a copy of the precompiled binaries and I'll post them (I don't have a mac otherwise, I'd do it myself! Sorry!)

14 May 2010 Dane T

I want to start by saying thanks for sharing this package with the community. However, recently I have encountered a problem. While I was able to use these scripts with my previous version of matlab, I get an error now that I have installed the latest mac version, Matlab 7.10 64bit Mac. I am using this package along with some algorithms supplied by NetWiki for network visualization and get the following error:

??? Undefined function or method 'matlab_bgl_all_sp_mex' for input arguments of type 'double'.

I have tried the following: Because this file is in a folder named 'private', this version of matlab won't allow this folder name to be added to the path. (I forget if this was the case on previous to my software update). Therefore, I changed the folder name to pri_vate and added it to the path. However, I get the same error. Does anyone know if this version has been precompiled for the 64bit Mac version of Matlab 7.10? If so, does anyone have any helpful suggestions. Also, if it has not, any recommendations on how to compile it for my computer's architecture would be much appreciated.

-Thanks

23 Mar 2010 lesel selle

hello
I have some problems because i can't install matlabBGL;
I install to version : version 4.0 and 2.1. but whenever i try the command "clustering_coefficients(sparse(ones(5)))", that is the error message :

??? Undefined function or variable 'get_matlab_bgl_options'.

Error in ==> clustering_coefficients at 45
[trans check full2sparse] = get_matlab_bgl_options(varargin{:});

I do exactly the installation procedure that you specify.

I'm using matlab 7.7.0(R2008b) or matlab R2009a

Thanks a lot in advance

19 Mar 2010 Mihir

Great piece of code, found it very useful. Found a small bug. MATLAB crashes when max_flow is called on a graph that contains edges with infinite capacity.

15 Mar 2010 Budhachandra Kh

Hi ,
Congrats on a nice and efficient package. I have a large matrix 80000 X 80000 which is quite sparse. I want to find network parameters like shortest path Dij, efficiency, etc. Could you suggest how I should do this ?

10 Feb 2010 David Gleich

In response to Feixiong, when any of the shortest_path algorithms have a target set, the search stops when it first finds the vertex. This does not guarantee that the shortest path is correct, but it's the first path found to the vertex. In light of your comment, I plan to revisit this behavior in a future version. If you require the actual shortest paths, then you should not use the target option in MatlabBGL 4. I'm not planning to provide a patch for this until a new version is released unless I hear from others that it's a source of considerable pain. Please contact me if you need a temporary (patched) shortest_path.m file that would transparently (but potentially inefficiently) address the issue.

10 Feb 2010 Feixiong

Hello David Gleich,

I found some error on the shortest path algorithm. in the "dijkstra_sp" function, if I specify the source only, it can find the right shortest path to all other nodes. However, when I specify both the source and target, sometime it output the right results, sometimes not. Can you sovle it?

By the way, it is very easy to extend the shortest path to bidirectional shortest path?

After all, the algorithm I am using is really efficient. Thanks.

Feixiong

05 Feb 2010 H

As it seems, there's also a built function for my problem, path_from_pred.m...

And a next question as well:

I have a graph that represents e.g. cities and the arcs are distances between them. Is there a way to have some kind of maximum length as an constraint to the shortest path problem?

19 Jan 2010 H

Thank you very much m!

18 Jan 2010 m

"How can I get the shortest path between nodes s and t? What I'm looking for is list of nodes, not just the distance..."

Use the predecessors returned by the shortest_paths function.
For example:

load graphs/clr-25-2.mat
startnode = 1;
endnode = 5;
[d pred] = shortest_paths(A,startnode);

cur = endnode;
path = [];
while(true)
path = [cur path];
if cur == startnode
break;
end
cur = pred(cur);
end

In this example, path = [1 3 5], which represents the shortest path from node 1 to node 5.

18 Jan 2010 H

No one has an idea?

11 Jan 2010 H

Never mind my previous question. How can I get the shortest path between nodes s and t? What I'm looking for is list of nodes, not just the distance...

05 Jan 2010 H

Thanks for the great package!

Is it possible to use this to form a 3-d grid graph with diagonal edges?

23 Dec 2009 Jesse Blocher

Absolutely brilliant. I used the precompiled Linux64 code and it is fast - much faster than anything I'd been able to do so far. Thanks.

18 Sep 2009 Petter

This is an exellent package!

10 Apr 2009 Maddy

Hi,

I am looking for a implementation for the Hopcroft Karp Algorithm for maximum bipartite matching.

Please help.

Thanks
Maddy

21 Feb 2009 Kaushal

Hi David,

Thanks for providing this library to the wider matlab community. It seems quite useful for students like myself.

I just downloaded the new version and was wondering whether the graph lay out algorithms allow insertion of node labels and edge labels on the graph ?

Thanks,

Kaushal

04 Feb 2009 yaaqob alrefaei

when i executed the following
1- Download the latest link from the File Exchange and unzip it to a directory of your choosing.
2- Open Matlab and change directory until you get to the directory where you unzipped it.
3- Change into the matlab_bgl subdirectory.
4- Try typing
clustering_coefficients(sparse(ones(5))) into Matlab. You should the output is error.

??? Undefined command/function 'clustering_coefficients_mex'.

Error in ==> clustering_coefficients at 97
ccfs=clustering_coefficients_mex(A,options.undirected,weight_arg);

Error in ==> Untitled at 3
clustering_coefficients(sparse(ones(5)))

03 Feb 2009 yaaqob alrefaei

i can't install it in matlab
i did the following steps
1- Unzip the file matlab bgl.zip.
2- in Matlab, add path the Windows path “C:\Documents and Settings\dgleich\My Documents\matlab\” to the path
3-To test the installation, try running the following script.

when i try to test the installation, i got this error

??? Undefined command/function 'clustering_coefficients_mex'.

Error in ==> clustering_coefficients at 97 ccfs=clustering_coefficients_mex(A,options.undirected,weight_arg);

03 Feb 2009 yaaqob alrefaei

very sufficient

03 Dec 2008 Andrea Tagliasacchi

The bioinformatics toolbox provides some functions for graphs as well. However I found a problem in the creation of spanning trees which I already reported. This library on the other hand provide a correct solution.

Thanks

17 Nov 2008 Hallvard

Thank you for sharing this library.
I have one question. I frequently get the following warning when using max_flow from version 4. It never occured when I used the 2.1 version or the 3.0 beta.

"Warning: The rounded (unrounded) value of the minimum cut is 7442843 (7.44284e+006),but the value of the max-flow is 7442842. These values should be equal "

The discrepancy seems to always equal 1 between min cut and max flow.

Is this critical? If not, is there a way to suppress warnings like this?

16 Oct 2008 ta ta

Thanks a lot!

03 Sep 2008 amina s

hello this my broblem
------------------------------------------------------------------------
Segmentation violation detected at Wed Sep 03 11:41:28 2008
------------------------------------------------------------------------

Configuration:
MATLAB Version: 7.0.0.19920 (R14)
Operating System: Microsoft Windows XP
Window System: Version 5.1 (Build 2600: Service Pack 2)
Processor ID: x86 Family 15 Model 2 Stepping 9, GenuineIntel
Virtual Machine: Java 1.4.2 with Sun Microsystems Inc. Java HotSpot(TM) Client VM
(mixed mode)
Default Charset: ibm-5348_P100-1997

Register State:
EAX = 1903ac90 EBX = 00cddd00
ECX = 190656b0 EDX = e6f9a94f
ESI = 18ffd0b0 EDI = 00000000
EBP = 00cddd0c ESP = 00cddcf4
EIP = 791b743f FLG = 00010202

Stack Trace:
[0] hg.dll:void __cdecl set_root_CurrentFigure(struct GObject_tag *,struct GObject_tag *)(0x01639bb0, 0, 0x00cde09c, 1) + 127 bytes
[1] hg.dll:_create_figure_post_fcn(0x18ffd0b0 "__ehhandler$??0?$_Tree@V?$_Tmap_..", 0, 0x01493b60, 0xffffffff) + 139 bytes
[2] hg.dll:_hgFigure(1, 0x00cde03c, 1, 0x00cde09c) + 430 bytes
[3] m_dispatcher.dll:public: virtual void __thiscall Mfh_builtin<struct mxArray_tag>::dispatch_mf(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(1, 0x00cde03c, 1, 0x00cde09c) + 55 bytes
[4] m_dispatcher.dll:public: virtual void __thiscall Mfh_MATLAB_fn::dispatch_fh(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(1, 0x00cde03c, 1, 0x00cde09c) + 200 bytes
[5] m_interpreter.dll:_inDispatchFromStack(166, 0x0160dfa3 "figure", 1, 1) + 891 bytes
[6] m_interpreter.dll:_inCallFcnFromReference(0, 0x16a806f0, 0x789b59c0, 0xcccccccd) + 176 bytes
[7] m_interpreter.dll:int __cdecl inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag volatile *)(1, 0, 9, 0) + 4115 bytes
[8] m_interpreter.dll:int __cdecl inInterPcodeSJ(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *)(1, 0, 8, 0) + 272 bytes
[9] m_interpreter.dll:int __cdecl inExecuteMFunctionOrScript(class Mfh_mp *,bool)(0x18f1ad50, 1, 0, 0x18f1ad50) + 773 bytes
[10] m_interpreter.dll:_inExecCompScript(0, 0x00cde71c, 0x18f1ad50, 0xffffffff) + 321 bytes
[11] m_interpreter.dll:public: void __thiscall Mfh_mp::inRunMP(int,struct mxArray_tag * *,int,struct mxArray_tag * *,struct inWorkSpace_tag *)(0, 0x00cde71c, 0, 0x00cde77c) + 122 bytes
[12] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(struct _mdUnknown_workspace *,int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 0, 0x00cde71c, 0) + 28 bytes
[13] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 0x00cde71c, 0, 0x00cde77c) + 26 bytes
[14] m_dispatcher.dll:public: virtual void __thiscall Mfh_file::dispatch_fh(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 0x00cde71c, 0, 0x00cde77c) + 273 bytes
[15] m_interpreter.dll:_inDispatchFromStack(668, 0x0144a5c4 "essaymop", 0, 0) + 891 bytes
[16] m_interpreter.dll:enum opcodes __cdecl inDispatchCall(char const *,int,int,int,int *,int *)(0x0144a5c4 "essaymop", 668, 0, 0) + 111 bytes
[17] m_interpreter.dll:int __cdecl inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag volatile *)(2, 0, 0, 0) + 2411 bytes
[18] m_interpreter.dll:int __cdecl inInterPcodeSJ(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *)(2, 0, 0, 0) + 272 bytes
[19] m_interpreter.dll:_inInterPcode(2, 0x7876f2d8 "¸òvx°úrx`ûrxÐúrx¸òvxØòvx", 0, 0) + 69 bytes
[20] m_interpreter.dll:enum inExecutionStatus __cdecl in_local_call_eval_function(int *,struct _pcodeheader *,int *,struct mxArray_tag * * const,enum inDebugCheck)(0x00cdf2c8, 0x00cdf3bc, 2, 0x166f3670 "essaymop\n") + 162 bytes
[21] m_interpreter.dll:$L72592(0x7876f2d8 "¸òvx°úrx`ûrxÐúrx¸òvxØòvx", 0x166f3670 "essaymop\n", 9, 0) + 196 bytes
[22] m_interpreter.dll:enum inExecutionStatus __cdecl inEvalCmdWithLocalReturnandtype(char const *,int *,enum inDebugCheck)(0, 2, 1, 0x00cdf44c "ôôÍ") + 86 bytes
[23] m_interpreter.dll:_inEvalCmdNoEnd(0x166f3670 "essaymop\n", 0x00cdf4e4, 0x00cdf4a0, 0x01612100) + 16 bytes
[24] bridge.dll:_mnParser(0x7c80b529, 0x01612100, 0, 0) + 431 bytes
[25] mcr.dll:public: void __thiscall mcrInstance::mnParser(void)(271242, 0x4d5c3a43, 0x414c5441, 0x625c3742) + 87 bytes
[26] MATLAB.exe:0x00401d2f(4194304, 0, 271242, 0x01612100)
[27] MATLAB.exe:0x00403e45(3538999, 3604528, 0x7ffdb000, 0x8054b35b)
[28] kernel32.dll:0x7c816d4f(0x00403cc0 "jth(U@", 0, 200, 499)

27 Jun 2008 Amanda Traud

I was wondering if I could get a precompiled versio n for Windows Vista 64bit, as the download doesn't come with this, and I have yet to find a compiler that will compile this for me in Matlab, Thanks so much!!!

07 Jan 2008 David Gleich

In regards to the Segmentation Violation with the max_flow function, see the suggested fix in the FAQ or try MatlabBGL 3.0 beta for a pre-compiled fix.

David

23 Dec 2007 hadi habibi

Dear all
Some times that i using the 'max_flow' function', i encounter with this error :
what is the problem?

------------------------------------------------------------------------
Segmentation violation detected at Sun Dec 23 13:33:38 2007
------------------------------------------------------------------------

Configuration:
MATLAB Version: 7.4.0.287 (R2007a)
MATLAB License: 161051
Operating System: Microsoft Windows XP
Window System: Version 5.1 (Build 2600: Service Pack 2)
Processor ID: x86 Family 15 Model 2 Stepping 4, GenuineIntel
Virtual Machine: Java 1.5.0_07 with Sun Microsystems Inc. Java HotSpot(TM) Client VM mixed mode
Default Charset: windows-1252

Register State:
EAX = 00000000 EBX = 00000001
ECX = 00000000 EDX = 00000065
ESI = 12ed9720 EDI = 12b90000
EBP = 00cec538 ESP = 00cec47c
EIP = 7c92ae22 FLG = 00210213

Stack Trace:
[0] ntdll.dll:0x7c92ae22(0x12b90000, 0, 0x12ed9740, 594)
[1] max_flow_mex.dll:0x12b843ef(0xffff40c0, 101, 0x12ed88a0, 0x0fa25960)
[2] max_flow_mex.dll:0x12b81519(5, 0x00cecc28, 0x12ed88a0, 396)
[3] libmex.dll:_mexRunMexFile(5, 0x00cecc28, 3, 0x00cecc88) + 139 bytes
[4] libmex.dll:private: void __thiscall Mfh_mex::runMexFileWithSignalProtection(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(5, 0x00cecc28, 3, 0x00cecc88) + 86 bytes
[5] libmex.dll:public: virtual void __thiscall Mfh_mex::dispatch_file(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(5, 0x00cecc28, 3, 0x00cecc88) + 263 bytes
[6] m_dispatcher.dll:public: virtual void __thiscall Mfh_file::dispatch_fh(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(5, 0x00cecc28, 3, 0x00cecc88) + 203 bytes
[7] m_interpreter.dll:_inDispatchWithDebug(652, 5, 0x00cecc28, 3) + 192 bytes
[8] m_interpreter.dll:_inDispatchFromStack(652, 0x0fb6e114 "max_flow_mex", 5, 3) + 877 bytes
[9] m_interpreter.dll:enum opcodes __cdecl inDispatchCall(char const *,int,int,int,int *,int *)(0x0fb6e114 "max_flow_mex", 652, 5, 3) + 156 bytes
[10] m_interpreter.dll:int __cdecl inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag volatile *,int *)(1, 420, 61, 0) + 2620 bytes
[11] m_interpreter.dll:int __cdecl protected_inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 420, 36, 0) + 87 bytes
[12] m_interpreter.dll:int __cdecl inInterPcodeSJ(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 420, 36, 0) + 302 bytes
[13] m_interpreter.dll:int __cdecl inExecuteMFunctionOrScript(class Mfh_mp *,bool)(0x043faf20, 0, 3, 0x00ced320) + 734 bytes
[14] m_interpreter.dll:_inWordsj(4, 0x00ced2c0, 3, 0x00ced320) + 351 bytes
[15] m_interpreter.dll:public: void __thiscall Mfh_mp::inRunMP(int,struct mxArray_tag * *,int,struct mxArray_tag * *,struct inWorkSpace_tag *)(4, 0x00ced2c0, 3, 0x00ced320) + 194 bytes
[16] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(struct _mdUnknown_workspace *,int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 4, 0x00ced2c0, 3) + 28 bytes
[17] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(4, 0x00ced2c0, 3, 0x00ced320) + 28 bytes
[18] m_dispatcher.dll:public: virtual void __thiscall Mfh_file::dispatch_fh(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(4, 0x00ced2c0, 3, 0x00ced320) + 203 bytes
[19] m_interpreter.dll:_inDispatchWithDebug(637, 4, 0x00ced2c0, 3) + 192 bytes
[20] m_interpreter.dll:_inDispatchFromStack(637, 0x019aae10 "max_flow", 4, 3) + 877 bytes
[21] m_interpreter.dll:enum opcodes __cdecl inDispatchCall(char const *,int,int,int,int *,int *)(0x019aae10 "max_flow", 637, 4, 3) + 156 bytes
[22] m_interpreter.dll:int __cdecl inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag volatile *,int *)(1, 1842, 108, 0) + 2620 bytes
[23] m_interpreter.dll:int __cdecl protected_inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 1842, 16, 0) + 87 bytes
[24] m_interpreter.dll:int __cdecl inInterPcodeSJ(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 1842, 16, 0) + 302 bytes
[25] m_interpreter.dll:int __cdecl inExecuteMFunctionOrScript(class Mfh_mp *,bool)(0x0433c420, 0, 9, 0x00ced9b8) + 734 bytes
[26] m_interpreter.dll:_inWordsj(1, 0x00ced958, 9, 0x00ced9b8) + 351 bytes
[27] m_interpreter.dll:public: void __thiscall Mfh_mp::inRunMP(int,struct mxArray_tag * *,int,struct mxArray_tag * *,struct inWorkSpace_tag *)(1, 0x00ced958, 9, 0x00ced9b8) + 194 bytes
[28] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(struct _mdUnknown_workspace *,int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 1, 0x00ced958, 9) + 28 bytes
[29] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(1, 0x00ced958, 9, 0x00ced9b8) + 28 bytes
[30] m_dispatcher.dll:public: virtual void __thiscall Mfh_file::dispatch_fh(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(1, 0x00ced958, 9, 0x00ced9b8) + 203 bytes
[31] m_interpreter.dll:_inDispatchWithDebug(636, 1, 0x00ced958, 9) + 192 bytes
[32] m_interpreter.dll:_inDispatchFromStack(636, 0x019af7ac "BiPartitionWithGolf", 1, 9) + 877 bytes
[33] m_interpreter.dll:enum opcodes __cdecl inDispatchCall(char const *,int,int,int,int *,int *)(0x019af7ac "BiPartitionWithGolf", 636, 1, 9) + 156 bytes
[34] m_interpreter.dll:int __cdecl inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag volatile *,int *)(1, 2205, 68, 0) + 2620 bytes
[35] m_interpreter.dll:int __cdecl protected_inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 2205, 4, 0) + 87 bytes
[36] m_interpreter.dll:int __cdecl inInterPcodeSJ(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 2205, 4, 0) + 302 bytes
[37] m_interpreter.dll:int __cdecl inExecuteMFunctionOrScript(class Mfh_mp *,bool)(0x0433c5e0, 0, 13, 0x00cee050) + 734 bytes
[38] m_interpreter.dll:_inWordsj(3, 0x00cedff0, 13, 0x00cee050) + 351 bytes
[39] m_interpreter.dll:public: void __thiscall Mfh_mp::inRunMP(int,struct mxArray_tag * *,int,struct mxArray_tag * *,struct inWorkSpace_tag *)(3, 0x00cedff0, 13, 0x00cee050) + 194 bytes
[40] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(struct _mdUnknown_workspace *,int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 3, 0x00cedff0, 13) + 28 bytes
[41] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(3, 0x00cedff0, 13, 0x00cee050) + 28 bytes
[42] m_dispatcher.dll:public: virtual void __thiscall Mfh_file::dispatch_fh(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(3, 0x00cedff0, 13, 0x00cee050) + 203 bytes
[43] m_interpreter.dll:_inDispatchWithDebug(647, 3, 0x00cedff0, 13) + 192 bytes
[44] m_interpreter.dll:_inDispatchFromStack(647, 0x02a5331d "ClusteredSlepian", 3, 13) + 877 bytes
[45] m_interpreter.dll:_inCallFcnFromReference(0xccbebe7e, 0x03d0f4d0, 0, 0) + 166 bytes
[46] m_interpreter.dll:int __cdecl inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag volatile *,int *)(1, 0, 48, 0) + 4783 bytes
[47] m_interpreter.dll:int __cdecl protected_inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 0, 1, 0) + 87 bytes
[48] m_interpreter.dll:int __cdecl inInterPcodeSJ(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(1, 0, 1, 0) + 302 bytes
[49] m_interpreter.dll:int __cdecl inExecuteMFunctionOrScript(class Mfh_mp *,bool)(0x0433c7a0, 1, 0xccbeb812, 0xffffffff) + 734 bytes
[50] m_interpreter.dll:_inExecCompScript(0, 0x00cee620, 0x0433c7a0, 0x00cee620) + 257 bytes
[51] m_interpreter.dll:public: void __thiscall Mfh_mp::inRunMP(int,struct mxArray_tag * *,int,struct mxArray_tag * *,struct inWorkSpace_tag *)(0, 0x00cee620, 0, 0x00cee680) + 159 bytes
[52] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(struct _mdUnknown_workspace *,int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 0, 0x00cee620, 0) + 28 bytes
[53] m_interpreter.dll:public: virtual void __thiscall Mfh_mp::dispatch_file(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 0x00cee620, 0, 0x00cee680) + 28 bytes
[54] m_dispatcher.dll:public: virtual void __thiscall Mfh_file::dispatch_fh(int,struct mxArray_tag * *,int,struct mxArray_tag * *)(0, 0x00cee620, 0, 0x00cee680) + 203 bytes
[55] m_interpreter.dll:_inDispatchWithDebug(640, 0, 0x00cee620, 0) + 192 bytes
[56] m_interpreter.dll:_inDispatchFromStack(640, 0x12d6f7b4 "CSW_CURVE2", 0, 0) + 877 bytes
[57] m_interpreter.dll:enum opcodes __cdecl inDispatchCall(char const *,int,int,int,int *,int *)(0x12d6f7b4 "CSW_CURVE2", 640, 0, 0) + 156 bytes
[58] m_interpreter.dll:int __cdecl inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag volatile *,int *)(2, 0, 0, 0) + 2745 bytes
[59] m_interpreter.dll:int __cdecl protected_inInterp(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(2, 0, 0, 0) + 87 bytes
[60] m_interpreter.dll:int __cdecl inInterPcodeSJ(enum inDebugCheck,int,int,enum opcodes,struct inPcodeNest_tag *,int *)(2, 0, 0, 0) + 302 bytes
[61] m_interpreter.dll:_inInterPcode(2, 0xccbeb5ae, 0, 0x78503444) + 84 bytes
[62] m_interpreter.dll:enum inExecutionStatus __cdecl in_local_call_eval_function(int *,struct _pcodeheader *,int *,struct mxArray_tag * * const,enum inDebugCheck)(0x00cef31c, 0x00cef38c, 0x00cef3a8, 2) + 152 bytes
[63] m_interpreter.dll:__catch$?inEvalStringWithIsVarFcn@@YA?AW4inExecutionStatus@@PAU_memory_context@@PBDW4EvalType@@HQAPAUmxArray_tag@@W4inDebugCheck@@PAU_pcodeheader@@PAHP6A_NPAX1@Z7@Z$0(0x78503444, 0x01964420 "CSW_CURVE2\n", 0, 0) + 219 bytes
[64] m_interpreter.dll:enum inExecutionStatus __cdecl inEvalCmdWithLocalReturnandtype(char const *,int *,enum inDebugCheck)(0x01964420 "CSW_CURVE2\n", 0, 2, 0x00cef3f8) + 69 bytes
[65] m_interpreter.dll:_inEvalCmdNoEnd(0x01964420 "CSW_CURVE2\n", 0xcce13d39, 0x7848c6b0, 0x00ec57c0) + 16 bytes
[66] bridge.dll:enum inExecutionStatus __cdecl ThrowSignal(char const *)(0x01964420 "CSW_CURVE2\n", 0xcce13a45, 0x018613c0, 0x01861360) + 75 bytes
[67] bridge.dll:__catch$_mnParser$0(0xccfeed3d, 0x01861360, 0x01861360, 0) + 328 bytes
[68] mcr.dll:public: void __thiscall mcrInstance::mnParser(void)(0xccfee93f, 0x004074a4, 336694, 0) + 62 bytes
[69] MATLAB.exe:0x004021b8(4194304, 0, 336694, 10)
[70] MATLAB.exe:0x00403bd2(1109972, 0, 0x7ffdb000, 0x8054b038)
[71] kernel32.dll:0x7c816d4f(0x00403daf, 0, 0x78746341, 32)

This error was detected while a MEX-file was running. If the MEX-file
is not an official MathWorks function, please examine its source code
for errors. Please consult the External Interfaces Guide for information
on debugging MEX-files.

If it is an official MathWorks function, please
follow these steps to report this problem to The MathWorks so we
have the best chance of correcting it:

The next time MATLAB is launched under typical usage, a dialog box will
open to help you send the error log to The MathWorks. Alternatively, you
can send an e-mail to segv@mathworks.com with the following file attached:
C:\DOCUME~1\crystal\LOCALS~1\Temp\matlab_crash_dump.3144

If the problem is reproducible, please submit a Service Request via:
http://www.mathworks.com/support/contact_us/ts/help_request_1.html

A technical support engineer might contact you with further information.

Thank you for your help. Save your workspace and restart MATLAB.

26 Nov 2007 David Gleich

In response to sienkiwicz Fliz:

You need to recompile the libmbgl library using ./compile-linux-64.sh because the default linux library is compiled for the 64-bit indices used with largeArrayDims. Send me an email if you can't get this to work and I can send a precompiled version.

26 Nov 2007 sienkiwicz Fliz

Nice library, but I have some problems to compile on a linux cluster (GLNXA64) and it failed with the following message:
>> compile
mex -largeArrayDims -DMATLAB_BGL_LARGE_ARRAYS -O -I../libmbgl/include -L../libmbgl -lmbgl-linux-64-large astar_search_mex.c
astar_search_mex.c: In function `mexFunction':
astar_search_mex.c:269: warning: passing arg 2 of `astar_search_hfunc_visitor' from incompatible pointer type
astar_search_mex.c:269: warning: passing arg 3 of `astar_search_hfunc_visitor' from incompatible pointer type
astar_search_mex.c:269: warning: passing arg 7 of `astar_search_hfunc_visitor' from incompatible pointer type
astar_search_mex.c:269: warning: passing arg 9 of `astar_search_hfunc_visitor' from incompatible pointer type
astar_search_mex.c:277: warning: passing arg 2 of `astar_search' from incompatible pointer type
astar_search_mex.c:277: warning: passing arg 3 of `astar_search' from incompatible pointer type
astar_search_mex.c:277: warning: passing arg 8 of `astar_search' from incompatible pointer type
astar_search_mex.c:283: warning: passing arg 2 of `astar_search_hfunc' from incompatible pointer type
astar_search_mex.c:283: warning: passing arg 3 of `astar_search_hfunc' from incompatible pointer type
astar_search_mex.c:283: warning: passing arg 8 of `astar_search_hfunc' from incompatible pointer type
astar_search_mex.c:283: warning: passing arg 10 of `astar_search_hfunc' from incompatible pointer type
/usr/bin/ld: cannot find -largeArrayDims
collect2: ld returned 1 exit status

mex: link of 'astar_search_mex.mexa64' failed.

??? Error using ==> mex
Unable to complete successfully

Error in ==> matlab_bgl-3.0-beta/private/compile at 74
eval(mexstr);

-----------------------------------------

My matlab version is 7.1.0.183, it seems the option -largeArrayDims is not supported. I removed this option and compiling is okay, but something wrong occured when I call mst function.

Any suggestions?

18 Sep 2007 tian wei  
24 Jul 2007 Gabi Kliot

Thank you very much! Your code is very usefull.

23 Jul 2007 David Gleich

I released a 3.0 beta version. Check it out on the website. I'll release the finished version to the File Exchange site.

I released a "beta" new version. I call it a beta because it isn't full documented yet.

http://www.stanford.edu/~dgleich/programs/matlab_bgl/index.html

18 Jul 2007 David Gleich

Two notes:

The betweenness centrality issue was an overflow in the int datatype for a larger graph. The function works correctly on a 64-bit version of Matlab with a 64-bit integer.

The max flow bug seems to appear in 2007a and can be fixed by replacing any instances of "free" with "mxFree" in max_flow_mex.c.

I am not planning on fixing the 2.1 release and will devote my efforts to finishing the 3.0 release (with the fix for this crash and almost a 30% across the board speed increase). Please send me an email if you are interested in testing the new version.

18 Jul 2007 Gabi Kliot

There is a bug in max_flow: when I call it to return cut and R and F it crashes with segfault in the C dll code (the example crashes either). Could you please fix it. Thank you.

28 Jun 2007 mohamed k

I am getting a betweeness centrality vector with some negative values !!!! Is it normal ?

26 Jun 2007 mohamed kaf

Very good work ...thx

06 Jun 2007 David Gleich

Dogukan Yücel: you need Matlab 7 or better, R12 is not compatible.

05 Jun 2007 Dogukan Yücel

Error: File: C:\matlabR12\work\matlab_bgl\shortest_paths.m Line: 40 Column: 18

22 May 2007 Radu Negoescu

No problems with it, well commented and (most likely) well implemented. Used for analysis of a 14K vertices graph

15 Apr 2007 josmir pineda

thank you

26 Feb 2007 David Gleich

In response to GC: I am not aware of any bugs in the bellman ford function, but it is possible. If you have a bug, please send it to me.

24 Feb 2007 G C

I only used the bellman ford function and this one is buggy. easier to write your own (take pseudo code from wikipedia)

07 Feb 2007 wisit sukchom

it's an excellent jobs for helping me

15 Jan 2007 Pawel Majewski

Great job! Thanks!

10 Jan 2007 julan hsu

ultra cool!

27 Nov 2006 Ahmet Bakan

Millions of thanks!

17 Oct 2006 Elon Yakir

Amazing

06 Oct 2006 Doraid Beck

u made my day..
thanx alot

22 Aug 2006 Shlomi Lifshits

Thank you very much for this contribution. It is simple to use and very fast.

11 Jul 2006 Mark Cummins

Fast and well-implemented.

23 May 2006 Christopher Honey

Fast and accurate from what I've seen. A minor hassle is that the package only accepts sparse matrices as input.

09 May 2006 li changbing

good

04 May 2006 Qiqi Wang

Fast and robust implementation of many graph algorithms.

01 May 2006 Les Fletcher

Been working with graphs in Matlab for a while now, but have always been frustrated the size and speed constraints it presented. Things are much faster and I can scale much better now.

01 May 2006 Jeremy Kozdon

This is excellent. It has all the graph stuff that I always wish was in MATLAB. And it is really really fast, compared to the other stuff that I have used.

Updates
09 May 2006

Fixed some bugs in the code:

1) components now works
2) mst default algorithm switched to handle graphs with negative edge weights
3) dfs_example.m fixed

24 Jul 2006

Significant updates to the package including visitors, bug fixes, and astar search.

11 Apr 2007

Recompiled for Matlab 2006b on 64-bit platforms, includes precompiled versions for Mac OS X, includes small bug fixes.

Adds predecessor matrix to floyd_warshall.
Adds edge centrality computations.

22 Oct 2008

Fixed mlint warnings and a typo in the title of a published m-file.
Added comment about Matlab R2009b and higher on 64-bit OSX.

07 Jul 2010

Added comment about Matlab R2009b and higher on 64-bit OSX.

Contact us