version 1.1.0.0 (8.72 MB) by
David Gleich

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

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.

David Gleich (2020). MatlabBGL (https://www.mathworks.com/matlabcentral/fileexchange/10922-matlabbgl), MATLAB Central File Exchange. Retrieved .

Created with
R2007a

Compatible with any release

**Inspired:**
NOCAD - Network based Observability and Controlability Analysis of Dynamical Systems toolbox, PM Architectures Project, GRETNA, MatPlanWDM v0.5, wgPlot - Weighted Graph Plot (a better version of gplot), gaimc : Graph Algorithms In Matlab Code, MetaboNetworks, pmfg

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

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Tomas ScagliariniMatlab sometimes crashes when performing planarity test, any idea?

for i = 1:500

A = sprand(150,150,0.01);

test_planar_graph(A)

end

Yafei HeDaniel RemondiniI am using Matlab R2019a on a "El Capitan" 10.11.6 OSX. I tried the 64bit OSX version available online - https://dgleich.wordpress.com/2010/07/08/matlabbgl-osx-64-bit/ - but I get errors:

Invalid MEX-file '/Users/daniel.remondini2/Downloads/matlab_bgl osx64

2012/private/betweenness_centrality_mex.mexmaci64':

dlopen(/Users/.../matlab_bgl osx64

2012/private/betweenness_centrality_mex.mexmaci64, 6): Library not loaded:

@loader_path/libmex.dylib

Referenced from: /Users/.../matlab_bgl osx64

2012/private/betweenness_centrality_mex.mexmaci64

Reason: image not found

jingwenOlivier LemerDavide Perronezhe wangHuiyun HuangWhy I can't find mst_mex.m? Where is it?

If someone have, can you share it with me?

Thank u.

Mahmoud SalehKlemens EsterleHi,

did anybody get it running for MacOS 64bit?

Would really appreciate pre-compiled Mex-Files.

guanhua tianHi

I download it and try to run it, and ./examples/edge_index_example, and it ERROR,

OS=win7,

matlab R2017a

>> edge_index_example

-------

Example of using the transposed edge index incorrectly

-------

ei, u, v, er(ei), A(u,v)

Error using fprintf

Function is not defined for sparse inputs.

Error in edge_index_example>@(ei,u,v)fprintf('examine_edge %2i, %1i, %1i, %4f, %4f\n',ei,u,v,edge_rand(ei),Av(u,v))

Error in breadth_first_search (line 80)

bfs_dfs_vis_mex(A,u,bfs_visitor,101);

Error in edge_index_example (line 17)

breadth_first_search(A,1,struct('examine_edge',ee));

>>

StandardtrickynessCan I generate planar graphs with these codes? If so how?

SOHAIL Muhammadhello I am using matlab R2008b can anyone help how to run Matlab BGL package, thanks

SOHAIL Muhammadhow to run the MatlabBGL package, need suggestions

Ilya TyuryukanovSuper useful

WenboBO WUcheng joylinSarunMichalis PapakostasJohnHave a see see if it is good

Nejc IlcisaacRodrigoThanks 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.

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.

Weiyufrancescothanks for the great tool

(Force-directed graphs implementation)

SmitaHas 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.

AwsI 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?

nailaHello!

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

SimonI 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 ?

SimonI 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 ?

AlexV Mantzarisa gem!

Guillaume VankeerberghenHarri SThanks 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.

Andrew WindExcellent 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?

Olivier PlanchonEXCELENT!

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.

Charles NelaturyStephen WuMaybe 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));

EoinRobertRobertI'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.

MikaelThanks 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!

JoanaI 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!

NeerajGreat work. Thanks for this

UjwalGreat 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.

Derek O'ConnorTop Class, especially with newly-compiled mexw64 files for Windows 7 64-bit

Ueli RutishauserBiaobin JiangTerrific!

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

Liuxun ZhusdwIt‘s a good toolbox,thanks!

WendyHi 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

Nam LeDavid GleichSee 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!)

Dane TI 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

lesel sellehello

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

MihirGreat 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.

Budhachandra KhHi ,

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 ?

David GleichIn 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.

FeixiongHello 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

HAs 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?

HThank you very much m!

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.

HNo one has an idea?

HNever 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...

HThanks for the great package!

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

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

PetterThis is an exellent package!

MaddyHi,

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

Please help.

Thanks

Maddy

KaushalHi 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

yaaqob alrefaeiwhen 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)))

yaaqob alrefaeii can't install it in matlab

i did the following steps

1- Unzip the ﬁle 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);

yaaqob alrefaeivery sufficient

Andrea TagliasacchiThe 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

HallvardThank 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?

ta taThanks a lot!

amina shello 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)

Amanda TraudI 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!!!

David GleichIn 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

hadi habibiDear 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:

https://www.mathworks.com/support/contact_us.html

A technical support engineer might contact you with further information.

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

David GleichIn 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.

sienkiwicz FlizNice 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?

tian weiGabi KliotThank you very much! Your code is very usefull.

David GleichI 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

David GleichTwo 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.

Gabi KliotThere 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.

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

mohamed kafVery good work ...thx

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

Dogukan YücelError: File: C:\matlabR12\work\matlab_bgl\shortest_paths.m Line: 40 Column: 18

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

josmir pinedathank you

David GleichIn 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.

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

wisit sukchomit's an excellent jobs for helping me

Pawel MajewskiGreat job! Thanks!

julan hsuultra cool!

Ahmet BakanMillions of thanks!

Elon YakirAmazing

Doraid Becku made my day..

thanx alot

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

Mark CumminsFast and well-implemented.

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

li changbinggood

Qiqi WangFast and robust implementation of many graph algorithms.

Les FletcherBeen 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.

Jeremy KozdonThis 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.