Matlab BGL v2.1
David Gleich
April 5, 2007
Abstract and Synopsis
MatlabBGL adds a wide range for graph algorithms to Matlab. The graph algorithms come
from the Boost Graph Library
1
. The following code segment briey demonstrates some of
the calls and algorithms in MatlabBGL.
>> [d ft dt pred] = dfs(A)
>> [d dt pred] = bfs(A);
>> [d pred] = dijkstra_sp(A,u);
>> [d pred] = bellman_ford_sp(A,u);
>> [d pred] = dag_sp(A,u);
>> D = johnson_all_sp(A);
>> D = floyd_warshall_all_sp(A);
>> T = kruskal_mst(A);
>> T = prim_mst(A);
>> cc = components(A)
>> [a C] = biconnected_components(A);
>> [flow cut R F] = max_flow(A,u,v);
>> print_func = @(str) @(u) fprintf('called %s(%s)', str, char(labels(u)));
>> breadth_first_search(A,1,struct('examine_vertex',print_func('examine_vertex')));
>> [d pred rank] = astar_search(A,u,heuristic_func);
1
http://www.boost.org/doc/graph
1
Contents
1 Installation 3
2 Motivation and Implementation 5
2.1 Graphs in Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Examples 8
3.1 Breadth rst search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Depth rst search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Max-ox min-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 New algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 In-place Modication/Pass by Reference Library 15
5 Visitors 17
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 Specics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6 Features not implemented 29
7 Reference 30
7.1 Sample Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2
1 Installation
We are distributing the library as a set of precompiled mex les for Windows and Linux along
with the source code for the libraries. This combination will work for all people, although it
may take a bit of eort.
If all goes well, installing the library is as easy as:
1. Unzip the le
matlab_bgl.zip
. For the sake of example, let's assume you unzipped it
into the same folder as I do: \
/home/dgleich/matlab/
" on Linux and \
C:\Documents
and Settings\dgleich\My Documents\matlab\
" on Windows.
2. In Matlab, add either the Linux path \
/home/dgleich/matlab/matlab bgl/
" or the Win-
dows path \
C:\Documents and Settings\dgleich\My Documents\matlab\
" to the path
(but replacing those directories with the ones where you actually unzipped
matlab_
bgl.zip
).
To test the installation, try running the following script.
% add matlab_bgl to the path
% e.g. addpath('/home/dgleich/matlab/matlab_bgl');
>> clustering_coefficients(sparse(ones(5)))
ans =
1
1
1
1
1
Building the library
Note: You should not need to complete the following steps!
In general, the precompiled versions should work. If they do not and you would like to try
compiling the mex les from source, this section explains the process. On Windows, you
must use a Microsoft Visual Studio compiler. The free Visual Studio 2003 Compiler Toolkit
2
suces for this purpose. On Linux, any recent version of gcc should work. All the precompiled
les are compiled with gcc-3.4 under Linux and the Microsoft Visual Studio 2003 compiler
on 32-bit Windows and Microsoft Visual Studio 2005 x64 cross compiler for 64-bit Windows.
To compile the .lib or .a les, rst determine which compile script you should use.
2
http://msdn.microsoft.com/visualc/vctoolkit2003/
3
System Matlab Script
32-bit Windows All
compile-win32.bat
64-bit Windows Matlab 7.3 - Current
compile-win64.bat
32-bit Linux Matlab 7.0 - Current
compile-linux-32.sh
64-bit Linux Matlab 7.0 - Matlab 7.2
compile-linux-64.sh
64-bit Linux Matlab 7.3 - Current
compile-linux-64-large.sh
Mac OS X (PPC) Matlab 7.0 - Current
compile-macosx-ppc-32.sh
Mac OS X (Intel) Matlab 7.4 - Current
compile-macosx-intel-32.sh
Next, you need to download and unzip version 1.33.1 of the Boost Graph Library. Goto
http://www.boost.org
to download this code. Update the script le for your platform with
the correct path so that the
BOOSTDIR
variable gives the correct location. Check all the paths
to the various tools on Windows to make sure they correspond to your installation. Finally,
run the script le from the libmbgl directory. For example, on 32-bit Windows
E:\dev\matlab\download\matlab_bgl-2.1\libmbgl>compile-win32.bat
Setting environment for using Microsoft Visual Studio 2005 x86 tools.
Setting environment for using Microsoft Visual C++ 2003 Toolkit.
(If you have another version of Visual Studio or Visual C++ installed and wish
to use its tools from the command line, run vcvars32.bat for that version.)
Thank you for choosing the Visual C++ Toolkit 2003! Get started quickly by
building the code samples included in the "Samples" directory. Each sample
includes a short whitepaper discussing the Visual C++ features, and a batch
file for building the code.
Type "cl /?" for brief documentation on compiler options.
Visit http://msdn.microsoft.com/visualc/using/documentation/default.aspx for
complete compiler documentation.
E:\dev\matlab\download\MATLAB~1.1\libmbgl>cl -c -nologo -I"." -I"e:\dev\lib\boos
t_1_33_1" /Fo"Release\\" /EHsc /D "NDEBUG" /O2 /ML components.cc
components.cc
E:\dev\matlab\download\MATLAB~1.1\libmbgl>cl -c -nologo -I"." -I"e:\dev\lib\boos
t_1_33_1" /Fo"Release\\" /EHsc /D "NDEBUG" /O2 /ML max_flow.cc
max_flow.cc
...
On 64-bit Linux,
dgleich@icme-112-dgleich:matlab_bgl/libmbgl$ chmod u+x compile-linux-64-large.sh
dgleich@icme-112-dgleich:matlab_bgl/libmbgl$ ./compile-linux-64-large.sh
To compile the library from the .lib and .a les,
4
>> cd /home/dgleich/matlab/ % use your directory here instead of mine!
>> cd matlab_bgl/
>> cd private
>> compile
>> cd ..
>> cd @ipdouble
>> mex subsasgn.c
>> cd ..
>> cd @ipint32
>> mex subsasgn.c
>> cd ..
If you cannot compile the library and the example does not work, please send email to
mithandor@gmail.com
with as much output as you can.
Try running
mex-setup
and selecting the
gcc
or Microsoft Visual Studio compiler setup
for Linux and Windows, respectively.
For Linux, edit your mexopts.sh le and remove the
-ansi
ag from the CFLAGS and
CXXFLAGS for your platform.
For some versions of Matlab, you may want to change the
CC
and
CXX
to gcc-3.4 or
gcc-4.0.
2 Motivation and Implementation
The Boost Graph Library
3
is a powerful graph analysis toolkit. It contains ecient algorithms
implemented as generic C++ template specications. In the MatlabBGL library, we have
wrapped these algorithms with
mex
functions which are callable from Matlab. The goal of
the library was to introduce as little new material in Matlab as possible. As the next section
explains, MatlabBGL uses the Matlab sparse matrix type as the graph type directly.
The idea behind the MatlabBGL library is to provide a rich set of graph-theoretic routines as
ecient Matlab functions.
2.1 Graphs in Matlab
Matlab
has
a built in graph type: the sparse matrix. The goal of the MatlabBGL library
is to use the Matlab sparse matrix as a graph type. To be slightly more concrete, we use
a sparse matrix in Matlab to represent the adjacency matrix of two graphs from the Boost
Graph library review of graph theory.
3
http://www.boost.org/libs/graph/doc/
5
- 1
- 2
- 3
前往页