/
new_in_3_0.m
161 lines (126 loc) · 4.96 KB
/
new_in_3_0.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
%% New features in MatlabBGL version 3.0
% Although MatlabBGL 3.0 was never officially released, here are some of
% it's key features.
%% Better performance
% We redid the backend interface to the BGL routines. This optimization
% gave a considerable performance increase.
%%
% test_benchmark on MatlabBGL 2.1
%
% 2008-10-07, Version 2.1, Matlab 2007b, boost 1.33.0,
% g++-3.4 (lib), gcc-? (mex)
%
% airfoil west cs-stan minneso tapir
% large 0.223 s 0.024 s 0.390 s 0.073 s 0.046 s
% med NaN s 0.955 s NaN s NaN s 6.621 s
% small NaN s 0.758 s NaN s NaN s NaN s
%%
% test_benchmark on MatlabBGL 3.0
%
% 2008-10-07: Version 3.0, Matlab 2007b, boost 1.34.1,
% g++-4.0 (lib), gcc-? (mex)
%
% airfoil west cs-stan minneso tapir
% large 0.183 s 0.017 s 0.222 s 0.048 s 0.037 s
% med NaN s 0.593 s NaN s NaN s 3.901 s
% small NaN s 0.543 s NaN s NaN s NaN s
%% Graph construction functions
% MatlabBGL 2.1 had a few graph construction functions. MatlabBGL 3.0 adds
% the grid_graph function for line, grid, cube, and hyper-cube graphs
[G xy] = grid_graph(6,5); gplot(G,xy,'.-');
%%
% In more dimensions...
[G xyz] = grid_graph(6,5,3);
G = grid_graph(2,2,2,2);
G = grid_graph([3,3,3,3,3]);
%% Targeted search
% The graph search algorithms now let you specify a target vertex that will
% stop the search early if possible.
A = grid_graph(50,50);
tic; d = bfs(A,1,struct()); toc
tic; d = bfs(A,1,struct('target',2)); toc
%%
% Also implemented for astar_search, shortest_paths, and dfs.
%% Edge weights
% In Matlab, there is no way to create a sparse matrix with a structural
% non-zero (used for MatlabBGL edges) and a value of 0 (used for MatlabBGL
% weights). Consequently, it's impossible to run algorithms on graphs
% where the edge weights are 0.
%
% Consequently, some algorithms now take an 'edge_weight' parameter that
% allows you to provide a different set of edge weights which allow
% structural non-zeros and 0 values.
%
% This behavior is a bit complicated, so see the REWEIGHTED_GRAPHS example
% for more information.
%% Matching algorithms
% While maximum cardinality bipartite matching is just a call to max-flow,
% general graph matching algorithms are not. MatlabBGL 3.0 contains the
% matching algorithms in Boost 1.34.0.
load('../graphs/matching_example.mat');
m = matching(A);
sum(m>0)/2 % matching cardinality should be 8
%% New graph statistics
% We added a few new statistics functions.
%%
% Test for a topological ordering of a graph (only applies to DAGs or
% directed acyclic graphs)
n = 10; A = sparse(1:n-1, 2:n, 1, n, n); % construct a simple dag
p = topological_order(A);
test_dag(A)
test_dag(cycle_graph(6)) % a cycle is not acyclic!
%%
% Core numbers can help identify important regions in a graph. MatlabBGL
% includes weighted and directed core numbers. Also, the algorithms return
% the removal time of a particular vertex, which gives interesting graph
% orderings.
% See EXAMPLES/CORE_NUMBERS_EXAMPLE
%%
% New algorithms for clustering_coefficients on weighted and directed
% graphs.
A = clique_graph(6) - cycle_graph(6); % A is a clique - a directed cycle
ccfs = clustering_coefficients(A)
B = sprand(A);
ccfs = clustering_coefficients(B)
C = A|A'; % now it's a full clique again
ccfs = clustering_coefficients(C)
%% Max-flow algorithms
% Since Boost added the Kolmogorov max-flow function, we added the
% full collection of flow algorithms to MatlabBGL.
load('../graphs/max_flow_example.mat');
push_relabel_max_flow(A,1,8)
kolmogorov_max_flow(A,1,8)
edmunds_karp_max_flow(A,1,8)
max_flow(A,1,8,struct('algname','push_relabel'));
max_flow(A,1,8,struct('algname','kolmogorov'));
max_flow(A,1,8,struct('algname','edmunds_karp'));
%% Dominator tree
% Dominator trees are relations about presidence in certain types of
% graphs. These are also called flow-graphs.
load('../graphs/dominator_tree_example.mat');
p = lengauer_tarjan_dominator_tree(A,1);
%% New utility functions
% MatlabBGL 3.0 introduces some new utility functions.
%%
% The output of a shortest path algorithm is a predecessor matrix. To
% convert these predecessor relationships to a path, use the path_from_pred
% function.
[A xy] = grid_graph(6,5); n= size(A,1);
[d dt pred] = bfs(A,1); %
path = path_from_pred(pred,n) % sequence of vertices to upper corner
%%
% Let's draw the path
gplot(A,xy,'r.-');
[px,py]=gplot(sparse(path(1:end-1),path(2:end),1,n,n),xy,'-');
hold on; plot(px,py,'-','LineWidth',2); hold off;
%%
% We can also create a full shortest path tree using the tree_from_pred
% function.
T = tree_from_pred(pred);
gplot(A,xy,'r.-');
[px,py]=gplot(T,xy,'-');
hold on; plot(px,py,'-','LineWidth',2); hold off;
%%
% Finally, there are a few new routines to make working with reweighted
% graphs easier. See EXAMPLES/REWEIGHTED_GRAPHS for information about
% the INDEXED_SPARSE and EDGE_WEIGHT_INDEX functions.