← Back to branch summary

~ubuntu-branches/ubuntu/karmic/scilab/karmic

« back to all changes in this revision

Viewing changes to man/metanet/best_match.cat

  • Committer: Bazaar Package Importer
  • Author(s): Torsten Werner
  • Date: 2002-03-21 16:57:43 UTC
  • Revision ID: james.westby@ubuntu.com-20020321165743-e9mv12c1tb1plztg
Tags: upstream-2.6
Import upstream version 2.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
man/metanet/best_match.cat
 
1
best_match         Scilab Group         Scilab function          best_match
 
2
NAME
 
3
   best_match - best matching of a graph
 
4
  
 
5
CALLING SEQUENCE
 
6
 [card,match] = best_match(g)
 
7
PARAMETERS
 
8
 g  : graph list 
 
9
    
 
10
 card
 
11
     : integer 
 
12
    
 
13
 match
 
14
     : integer row vector 
 
15
    
 
16
DESCRIPTION
 
17
   best_match finds an optimal matching for the graph g. The output are card
 
18
  and the vector match. card is the  cardinality of an optimal matching.
 
19
  match(i) is the node adjacent to node i in the optimal matching or 0 if i
 
20
  is unmatched.
 
21
  
 
22
EXAMPLE
 
23
 ta=[27 27 3 12 11 12 27 26 26 25 25 24 23 23 21 22 21 20 19 18 18];
 
24
 ta=[ta  16 15 15 14 12 9 10 6 9 17 8 17 10 20 11 23 23 12 18 28]; 
 
25
 he=[ 1  2 2  4  5 11 13  1 25 22 24 22 22 19 13 13 14 16 16  9 16];
 
26
 he=[he  10 10 11 12  2 6  5 5 7  8 7  9  6 11  4 18 13  3 28 17];
 
27
 n=28;
 
28
 g=make_graph('foo',0,n,ta,he);
 
29
 xx=[46 120 207 286 366 453 543 544 473 387 300 206 136 250 346 408];
 
30
 g('node_x')=[xx 527 443 306 326 196 139 264  55  58  46 118 513];
 
31
 yy=[36  34  37  40  38  40  35 102 102  98  93  96 167 172 101 179];
 
32
 g('node_y')=[yy 198 252 183 148 172 256 259 258 167 109 104 253];
 
33
 show_graph(g);
 
34
 [card,match] = best_match(g);
 
35
 sp=sparse([ta' he'],[1:size(ta,2)]',[n,n]);
 
36
 sp1=sparse([[1:n]' match'],ones(1,size(match,2))',[n,n]);
 
37
 [ij,v,mn]=spget(sp.*sp1);
 
38
 show_arcs(v');
 
39
 //
 
40
 // WITH A LARGER GRAPH
 
41
 g=load_graph(SCI+'/demos/metanet/mesh1000');
 
42
 g('directed')=0;
 
43
 ta=g('tail');he=g('head');n=node_number(g);
 
44
 show_graph(g,'new',[3000,1000]);
 
45
 [card,match] = best_match(g);
 
46
 sp=sparse([ta' he'],[1:size(ta,2)]',[n,n]);
 
47
 sp1=sparse([[1:n]' match'],ones(1,size(match,2))',[n,n]);
 
48
 [ij,v,mn]=spget(sp.*sp1);
 
49
 show_arcs(v');
 
50
SEE ALSO
 
51
   perfect_match
 
52