matlab的BGL库介绍.pdf-资料库

bb_bang-5023711-4744302543369916974.pdf-第1页.png

第1页 / 共61页

bb_bang-5023711-4744302543369916974.pdf-第2页.png

第2页 / 共61页

bb_bang-5023711-4744302543369916974.pdf-第3页.png

第3页 / 共61页

bb_bang-5023711-4744302543369916974.pdf-第4页.png

第4页 / 共61页

bb_bang-5023711-4744302543369916974.pdf-第5页.png

第5页 / 共61页

bb_bang-5023711-4744302543369916974.pdf-第6页.png

第6页 / 共61页

bb_bang-5023711-4744302543369916974.pdf-第7页.png

第7页 / 共61页

bb_bang-5023711-4744302543369916974.pdf-第8页.png

第8页 / 共61页

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 Library1. The following code segment brie y 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)\n', 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); 1http://www.boost.org/doc/graph 1

Contents 1 Installation 2 Motivation and Implementation 2.1 Graphs in Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation details 3 Examples 3.1 Breadth rst search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Depth rst search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Max- ox min-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 New algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 In-place Modication/Pass by Reference Library 5 Visitors 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Specics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Features not implemented 7 Reference 7.1 Sample Graphs 7.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5 5 8 8 9 10 11 12 15 17 18 20 22 29 30 30 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 Toolkit2 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. 2http://msdn.microsoft.com/visualc/vctoolkit2003/ 3

Script Matlab System All 32-bit Windows compile-win32.bat Matlab 7.3 - Current 64-bit Windows compile-win64.bat Matlab 7.0 - Current 32-bit Linux compile-linux-32.sh Matlab 7.0 - Matlab 7.2 compile-linux-64.sh 64-bit Linux 64-bit Linux Matlab 7.3 - Current Mac OS X (PPC) Matlab 7.0 - Current Mac OS X (Intel) Matlab 7.4 - Current compile-linux-64-large.sh compile-macosx-ppc-32.sh 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 Library3 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. 3http://www.boost.org/libs/graph/doc/ 5

Figure 1: A directed graph. For the graph in Figure 1, the adjacency matrix is  0 0 0 0 0 1 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0  ; and we labeled vertex a = 1, b = 2, v = 3, x = 4, y = 5, z = 6. In the original graph from Figure 1, there are two edges from b to y . We have replaced both edges with a two in the adjacency matrix. While this works for many algorithms, there are currently no ways of implemented true multi-graphs in MatlabBGL. Note: There are currently no multi-graphs supported in MatlabBGL. We can construct this graph as a Matlab sparse matrix with the following set of commands. >> A = sparse(6,6); >> A(1,6) = 1; >> A(6,1) = 1; >> A(2,4) = 1; >> A(2,5) = 2; >> A(4,4) = 1; >> A(4,6) = 1; >> A(5,3) = 1; >> labels = {'a';'b';'v';'x';'y';'z'}; Now, we can use the directed graph as a Matlab sparse matrix and as a MatlabBGL graph. As we will see, we can treat any square sparse matrix as a MatlabBGL graphs. 6

Figure 2: An undirected graph. MatlabBGL requires that undirected graphs have symmetric adjacency. When constructing a graph, this means that you must specify each edge twice. The following Matlab session constructs the graph in Figure 2. >> A = sparse(6,6); >> A(1,6) = 1; >> A(6,1) = 1; >> A(2,4) = 1; >> A(4,2) = 1; >> A(2,5) = 1; >> A(5,2) = 1; >> A(3,4) = 1; >> A(4,3) = 1; >> A(3,5) = 1; >> A(5,3) = 1; >> labels = {'a';'b';'v';'x';'y';'z'}; An easier way of constructed the graph from Figure 2 is to take advantage of some of Matlab's sparse matrix routines. We can use one command to add a reverse edge for each edge listed in a sparse matrix by executing >> A = max(A,A'); Using this command, we can build the undirected graph using the commands: >> A = sparse(6,6); >> A(1,6) = 1; >> A(2,4) = 1; >> A(5,2) = 1; >> A(4,3) = 1; >> A(3,5) = 1; >> A = max(A,A'); 7

In general, any square sparse matrix in Matlab is a MatlabBGL graph; the non-zeros of the matrix dene the edges. If the sparse matrix is symmetric, then the graph is undirected. Note: Any square sparse matrix is a MatlabBGL graph. 2.2 Implementation details In this section, we will address some fairly technical details of the implementation. Matlab implements sparse matrices as a set of compressed column arrays. Most adjacency matrix representations (and the one used in MatlabBGL) use the rows of the matrix to specify the edges from a particular vertex. That is, A(i ; j) = 1 indices there is an edge between vertex i and vertex j. Unfortunately, this means that in the Matlab compressed column storage format, we do not have ecient access to the elements of each row of the matrix (i.e. the adjacent vertices). The Boost graph algorithms require access to the adjacent vertices. So, every time we call a MatlabBGL function we transpose the sparse matrix, unless the function requires a symmetric input. Some algorithms only use the non-zero structure of the sparse matrix. Other algorithms use the values of the non-zeros as the weights of the edges. In general, things work the way you expect them to using a sparse adjacency matrix to represent the graph; we have documented any serious deviations from the expected behavior. Transposing the matrix can be somewhat expensive, so we provide an option to eliminate the transpose if the user knows better. Thus, for the most ecient MatlabBGL runtimes, construct the transpose of the adjacency matrix and run the MatlabBGL routines with the extra option >> bfs(A,u,struct('istrans',1)); Currently, the max_flow function performs additional input manipulation and does not have this optimization. 3 Examples We'll show four examples of how to use the Matlab BGL library. The rst three examples come from the Boost Graph Library samples. The last example shows how to write a new algorithm using MatlabBGL. 8

资料库

matlab的BGL库介绍.pdf

相关推荐

网络技术

热门标签

最新资料