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
|
perfect_match(1) Scilab function perfect_match(1)
NAME
perfect_match - min-cost perfect matching
CALLING SEQUENCE
[cst,nmatch] = perfect_match(g,arcost)
PARAMETERS
g : graph list
arcost : integer row vector
cst : integer
nmatch : integer row vector
DESCRIPTION
perfect_match finds a perfect min-cost matching for the graph g. g must be
an undirected graph with an even number of nodes. arcost is the vector of
the (integer) costs of the arcs (the dimension of arcost is twice the
number of edges of the graph). The output is the vector nmatch of the per-
fect matching and the corresponding cost cst.
EXAMPLE
ta=[27 27 3 12 11 12 27 26 26 25 25 24 23 23 21 22 21 20 19 18 18];
ta=[ta 16 15 15 14 12 9 10 6 9 17 8 17 10 20 11 23 23 12 18 28];
he=[ 1 2 2 4 5 11 13 1 25 22 24 22 22 19 13 13 14 16 16 9 16];
he=[he 10 10 11 12 2 6 5 5 7 8 7 9 6 11 4 18 13 3 28 17];
n=28;
g=make_graph('foo',0,n,ta,he);
xx=[46 120 207 286 366 453 543 544 473 387 300 206 136 250 346 408];
g('node_x')=[xx 527 443 306 326 196 139 264 55 58 46 118 513];
yy=[36 34 37 40 38 40 35 102 102 98 93 96 167 172 101 179];
g('node_y')=[yy 198 252 183 148 172 256 259 258 167 109 104 253];
show_graph(g);m2=2*size(ta,2);
arcost=round(100.*rand(1,m2));
[cst,nmatch] = perfect_match(g,arcost);
sp=sparse([ta' he'],[1:size(ta,2)]',[n,n]);
sp1=sparse([[1:n]' nmatch'],ones(1,size(nmatch,2))',[n,n]);
[ij,v,mn]=spget(sp.*sp1);
show_arcs(v');
SEE ALSO
best_match
|
