Previous Next Contents

10  Metanet

10.1   add_edge adds an edge or an arc between two nodes




CALLING SEQUENCE :

g1 = add_edge(i,j,g)



PARAMETERS :




DESCRIPTION :

add_edge returns the graph g1 with a new edge from node number i to node number j. If the graph is directed, the edge is an arc. The number of edges plus 1 is taken as the name of the new edge.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
g=add_edge(1,7,g);
g('edge_color')=[ones(ta) 11];
show_graph(g);



See Also : add_node X, delete_arcs X, delete_nodes X

10.2   add_node adds a disconnected node to a graph




CALLING SEQUENCE :

g1 = add_node(g,[xy,name])



PARAMETERS :




DESCRIPTION :

add_node adds a disconnected node to graph g and returns the new graph g1.

The coordinates of the new node can be given as a row vector of coordinates in xy. If the nodes of graph g have no coordinates (elements node_x and node_y are []), to give xy has no effect. If the nodes of graph g have coordinates and xy is not given, the new node has (0,0) as coordinates.

If name is given, it is the name of the new node, otherwise the number of nodes plus 1 is taken as the name of the new node.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
n=g('node_number');
g1=add_node(g,[270 140]);
g1('node_color')=[ones(1,n) 11];
show_graph(g1);



See Also : add_edge X, delete_arcs X, delete_nodes X

10.3   adj_lists computes adjacency lists




CALLING SEQUENCE :

[lp,la,ls] = adj_lists(g)
[lp,la,ls] = adj_lists(directed,n,tail,head)



PARAMETERS :




DESCRIPTION :

adj_lists computes the row vectors of the adjacency lists description of the graph g. It is also possible to give adj_lists the description of the graph given by the number of nodes n and the row vectors tail and head.


EXAMPLE :

ta=[2 3 3 5 3 4 4 5 8];
he=[1 2 4 2 6 6 7 7 4];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[129 200 283 281 128 366 122 333];
g('node_y')=[61 125 129 189 173 135 236 249];
show_graph(g);
[lp,la,ls]=adj_lists(g)
[lp,la,ls]=adj_lists(1,g('node_number'),ta,he)



See Also : chain_struct X, graph_2_mat X

10.4   arc_graph graph with nodes corresponding to arcs




CALLING SEQUENCE :

g1 = arc_graph(g)



PARAMETERS :




DESCRIPTION :

arc_graph returns the directed graph g1 with the nodes corresponding to the arcs of the directed graph g. g1 is defined in the following way:

- its nodes correspond to the arcs of g - 2 nodes of the new graph are adjacent if and only if the corresponding arcs of the graph g are consecutive.

The coordinates of the nodes of g1 are given by the middle points of the corresponding edges of g.

If such an arc graph does not exist, an empty vector is returned.


EXAMPLE :

ta=[1 1 2 4 4 5 6 7 2 3 5 1];
he=[2 6 3 6 7 8 8 8 4 7 3 5];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[281  284  360  185  405  182  118  45];
g('node_y')=[262  179  130  154  368  248  64  309];
show_graph(g);
g1=arc_graph(g);
show_graph(g1,'new');



See Also : line_graph X

10.5   arc_number number of arcs of a graph




CALLING SEQUENCE :

ma = arc_number(g)



PARAMETERS :




DESCRIPTION :

arc_number returns the number ma of arcs of the graph. If the graph is directed, it is the number of edges. If the graph is undirected, it is twice the number of edges.


See Also : edge_number X, node_number X

10.6   articul finds one or more articulation points




CALLING SEQUENCE :

nart = articul([i],g)



PARAMETERS :




DESCRIPTION :

articul finds one or more articulation points (if they exist) of the graph g. nart is the row vector of numbers of articulation nodes: deleting one of these nodes increases the number of connected components of the graph. i is the optional node number from which the algorithm starts. The default is 1. Note that the result depends strongly on this starting node.


EXAMPLE :

ta=[2  1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 14 15 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7  7 11 13 15 12 13 14 11 16 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
nart = articul(g)
show_nodes(nart);

10.7   bandwr bandwidth reduction for a sparse matrix




CALLING SEQUENCE :

[iperm,mrepi,profile,ierr] = bandwr(sp,[iopt])
[iperm,mrepi,profile,ierr] = bandwr(lp,ls,n,[iopt])



PARAMETERS :




DESCRIPTION :

bandwr solves the problem of bandwidth reduction for a sparse matrix: the matrix is supposed to be upper triangular with a full diagonal (it is easy to complete a non symmetric matrix, and then discards the added terms).

In the first calling sequence, sp denotes a sparse matrix; the optional argument iopt is 0 or 1: 1 if reducing the profile of the matrix is more important than reducing the bandwidth and 0 if bandwidth reduction is most important.

The second calling sequence corresponds to the description of a graph: lp is a row vector, pointer array of the adjacency lists description of a graph (its size is the number of nodes of the graph + 1); ls is a row vector, node array of the adjacency lists description (its size is the number of edges of the graph i.e. the number of non-zero terms of the corresponding sparse matrix). n is the number of nodes (dimension of sp).

iperm is the permutation vector for reordering the rows and columns which reduces the bandwidth and/or profile (new numbering of the nodes of the graph); mrepi is the inverse permutation (mrepi(iperm) is the identity). profile is the array giving the profile of the sparse matrix after the bandwidth reduction if iopt is 1. If iopt is 0 this array is zero except for the first term giving the bandwidth. The simple command max(profile(2:$)-profile(1:($-1))) returns the bandwidth of the matrix. ierr is an integer indicating an error if its value is not zero.


EXAMPLE :

ta=[2  1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7 7 11 13 15 12 13  9 14 11 16 1 17 14 15];
g=make_graph('foo',0,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
// THE GRAPH
show_graph(g);
a=graph_2_mat(g,'node-node');
ww=tril(a)'+eye();
ww1=full(ww);
xset('window',0)
hist3d((ww1+tril(ww1',-1)+tril(ww1,-1)'),52,85); 
// BANDWIDTH REDUCTION FOR THE MATRIX
[iperm,mrepi,profile,ierr]=bandwr(ww);
max(profile(2:$)-profile(1:($-1)))
// GRAPH WITH THE NEW NUMBERING
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new')
// NEW MATRIX
n=g('node_number');
yy=ww1(mrepi,mrepi);
xset('window',1)
hist3d((yy+tril(yy',-1)+tril(yy,-1)'),52,85); 
// STARTING WITH THE SAME MATRIX
[ij,v,mn]=spget(ww);
g1=make_graph('foo',0,n,ij(:,1)',ij(:,2)');
g1('node_x')=g('node_x');g1('node_y')=g('node_y');
// GRAPH
//show_graph(g1,'rep');
[lp,la,ls] = adj_lists(1,n,g1('tail'),g1('head'));
[iperm,mrepi,profile,ierr]=bandwr(lp,ls,n,0);
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new');

10.8   best_match best matching of a graph




CALLING SEQUENCE :

[card,match] = best_match(g)



PARAMETERS :




DESCRIPTION :

best_match finds an optimal matching for the graph g. The output are card and the vector match. card is the cardinality of an optimal matching. match(i) is the node adjacent to node i in the optimal matching or 0 if i is unmatched.


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);
[card,match] = best_match(g);
sp=sparse([ta' he'],[1:size(ta,2)]',[n,n]);
sp1=sparse([[1:n]' match'],ones(1,size(match,2))',[n,n]);
[ij,v,mn]=spget(sp.*sp1);
show_arcs(v');
//
// WITH A LARGER GRAPH
g=load_graph(SCI+'/demos/metanet/mesh1000');
g('directed')=0;
ta=g('tail');he=g('head');n=node_number(g);
show_graph(g,'new',[3000,1000]);
[card,match] = best_match(g);
sp=sparse([ta' he'],[1:size(ta,2)]',[n,n]);
sp1=sparse([[1:n]' match'],ones(1,size(match,2))',[n,n]);
[ij,v,mn]=spget(sp.*sp1);
show_arcs(v');



See Also : perfect_match X

10.9   chain_struct chained structure from adjacency lists of a graph




CALLING SEQUENCE :

[fe,che,fn,chn] = chain_struct(g)
[fe,che,fn,chn] = chain_struct(lp,la,ls)



PARAMETERS :




DESCRIPTION :

chain_struct computes the row vectors of the edge chained structure description of the graph g. It is also possible to give directly chain_struct the adjacency lists of the graph. This is more efficient if the adjacency lists are already available since chain_struct uses them to make computations.

The vectors fe, che, fn and chn describe the chained structure in the following way:

fe(i)) is the number of the first edge starting from node i

che(fe(i)) is the number of the second edge starting from node i, che(che(fe(i))) is the number of the third edge starting from node i and so on until the value is 0

fn(i) is the number of the first node reached from node i

ch(i) is the number of the node reached by edge che(i).


EXAMPLE :

ta=[1 1 2 3 5 4 6 7 7 3 3 8 8 5];
he=[2 3 5 4 6 6 7 4 3 2 8 1 7 4];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[116 231 192 323 354 454 305 155];
g('node_y')=[118 116 212 219 117 185 334 316];
show_graph(g);
[fe,che,fn,chn] = chain_struct(g)



See Also : adj_lists X, graph_2_mat X

10.10   check_graph checks a Scilab graph list




CALLING SEQUENCE :

check_graph(g)



PARAMETERS :




DESCRIPTION :

check_graph checks its argument g to see if it is a graph list. The checking is not only syntactic (number of elements of the list, compatible sizes of the vectors), but also semantic in the sense that check_graph checks that node_number, tail and head elements of the list can really represent a graph.

Moreover, the names of the node must be different. In fact, this do not give errors in Scilab, but strange behaviour can appear when using the Metanet window. So, this is not checked by check_graph because it is time consuming. It is only checked when loading, saving or showing a graph.




See Also : graph-list X

10.11   circuit finds a circuit or the rank function in a directed graph




CALLING SEQUENCE :

[p,r] = circuit(g)



PARAMETERS :




DESCRIPTION  :

circuit tries to find a circuit for the directed graph g. It returns the circuit p as a row vector of the corresponding arc numbers if it exists and it returns the empty vector [] otherwise. If the graph has no circuit, the rank function is returned in r, otherwise its value is the empty vector [].


EXAMPLE :

// graph with circuit
ta=[1 1 2 3 5 4 6 7 7 3 3 8 8 5];
he=[2 3 5 4 6 6 7 4 3 2 8 1 7 4];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[116 231 192 323 354 454 305 155];
g('node_y')=[ 118 116 212 219 117 185 334 316];
show_graph(g);
p=circuit(g)
show_arcs(p)
// graph without circuit
g=make_graph('foo',1,4,[1 2 2 3],[2 3 4 4]);
[p,r]=circuit(g)

10.12   con_nodes set of nodes of a connected component




CALLING SEQUENCE :

ns = con_nodes(i,g)



PARAMETERS :




DESCRIPTION :

con_nodes returns the row vector ns of the numbers of the nodes which belong to the connected component number i. If i is not the number of a connected component, the empty vector [] is returned.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 7 7 9 10 12 12 13 13 14 15];
he=[2 6 3 4 5 1 3 5 1 8 9 8 11 10 11 11 15 13 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[197 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[76 181 276 278 276 83 174 281 177 86 175 90 290 397 399];
show_graph(g);
con_nodes(2,g)
x_message('Displaying the nodes of component #2');
n=g('node_number');
nodecolor=0*ones(1,n);
nodecolor(1,con_nodes(2,g))=11*ones(con_nodes(2,g));
g('node_color')=nodecolor;
nodediam=20.*ones(1,n);
nodediam(1,con_nodes(2,g))=30*ones(con_nodes(2,g));
g('node_diam')=nodediam;
show_graph(g);



See Also : connex X, is_connex X, strong_connex X, strong_con_nodes X

10.13   connex connected components




CALLING SEQUENCE :

[nc,ncomp] = connex(g)



PARAMETERS :




DESCRIPTION :

connex returns the number nc of connected components of graph g and a row vector ncomp giving the number of the connected component for each node. For instance, if i is a node number, ncomp[i] is the number of the connected component to which node number i belongs.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 7 7 7 8 9 10 12 12 13 13 14 15];
he=[2 6 3 4 5 1 3 5 1 7 5 8 9 5 8 11 10 11 11 15 13 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[197 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[76 181 276 278 276 83 174 281 177 86 175 90 290 397 399];
show_graph(g);
[nc,ncomp]=connex(g)
g('node_color')=10+ncomp; 
g('node_diam')=10+10*ncomp;
x_message('Displaying the connected components of this graph');
show_graph(g);



See Also : con_nodes X, is_connex X, strong_connex X, strong_con_nodes X

10.14   contract_edge contracts edges between two nodes




CALLING SEQUENCE :

g1 = contract_edge(i,j,g)



PARAMETERS :




DESCRIPTION :

contract_edge returns the graph g1, the edges between the nodes number i and j being deleted, the nodes being reduced to one node with the same name as node i and located at the middle point between the 2 previous nodes.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
g1=contract_edge(10,13,g);
show_graph(g1,'new');



See Also : add_edge X, add_node X, delete_arcs X, delete_nodes X

10.15   convex_hull convex hull of a set of points in the plane




CALLING SEQUENCE :

[nhull,ind] = convex_hull(xy)



PARAMETERS :




DESCRIPTION :

convex_hull finds the convex hull of a given set of n points in the plane. xy is the 2 x n matrix of the (x,y) coordinates of the given points. convex_hull returns in nhull the number of the points of the boundary of the convex hull and in ind the row vector (of size nhull) giving the indices in xy of the points of the boundary. The order in ind corresponds to consecutive points on the boundary.


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];
g=make_graph('foo',0,28,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);
xy=[g('node_x');g('node_y')];
[nhull,ind] = convex_hull(xy)
show_nodes(ind);

10.16   cycle_basis basis of cycle of a simple undirected graph




CALLING SEQUENCE :

spc = cycle_basis(g)



PARAMETERS :




DESCRIPTION :

First a spanning tree is found by using min_weight_tree and then used to find all fundamental cycles with respect to this tree. They are returned as a set of cycles, each cycle being represented by a set of edges. These cycles are returned in a sparse matrix spc: each line of this matrix corresponds to a cycle.

The graph g is supposed to be a simple undirected and connected graph (cycle_basis does not check that the graph is simple, use graph_simp before calling it if necessary).


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
gt=make_graph('foo',1,17,ta,he);
gt('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
gt('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
gt('edge_color')=modulo([1:(edge_number(gt))],15)+1;
gt('node_diam')=[1:(gt('node_number'))]+20;
show_graph(gt);
g=graph_simp(gt);
g('edge_color')=modulo([1:(edge_number(g))],15)+1;
g('node_diam')=gt('node_diam');
g('default_edge_hi_width')=12;
show_graph(g);
spc=cycle_basis(g);
for kk=1:(size(spc,1)),
  aaa=spc(kk,:);aaa=full(aaa);aaa(aaa==0)=[];
  show_arcs(aaa);
end;



See Also : min_weight_tree X, graph_simp X

10.17   delete_arcs deletes all the arcs or edges between a set of nodes




CALLING SEQUENCE :

g1 = delete_arcs(ij,g)



PARAMETERS :




DESCRIPTION :

If g is a directed graph, delete_arcs returns the graph g1 with the arcs defined by matrix ij being deleted. ij must be a n x 2 matrix of node numbers: the n arcs to be deleted are defined by couples of nodes (ij(i,1), ij(i,2)).

If g is an undirected graph, the edges corresponding to matrix ij are deleted.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
ij=[13 10;8 6;5 4;4 2];
gt=delete_arcs(ij,g);
show_graph(gt,'new');
g('directed')=0;
gt=delete_arcs(ij,g);
show_graph(gt,'new');



See Also : add_edge X, add_node X, delete_nodes X

10.18   delete_nodes deletes nodes




CALLING SEQUENCE :

g1 = delete_nodes(v,g)



PARAMETERS :




DESCRIPTION :

delete_nodes returns the graph g1, with the nodes given by the vector v being deleted.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
v=[10 13 4];
gt=delete_nodes(v,g);
show_graph(gt,'new');



See Also : add_edge X, add_node X, delete_arcs X

10.19   edge_number number of edges of a graph




CALLING SEQUENCE :

ma = edge_number(g)



PARAMETERS :




DESCRIPTION :

edge_number returns the number m of edges of the graph. If the graph is directed, it is the number of arcs. If the graph is undirected, it is half the number of edges. It is always equal to the dimension of g('tail') and g('head').


See Also : arc_number X, node_number X

10.20   find_path finds a path between two nodes




CALLING SEQUENCE :

p = find_path(i,j,g)



PARAMETERS :




DESCRIPTION :

find_path returns a path p from node number i to node number j if one exists, and the empty vector [] otherwise.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
p=find_path(1,14,g);
edgecolor=1*ones(ta); edgecolor(p)=11*ones(p); g('edge_color')=edgecolor;
show_graph(g); show_arcs(p);



See Also : nodes_2_path X, shortest_path X

10.21   gen_net generation of a network




CALLING SEQUENCE :

g = gen_net(name,directed,v)
g = gen_net()



PARAMETERS :




DESCRIPTION :

gen_net generates a network g. The arguments are the name of the graph, a flag equal to 0 (undirected graph) or to 1 (directed graph) and a vector describing the network (see below).

If no argument are given, a dialog box for the definition of all the arguments is opened.

v must be a row vector with 12 values. The meaning of the values are:

Seed for random: used for initialization of random generation

Number of nodes

Number of sources

Number of sinks

Minimum cost

Maximum cost

Input supply

Output supply

Minimum capacity

Maximum capacity

Percentage of edges with costs: between 0 and 100

Percentage of edges with capacities: between 0 and 100

The cost of edges without cost are put to minimum cost. The maximum capacity of edges without capacity are put to maximum upply

The result is a network g built on a planar connected graph, by using a triangulation method. Moreover, computations are made in order to have a coherent network. Values of costs and maximum capacities are put on the edges. Minimum capacities are reduced to 0.


EXAMPLE :

v=[1,10,2,1,0,10,100,100,0,100,50,50];
g=gen_net('foo',1,v);
show_graph(g)
// generating using dialogs
g=gen_net();
show_graph(g)



See Also : mesh2d X

10.22   girth girth of a directed graph




CALLING SEQUENCE :

d = girth(g)



PARAMETERS :




DESCRIPTION :

girth computes the length (number of arcs) of the shortest cycle in an unweighted directed graph g.


EXAMPLE :

ta=[1 6 2 4 7 5 6 8 4 3 5 1];
he=[2 1 3 6 4 8 8 7 2 7 3 5];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[285  284  335  160  405  189  118  45];
g('node_y')=[266  179   83  176  368  252  64  309];
show_graph(g);
d=girth(g)

10.23   glist graph list creation




CALLING SEQUENCE :

g = glist(a1, ... ,a34)



DESCRIPTION :

glist(a1,....a34) is a shortcut to to tlist(['graph','name','directed','node_number','tail','head',.. 'node_name','node_type','node_x','node_y','node_color',.. 'node_diam','node_border','node_font_size','node_demand',.. 'edge_name','edge_color','edge_width','edge_hi_width',.. 'edge_font_size','edge_length','edge_cost',.. 'edge_min_cap','edge_max_cap','edge_q_weight','edge_q_orig',.. 'edge_weight','default_node_diam','default_node_border',.. 'default_edge_width','default_edge_hi_width',.. 'default_font_size','node_label','edge_label'],a1, ... ,a34) It is a low level function to create graph lists, mainly used by programmers. No checking is done. For standard creation of graph lists, use make_graph.


See Also : check_graph X, graph-list X, make_graph X

10.24   graph-list description of graph list




DESCRIPTION :

A graph in Scilab is represented by a Scilab typed list. We call it a graph list.

You will find below the complete description of the list. Each element is described by one or more lines. The first line gives the name of the element and its definition. Additional informations, such as the default for elements that can have one, are given in the other lines. Indeed, only the 5 first elements must have a value in the list, all the others can be given the empty vector [] as a value, and then the default is used when it is needed by functions or by the Metanet window. For instance, you can define a graph list by 
g=make_graph('min',1,1,[1],[1]);
which is the simplest graph you can create in Metanet (it is directed, has one node and one loop arc on this node).

The name of the element in the list is very important because it is used to access the elements of the list. For instance, if g is a graph list, to get the name of the graph, you only have to do: 
g('name')
and if you want to change the name of the graph to 'toto', you have to do: 
g('name')='toto';
Moreover, you can get the number of edges and the number of arcs of the graph by using edge_number(g) and arc_number(g) (these names do not correspond to elements of the list). For compatibility, node_number(g) can also be used instead of g('node_number').

A graph list can be syntactically correct but not represent a good graph. You can use the function check_graph to check it. Moreover it is a good idea to give nodes different names. In fact, this does not give errors in Scilab, but strange behaviour can appear when using the Metanet window. This is not checked by check_graph because it is time consuming. It is only checked when loading, saving or showing a graph.

The elements of a graph list are given below:




EXAMPLE :

g=load_graph(SCI+'/demos/metanet/mesh100');
g('node_color')=int(rand(1:g('node_number'))*16);
g('edge_color')=int(rand(1:edge_number(g))*16);
show_graph(g)



See Also : arc_number X, check_graph X, edge_number X, glist X, make_graph X, node_number X

10.25   graph_2_mat node-arc or node-node incidence matrix of a graph




CALLING SEQUENCE :

a = graph_2_mat(g,mat)



PARAMETERS :




DESCRIPTION :

graph_2_mat computes the node-arc or the node-node incidence matrix corresponding to the graph g.

If the optional argument mat is omitted or is the string 'node-arc', the node-arc matrix is computed. If mat is the string 'node-node', the node-node matrix is computed.

If n is the number of nodes of the graph and m is the number of edges of the graph, the node-arc matrix is a Scilab sparse matrix of size (n,m).

It is defined as follows. If the graph is directed:

a(i,j) = +1 if node i is the tail of arc j a(i,j) = -1 if node i is the head of arc j If the graph is undirected:

a(i,j) = 1 if node i is the tail or the head of arc j If n is the number of nodes of the graph, the node-node matrix is a Scilab sparse matrix of size (n,n).

It is defined as follows:

a(i,j) = 1 if there is an arc from node i to node j


EXAMPLE :

g=load_graph(SCI+'/demos/metanet/colored');
a=graph_2_mat(g)
a=graph_2_mat(g,'node-node')



See Also : mat_2_graph X

10.26   graph_center center of a graph




CALLING SEQUENCE :

[no,rad] = graph_center(g)



PARAMETERS :




DESCRIPTION :

graph_center computes the center of the graph g i.e. the node for which the largest of the shortest paths to all the other nodes is minimum. The lengths of the arcs are supposed to be integer (and the default value is 1). The output is the value rad of the length of the radius and no which is the node number of the center of the graph.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 15 12 13  9 14 11 16 1 17 14 15];
g=make_graph('foo',0,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
[no,rad] = graph_center(g)
show_nodes(no);



See Also : graph_diameter X

10.27   graph_complement complement of a graph




CALLING SEQUENCE :

g1 = graph_complement(g,[gmax])



PARAMETERS :




DESCRIPTION :

graph_complement returns the undirected graph g1 which is the complement of the graph g with respect to the corresponding complete graph. When gmax is given, the complement is made with respect to gmax. g and gmax are supposed to be simple graphs (use graph_simp before calling graph_complement if necessary) and to have the same number of nodes.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 11 12 13 13 13 14 15 17 17 16 16];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 15 12 13 9 10 14 11 16 14 15 1 17];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('edge_color')=modulo([1:(edge_number(g))],15)+1;
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
g1=graph_complement(g);
show_graph(g1,'new');
g=graph_complement(g1);
show_graph(g);



See Also : graph_sum X, graph_simp X

10.28   graph_diameter diameter of a graph




CALLING SEQUENCE :

[d,p] = graph_diameter(g)



PARAMETERS :




DESCRIPTION :

graph_diameter computes the diameter of the graph g i.e. the largest shortest path between two nodes. The length of the arcs are supposed to be integer (and the default value is 1). The output is the value d of the length of the diameter and p is the corresponding path.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 15 12 13  9 14 11 16 1 17 14 15];
g=make_graph('foo',0,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
[d,p] = graph_diameter(g)
show_arcs(p);



See Also : graph_center X

10.29   graph_power kth power of a directed 1-graph




CALLING SEQUENCE :

g1 = graph_power(g,k)



PARAMETERS :




DESCRIPTION :

graph_power computes the directed graph g1 which is the kth power of directed 1-graph g. There is an arc between two nodes in g1 if there exists a path between these nodes of length at most k in g. graph_power(g,1) is graph g.

If such a graph does not exist, an empty vector is returned.


EXAMPLE :

ta=[1 1 2 4 4 5 6 7 2 3 5 1];
he=[2 6 3 6 7 8 8 8 4 7 3 5];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[285  284  335  160  405  189  118  45];
g('node_y')=[266  179   83  176  368  252  64  309];
show_graph(g);
g1=graph_power(g,2);
show_graph(g1,'new');

10.30   graph_simp converts a graph to a simple undirected graph




CALLING SEQUENCE :

g1 = graph_simp(g)



PARAMETERS :




DESCRIPTION :

graph_simp returns the simple undirected graph g1 corresponding to multigraph g. It deletes loops in g, replaces directed edges with undirected edges and replaces multiple edges with single edges.


EXAMPLE :

ta=[1 1  1 2 2 2 3 4 4 4 5 5 6 7 7 8 8 9 9 10 10 10 10 10 11 12 12 13 13 13 14 15 16 16 17 17];
he=[1 2 10 3 5 7 4 2 9 9 4 6 6 8 2 6 9 7 4  7 11 13 13 15 12 11 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163  63  98 164 162 273 235 267 384 504 493 409 573 601 627 642];
g('node_y')=[ 59 133 223 311 227 299 221 288 384 141 209 299 398 383 187 121 301];
show_graph(g);
g1=graph_simp(g);
show_graph(g1,'new');

10.31   graph_sum sum of two graphs




CALLING SEQUENCE :

g2 = graph_sum(g,g1)



PARAMETERS :




DESCRIPTION :

graph_sum creates a graph g2 with an adjacency matrix equal to the sum of the adjacency matrices of the two graphs g and g1. g and g1 are supposed to be simple graphs (use graph_simp before calling graph_complement if necessary) and to have the same number of nodes.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('edge_color')=modulo([1:(edge_number(g))],15)+1;
g('edge_width')=ones(1,(edge_number(g)));
g('node_diam')=[1:(g('node_number'))]+20;
g('node_name')=['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' 'N' 'O' 'P' 'Q'];
show_graph(g);
ta=[2 3 4 5 11 12 1];
he=[10 5 6 7 15 17 7];
g1=make_graph('foo',1,17,ta,he);
g1('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g1('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g1('edge_color')=modulo([1:(edge_number(g1))],15)+1;
g1('edge_width')=10*ones(1,(edge_number(g1)));
g1('node_diam')=[1:(g1('node_number'))]+20;
g1('node_name')=['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' 'N' 'O' 'P' 'Q'];
show_graph(g1,'new');
g2=graph_sum(g,g1);
show_graph(g2,'new');



See Also : graph_complement X, graph_union X

10.32   graph_union union of two graphs




CALLING SEQUENCE :

g2 = graph_union(g,g1)



PARAMETERS :




DESCRIPTION :

graph_union creates a new graph g2. The node set of g2 is the union (in the usual sense) of the node sets of g and g1. g2 has an edge for each edge of g and an edge for each edge of g1. The edges of g and g1 having the same endpoints are kept and in this case g2 has multiple edges.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('edge_color')=modulo([1:(edge_number(g))],15)+1;
g('node_diam')=[1:(g('node_number'))]+20;
g('node_name')=['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' 'N' 'O' 'P' 'Q'];
show_graph(g);
l=netwindows(); nw=l(2);
v=[7 8 9 10 11 12 13];
show_nodes(v);
g1=subgraph(v,'nodes',g);
show_graph(g1,'new');
v=[1 2 5 6 7 8 9 10];
netwindow(nw);
show_nodes(v);
g2=subgraph(v,'nodes',g);
show_graph(g2,'new');
g=graph_union(g1,g2);
show_graph(g,'new');



See Also : supernode X, subgraph X

10.33   hamilton hamiltonian circuit of a graph




CALLING SEQUENCE :

cir = hamilton(g)



PARAMETERS :




DESCRIPTION :

hamilton finds an hamiltonian circuit (if it exists) of the directed graph g.


EXAMPLE :

ta=[2  1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7 7 11 13 15 12 13  9 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
cir=hamilton(g)
show_arcs(cir);

10.34   is_connex connectivity test




CALLING SEQUENCE :

res = is_connex(g)



PARAMETERS :




DESCRIPTION :

is_connex returns 1 if the graph g is connected and 0 otherwise.


EXAMPLE :

g=make_graph('foo',1,3,[1,2,3,1],[2,3,1,3]);
is_connex(g)
g=make_graph('foo',1,4,[1,2,3,1],[2,3,1,3]);
is_connex(g)



See Also : con_nodes X, strong_connex X

10.35   knapsack solves a 0-1 multiple knapsack problem




CALLING SEQUENCE :

[earn,ind] = knapsack(profit,weight,capa,[bck])



PARAMETERS :




DESCRIPTION :

knapsack solve a 0-1 multiple knapsack problem with n (n >= 2) items and m knapsacks (m >= 1). profit is the vector of the (integer) profits of the n items and weight is the vector of the corresponding (integer) weights. capa is the vector of the (integer) capacities of the m knapsacks. bck is an optional integer: the maximum number of backtrackings to be performed, if heuristic solution is required. If the exact solution is required bck can be omitted or can have a negative value. earn is the value of the criterium for the "optimal" solution and ind is a vector giving the optimal location: ind(i) gives the number of the knapsack where item i is inserted and this value is 0 if the item i is not in the optimal solution.

We recall that the problem to be solved is the following: p(i) and w denote respectively the profit and the weight of the item i 1=1,...,n; c(j) denotes the capacity of the knapsack j j=1,...,m; q(j,i) denotes the quantity of item i in knapsack j (in fact 0 or 1).

We want to maximize the global profit E: E=p(1)*[x(1,1)+...+x(m,1)]+...+p(n)*[x(1,n)+...+x(m,n)] under the constraints: [w(1)*x(j,1)+...+w(n)*x(j,m)] <= c(j) ; j=1,...,m [x(1,i)+...+x(m,i)] <= 1 ; i=1,...,n x(j,i)= 0 or 1 p(),w(),c() are positive integers.


EXAMPLE :

weight=ones(1,15).*.[1:4];
profit=ones(1,60);
capa=[15 45 30 60];
[earn,ind]=knapsack(profit,weight,capa)



See Also : qassign X

10.36   line_graph graph with nodes corresponding to edges




CALLING SEQUENCE :

g1 = line_graph(g)



PARAMETERS :




DESCRIPTION :

line_graph returns the graph g1 with the nodes corresponding to the edges of the graph g. g1 is defined in the following way: - its nodes correspond to the edges of g - 2 nodes of the new graph are adjacent if and only if the corresponding edges of the graph g are adjacent.

The coordinates of the nodes of g1 are given by the middle points of the corresponding edges of g.


EXAMPLE :

ta=[1 1 2 4 4 5 6 7 2 3 5 1];
he=[2 6 3 6 7 8 8 8 4 7 3 5];
g=make_graph('foo',0,8,ta,he);
g('node_x')=[281  284  360  185  405  182  118  45];
g('node_y')=[262  179  130  154  368  248  64  309];
show_graph(g);
g1=line_graph(g);
show_graph(g1,'new');



See Also : arc_graph X

10.37   load_graph loads a graph




CALLING SEQUENCE :

g = load_graph(name)



PARAMETERS :




DESCRIPTION :

name is the name of a graph file which contains the ASCII description of a graph. Such a file must have the "graph" extension. name can be the name or the pathname of the file; if the "graph" extension is missing in name, it is assumed. load_graph returns the corresponding graph list.


EXAMPLE :

g=load_graph(SCI+'/demos/metanet/mesh100.graph');
show_graph(g);
g=load_graph(SCI+'/demos/metanet/colored');
show_graph(g,'new');



See Also : save_graph X

10.38   make_graph makes a graph list




CALLING SEQUENCE :

g = make_graph(name,directed,n,tail,head)



PARAMETERS :




DESCRIPTION :

make_graph makes a graph list according to its arguments which are respectively the name of the graph, a flag for directed or undirected, the number of nodes and the row vectors tail and head. These are the minimal data needed for a graph.

If n is a positive number, graph g has n nodes; this number must be greater than or equal to max(max(tail),max(head)). If it is greater than this number,graph g has isolated nodes. The nodes names are taken as the nodes numbers.

If n is equal to 0, graph g has no isolated node and the number of nodes is computed from tail and head. The nodes names are taken from the numbers in tail and head.




EXAMPLE :

// creating a directed graph with 3 nodes and 4 arcs.
g=make_graph('foo',1,3,[1,2,3,1],[2,3,1,3]);
// creating a directed graph with 13 nodes and 14 arcs.
ta=[1  1 2 7 8 9 10 10 10 10 11 12 13 13];
he=[2 10 7 8 9 7  7 11 13 13 12 13  9 10];
g=make_graph('foo',1,13,ta,he);
g('node_x')=[120  98  87 188 439 698 226 127 342 467 711 779 477];
g('node_y')=[ 21 184 308 426 435 428 129 360 435  55 109 320 321];
show_graph(g)
// creating same graph without isolated node and 14 arcs.
g=make_graph('foo',1,0,ta,he);
g('node_x')=[120  98 226 127 342 467 711 779 477];
g('node_y')=[ 21 184 129 360 435  55 109 320 321];
show_graph(g,'new')



See Also : graph-list X

10.39   mat_2_graph graph from node-arc or node-node incidence matrix




CALLING SEQUENCE :

g = mat_2_graph(a,directed,[mat])



PARAMETERS :




DESCRIPTION :

mat_2_graph computes the graph g corresponding to the node-arc or the node-node incidence matrix a. Note that a checking is made to insure that a is a sparse node-arc or node-node incidence matrix of a directed (directed = 1) or undirected (directed = 0) graph. If the optional argument mat is omitted or is the string 'node-arc', a must be a node-arc matrix. If mat is the string 'node-node', a must be a node-node matrix.


EXAMPLE :

g=load_graph(SCI+'/demos/metanet/colored');
show_graph(g);
a=graph_2_mat(g);
g1=mat_2_graph(a,1);
g1('node_x')=g('node_x'); g1('node_y')=g('node_y');
show_graph(g1,'new');
a=graph_2_mat(g,'node-node');
g1=mat_2_graph(a,1,'node-node');
g1('node_x')=g('node_x'); g1('node_y')=g('node_y');
show_graph(g1,'new');



See Also : adj_lists X, chain_struct X, graph_2_mat X

10.40   max_cap_path maximum capacity path




CALLING SEQUENCE :

[p,cap] = max_cap_path(i,j,g)



PARAMETERS :




DESCRIPTION :

max_cap_path returns the path with maximum capacity from node i to node j for the graph g if it exists and returns the empty vector [] otherwise.

The capacities of the edges are given by the element edge_max_cap of the graph list. If its value is not given (empty vector []), max_cap_path returns the empty vector []. The capacities must be strictly positive, i.e negative capacities are considered as equal to 0 (no capacity at all).


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
ma=edge_number(g);
g('edge_max_cap')=int(rand(1,ma)*16)+5;
[p,cap]=max_cap_path(1,14,g);
edgecolor=1*ones(1,ma); edgecolor(p)=11*ones(p); g('edge_color')=edgecolor;
x_message(['The maximum capacity is: '+string(cap);
           'Showing the corresponding path']);
show_graph(g); show_arcs(p);

10.41   max_clique maximum clique of a graph




CALLING SEQUENCE :

[size,nodes] = max_clique(g,[ind])



PARAMETERS :




DESCRIPTION :

max_clique computes the maximum clique of the graph g i.e. the complete subgraph of maximum size. ind is a parameter for the choice of the method: if ind is 0 the method is a partial enumerative algorithm and if ind is 1 the algorithm is based on quadratic zero-one programming. The default is 0. The output size is the number of the nodes of the clique found by the algorithm and nodes is the vector of the corresponding nodes.


EXAMPLE :

 
ta=[1 2 3 4 5 6 6 7 8  9 10 16 16 10 11 11 12 12 11 14 15 15 13 7 13 13];
he=[2 3 4 5 6 7 8 8 9 10 16  2  3 11 12 13  1 14 14 15  5  9 12 4 14 15];
g=make_graph('foo',0,16,ta,he);
g('node_x')=[106 199 369 467 470 403 399 347 308 269 184 108 199 268 345 272];
g('node_y')=[341 420 422 321 180 212 286 246 193 244 243 209  59 134  51 348];
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
[ns,no] = max_clique(g);
show_nodes(no);
g1=graph_complement(g);
[ns,no] = max_clique(g1);
show_nodes(no);

10.42   max_flow maximum flow between two nodes




CALLING SEQUENCE :

[v,phi,flag] = max_flow(i,j,g)



PARAMETERS :




DESCRIPTION :

max_flow returns the value of maximum flow v from node number i to node number j if it exists, and the value of the flow on each arc as a row vector phi. All the computations are made with integer numbers. The graph must be directed. If the problem is not feasible, flag is equal to 0, otherwise it is equal to 1.

The bounds of the flow are given by the elements edge_min_cap and edge_max_cap of the graph list. The value of the maximum capacity must be greater than or equal to the value of the minimum capacity. If the value of edge_min_cap or edge_max_cap is not given (empty row vector []), it is assumed to be equal to 0 on each edge.


EXAMPLE :

ta=[1 1 2 2 3 3 4 4 5 5 5 5 6 6 6 7 7 15 15 15 15 15 15];
ta=[ta, 15 8 9 10 11 12 13 14];
he=[10 13 9 14 8 11 9 11 8 10 12 13 8 9 12 8 11 1 2 3 4];
he=[he, 5 6 7 16 16 16 16 16 16 16];
n=16;
g=make_graph('foo',1,n,ta,he);
g('node_x')=[42 615 231 505 145 312 403 233 506 34 400 312 142 614 260 257];
g('node_y')=[143 145 154 154 147 152 157 270 273 279 269 273 273 274 50 376];
ma=edge_number(g);
g('edge_max_cap')=ones(1,ma);
g('edge_min_cap')=zeros(1,ma);
source=15; sink=16;
nodetype=0*ones(1,n); nodetype(source)=2; nodetype(sink)=1;
g('node_type')=nodetype;
nodecolor=0*ones(1,n); nodecolor(source)=11; nodecolor(sink)=11;
g('node_color')=nodecolor;
show_graph(g);
[v,phi,ierr]=max_flow(source,sink,g);
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g('edge_font_size')=edgefontsize;
g('edge_label')=string(phi);
show_graph(g);

10.43   mesh2d triangulation of n points in the plane




CALLING SEQUENCE :

[nutr,A] = mesh2d(x,y,[front])



PARAMETERS :




DESCRIPTION :

The arrays x and y are the coordinates of n points in the plane. mesh2d returns a matrix nutr(3,nbt) of the numbers of the nodes of the nbt triangles of the triangulation of the points. It returns also a sparse matrix A representing the connections between the nodes (A(i,j)=1 if (i,j) is a side of one of the triangles or i=j). In the case of 3 parameters front is the array defining the boundary: it is the array of the indices of the points located on the boundary . The boundary is defined such that the normal to the boundary is oriented towards outside. The boundary is given by its connected components: a component is the part (i1,i2) such that front(i1)=front(i2) (the external boundary is defined in the counterclockwise way, see the examples below). The error cases are the following: err = 0 if no errors were encountered; err = 3 all nodes are collinear.

If the boundary is given, the other error cases are: err = 2 some points are identical; err = 5 wrong boundary array; err = 6 crossed boundary; err = 7 wrong orientation of the boundary; err = 10 an interior point is on the boundary; err = 8 size limitation; err = 9 crossed boundary; err = 12 some points are identical or size limitation.


EXAMPLE :

//        FIRST CASE
theta=0.025*[1:40]*2.*%pi;
x=1+cos(theta);
y=1.+sin(theta);
theta=0.05*[1:20]*2.*%pi;
x1=1.3+0.4*cos(theta);
y1=1.+0.4*sin(theta);
theta=0.1*[1:10]*2.*%pi;
x2=0.5+0.2*cos(theta);
y2=1.+0.2*sin(theta);
x=[x x1 x2];
y=[y y1 y2];
//
nu=mesh2d(x,y);
nbt=size(nu,2);
jj=[nu(1,:)' nu(2,:)';nu(2,:)' nu(3,:)';nu(3,:)' nu(1,:)'];
as=sparse(jj,ones(size(jj,1),1));
ast=tril(as+abs(as'-as));
[jj,v,mn]=spget(ast);
n=size(x,2);
g=make_graph('foo',0,n,jj(:,1)',jj(:,2)');
g('node_x')=300*x;
g('node_y')=300*y;
g('default_node_diam')=10;
show_graph(g)
//        SECOND CASE !!! NEEDS x,y FROM FIRST CASE
x3=2.*rand(1:200);
y3=2.*rand(1:200);
wai=((x3-1).*(x3-1)+(y3-1).*(y3-1));
ii=find(wai >= .94);
x3(ii)=[];y3(ii)=[];
wai=((x3-0.5).*(x3-0.5)+(y3-1).*(y3-1));
ii=find(wai <= 0.055);
x3(ii)=[];y3(ii)=[];
wai=((x3-1.3).*(x3-1.3)+(y3-1).*(y3-1));
ii=find(wai <= 0.21);
x3(ii)=[];y3(ii)=[];
xnew=[x x3];ynew=[y y3];
fr1=[[1:40] 1];fr2=[[41:60] 41];fr2=fr2($:-1:1);
fr3=[[61:70] 61];fr3=fr3($:-1:1);
front=[fr1 fr2 fr3];
//
nu=mesh2d(xnew,ynew,front);
nbt=size(nu,2);
jj=[nu(1,:)' nu(2,:)';nu(2,:)' nu(3,:)';nu(3,:)' nu(1,:)'];
as=sparse(jj,ones(size(jj,1),1));
ast=tril(as+abs(as'-as));
[jj,v,mn]=spget(ast);
n=size(xnew,2);
g=make_graph('foo',0,n,jj(:,1)',jj(:,2)');
g('node_x')=300*xnew;
g('node_y')=300*ynew;
g('default_node_diam')=10;
show_graph(g)
//        REGULAR CASE !!! NEEDS PREVIOUS CASES FOR x,y,front
xx=0.1*[1:20];
yy=xx.*.ones(1,20);
zz= ones(1,20).*.xx;
x3=yy;y3=zz;
wai=((x3-1).*(x3-1)+(y3-1).*(y3-1));
ii=find(wai >= .94);
x3(ii)=[];y3(ii)=[];
wai=((x3-0.5).*(x3-0.5)+(y3-1).*(y3-1));
ii=find(wai <= 0.055);
x3(ii)=[];y3(ii)=[];
wai=((x3-1.3).*(x3-1.3)+(y3-1).*(y3-1));
ii=find(wai <= 0.21);
x3(ii)=[];y3(ii)=[];
xnew=[x x3];ynew=[y y3];
nu=mesh2d(xnew,ynew,front);
nbt=size(nu,2);
jj=[nu(1,:)' nu(2,:)';nu(2,:)' nu(3,:)';nu(3,:)' nu(1,:)'];
as=sparse(jj,ones(size(jj,1),1));
ast=tril(as+abs(as'-as));
[jj,v,mn]=spget(ast);
n=size(xnew,2);
g=make_graph('foo',0,n,jj(:,1)',jj(:,2)');
g('node_x')=300*xnew;
g('node_y')=300*ynew;
g('default_node_diam')=3;
show_graph(g)

10.44   metanet opens a Metanet window




CALLING SEQUENCE :

window = metanet([path,winsize])



PARAMETERS :




DESCRIPTION :

This function is used to open a Metanet window from Scilab.

path is an optional argument; it is the directory where graph files are searched. If this path is the pathname of a graph, this graph is displayed in the Metanet window and the directory of this pathname becomes the default directory. By default, path is the working directory.

winsize is an optional argument; it is a row vector [width height] giving the size in pixels of Metanet window. The default is [1000 1000].

Usually, show_graph is used and metanet is seldom used.

Each time metanet is executed, a new window is created and its number is incremented by 1.


See Also : netclose X, netwindow X, netwindows X, show_graph X

10.45   metanet_sync asynchronous or synchronous mode in Metanet




CALLING SEQUENCE :

res = metanet_sync([flag])



PARAMETERS :




DESCRIPTION :

By default Metanet windows work with Scilab in asynchronous mode, ie Scilab proceeds without waiting for graphics commands sent to Metanet window to terminate: these commands are show_graph, show_arcs and show_nodes. This mode is the most efficient. But when running a lots of such graphical commands, problems can arise.

metanet_sync(0) changes to asynchronous mode (default).

metanet_sync(1) changes to synchronous mode.

metanet_sync() returns the current mode (0 = asynchronous, 1 = synchronous).

10.46   min_lcost_cflow minimum linear cost constrained flow




CALLING SEQUENCE :

[c,phi,v,flag] = min_lcost_cflow(i,j,cv,g)



PARAMETERS :




DESCRIPTION :

min_lcost_cflow computes the minimum cost flow in the network g, with the value of the flow from source node i to sink node j constrained to be equal to cv.

min_lcost_cflow returns the total cost of the flows on the arcs c, the row vector of the flows on the arcs phi and the value of the flow v on the virtual arc from sink to source. If v is less than cv, a message is issued, but the computation is done: in this case flag is equal to 0, otherwise it is equal to 1.

The bounds of the flows are given by the elements edge_min_cap and edge_max_cap of the graph list. The value of the minimum capacity must be equal to zero, and the value of the maximum capacity must be non negative and must be integer numbers. If the value of edge_min_cap or edge_max_cap is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The costs on the edges are given by the element edge_cost of the graph list. The costs must be non negative. If the value of edge_cost is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The demands, element node_demand of the graph list, must be equal to zero.

This function uses the algorithm of Busacker and Goven.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 181 276 278 276 103 174 281 177 86 175 90 290 397 399];
show_graph(g);
g1=g; ma=arc_number(g1); n=g1('node_number');
g1('edge_min_cap')=0*ones(1,ma);
rand('uniform');
g1('edge_max_cap')=round(20*rand(1,ma))+ones(1,ma);
g1('edge_cost')=10*rand(1,ma)+ones(1,ma);
source=15; sink=1; cv=5;
[c,phi,v]=min_lcost_cflow(source,sink,cv,g1);
x_message(['The cost is: '+string(c);
           'Showing the flow on the arcs']);
nodetype=0*ones(1,n); nodetype(source)=2; nodetype(sink)=1;
g1('node_type')=nodetype;
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
nodecolor=0*ones(1,n); nodecolor(source)=11; nodecolor(sink)=11;
g1('node_color')=nodecolor;
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);



See Also : min_lcost_flow1 X, min_lcost_flow2 X, min_qcost_flow X

10.47   min_lcost_flow1 minimum linear cost flow




CALLING SEQUENCE :

[c,phi,flag] = min_lcost_flow1(g)



PARAMETERS :




DESCRIPTION :

min_lcost_flow1 computes the minimum linear cost flow in the network g. It returns the total cost of the flows on the arcs c and the row vector of the flows on the arcs phi. If the problem is not feasible (impossible to find a compatible flow for instance), flag is equal to 0, otherwise it is equal to 1.

The bounds of the flow are given by the elements edge_min_cap and edge_max_cap of the graph list. The value of the minimum capacity and of the maximum capacity must be non negative and must be integer numbers. The value of the maximum capacity must be greater than or equal to the value of the minimum capacity. If the value of edge_min_cap or edge_max_cap is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The costs on the edges are given by the element edge_cost of the graph list. The costs must be non negative. If the value of edge_cost is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The demands, element node_demand of the graph list, must be equal to zero.

This function uses the out-of-kilter algorithm.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10 1 8];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1 12 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
show_graph(g);
g1=g;ma=arc_number(g1);
rand('uniform');
while %T then
  g1('edge_min_cap')=round(20*rand(1,ma));
  g1('edge_max_cap')=round(20*rand(1,ma))+g1('edge_min_cap')+33*ones(1,ma);
  g1('edge_cost')=round(10*rand(1,ma))+ones(1,ma);
  [c,phi,flag]=min_lcost_flow1(g1);
  if flag==1 then break; end;
end;  
x_message(['The cost is: '+string(c);
           'Showing the flow on the arcs ']);
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);



See Also : min_lcost_cflow X, min_lcost_flow2 X, min_qcost_flow X

10.48   min_lcost_flow2 minimum linear cost flow




CALLING SEQUENCE :

[c,phi,flag] = min_lcost_flow2(g)



PARAMETERS :




DESCRIPTION :

min_lcost_flow2 computes the minimum linear cost flow in the network g. It returns the total cost of the flows on the arcs c and the row vector of the flows on the arcs phi. If the problem is not feasible (impossible to find a compatible flow for instance), flag is equal to 0, otherwise it is equal to 1.

The bounds of the flow are given by the elements edge_min_cap and edge_max_cap of the graph list. The value of the minimum capacity must be equal to zero. The values of the maximum capacity must be non negative and must be integer numbers. If the value of edge_min_cap or edge_max_cap is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The costs on the edges are given by the element edge_cost of the graph list. The costs must be non negative and must be integer numbers. If the value of edge_cost is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The demand on the nodes are given by the element node_demand of the graph list. The demands must be integer numbers. Note that the sum of the demands must be equal to zero for the problem to be feasible. If the value of node_demand is not given (empty row vector []), it is assumed to be equal to 0 on each node.

This functions uses a relaxation algorithm due to D. Bertsekas.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10 1 8];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1 12 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
show_graph(g);
g1=g; ma=arc_number(g1); n=g1('node_number');
g1('edge_min_cap')=0.*ones(1,ma);
x_message(['Random generation of data';
           'The first(s) generated problem(s) may be unfeasible']);
while %T then
 rand('uniform');
 g1('edge_max_cap')=round(20*rand(1,ma))+20*ones(1,ma);
 g1('edge_cost')=round(10*rand(1,ma)+ones(1,ma));
 rand('normal');
 dd=20.*rand(1,n)-10*ones(1,n);
 dd=round(dd-sum(dd)/n*ones(1,n));
 dd(n)=dd(n)-sum(dd);
 g1('node_demand')=dd;
 [c,phi,flag]=min_lcost_flow2(g1);
 if flag==1 then break; end;
end;
x_message(['The cost is: '+string(c);
           'Showing the flow on the arcs and the demand on the nodes']);
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
g1('node_label')=string(g1('node_demand'));
show_graph(g1);



See Also : min_lcost_cflow X, min_lcost_flow1 X, min_qcost_flow X

10.49   min_qcost_flow minimum quadratic cost flow




CALLING SEQUENCE :

[c,phi,flag] = min_qcost_flow(eps,g)



PARAMETERS :




DESCRIPTION :

min_qcost_flow computes the minimum quadratic cost flow in the network g. It returns the total cost of the flows on the arcs c and the row vector of the flows on the arcs phi. eps is the precision of the iterative algorithm. If the problem is not feasible (impossible to find a compatible flow for instance), flag is equal to 0, otherwise it is equal to 1.

The bounds of the flow are given by the elements edge_min_cap and edge_max_cap of the graph list. The value of the maximum capacity must be greater than or equal to the value of the minimum capacity. If the value of edge_min_cap or edge_max_cap is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The costs on the edges are given by the elements edge_q_orig and edge_q_weight of the graph list. The cost on arc u is given by:

(1/2)*edge_q_weight[u](phi[u]-edge_q_orig[u])^2 The costs must be non negative. If the value of edge_q_orig or edge_q_weight is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

This function uses an algorithm due to M. Minoux.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10 1 8];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1 12 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
show_graph(g);
g1=g; ma=arc_number(g1);
rand('uniform');
while %T then
  g1('edge_min_cap')=round(5*rand(1,ma));
  g1('edge_max_cap')=round(20*rand(1,ma))+30*ones(1,ma);
  g1('edge_q_orig')=0*ones(1,ma);
  g1('edge_q_weight')=ones(1,ma);
  [c,phi,flag]=min_qcost_flow(0.001,g1);
 if flag==1 then break; end;
end;
x_message(['The cost is: '+string(c);
          'Showing the flow on the arcs']);
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);



See Also : min_lcost_cflow X, min_lcost_flow1 X, min_lcost_flow2 X

10.50   min_weight_tree minimum weight spanning tree




CALLING SEQUENCE :

t = min_weight_tree([i],g)



PARAMETERS :




DESCRIPTION :

min_weight_tree tries to find a minimum weight spanning tree for the graph g. The optional argument i is the number of the root node of the tree; its default value is node number 1. This node is meaningless for an undirected graph.

The weights are given by the element edge_weight of the graph list. If its value is not given (empty vector []), it is assumed to be equal to 0 on each edge. Weigths can be positive, equal to 0 or negative. To compute a spanning tree without dealing with weights, give to weights a value of 0 on each edge or the empty vector [].

min_weight_tree returns the tree t as a row vector of the arc numbers (directed graph) or edge numbers (undirected graph) if it exists or the empty vector [] otherwise. If the tree exists, the dimension of t is the number of nodes less 1. If t(i) is the root of the tree: - for j < i, t(j) is the number of the arc in the tree after node t(j) - for j > i, t(j) is the number of the arc in the tree before node t(j)


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
t=min_weight_tree(1,g); 
g1=g; ma=arc_number(g1); n=g1('node_number');
nodetype=0*ones(1,n); nodetype(1)=2; g1('node_type')=nodetype;
edgecolor=1*ones(1,ma); edgecolor(t)=11*ones(t); g1('edge_color')=edgecolor;
edgewidth=1*ones(1,ma); edgewidth(t)=4*ones(t); g1('edge_width')=edgewidth;
x_message('Minimum weight tree from node 1');
show_graph(g1);

10.51   neighbors nodes connected to a node




CALLING SEQUENCE :

a = neighbors(i,g)



PARAMETERS :




DESCRIPTION :

neighbors returns the numbers of the nodes connected with node i for graph g (directed or not).


EXAMPLE :

ta=[1  6  2  4  7  5  6  8  4  3  5  1];
he=[2  1  3  6  4  8  8  7  2  7  3  5];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[285  284  335  160  405  189  118  45];
g('node_y')=[266  179   83  176  368  252  64  309];
show_graph(g);
a=neighbors(6,g)
show_nodes(a);



See Also : predecessors X, successors X

"Scilab function"

10.52   netclose closes a Metanet window




CALLING SEQUENCE :

netclose(window)



PARAMETERS :




DESCRIPTION :

Each Metanet window has a window number returned by the metanet and show_graph functions. This function is used to close the Metanet window with number window.


See Also : metanet X, netwindow X, netwindows X, show_graph X

10.53   netwindow chooses a Metanet window




CALLING SEQUENCE :

netwindow(window)



PARAMETERS :




DESCRIPTION :

This function is used to change the Metanet window. Each Metanet window has a window number returned by the metanet and show_graph functions. To use the Metanet window associated to window number window, use netwindow(window). The numbers of existing windows are given by the function netwindows.


See Also : metanet X, netclose X, netwindows X, show_graph X

10.54   netwindows gets the numbers of Metanet windows




CALLING SEQUENCE :

l = netwindows()



PARAMETERS :




DESCRIPTION :

This function returns a list l. Its first element is the row vector of all the Metanet windows and the second element is the number of the current Metanet window. This number is equal to 0 if no current Metanet window exists.


See Also : metanet X, netclose X, netwindow X, show_graph X

10.55   node_number number of nodes of a graph




CALLING SEQUENCE :

n = node_number(g)



PARAMETERS :




DESCRIPTION :

node_number returns the number n of nodes of the graph.


See Also : arc_number X, edge_number X

10.56   nodes_2_path path from a set of nodes




CALLING SEQUENCE :

p = nodes_2_path(ns,g)



PARAMETERS :




DESCRIPTION :

nodes_2_path returns the path p corresponding to the node sequence ns given by its node numbers if it exists ; it returns the empty vector [] otherwise.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
ns=[1 10 15 16 17 14 11 12 13 9 7 8 6];
g1=g; nodecolor=1*ones(g('node_x')); nodecolor(ns)=11*ones(ns);
g1('node_color')=nodecolor;
show_graph(g1); show_nodes(ns);
p=nodes_2_path(ns,g);
g1=g; edgecolor=1*ones(ta); edgecolor(p)=11*ones(p);
g1('edge_color')=edgecolor;
show_graph(g1); show_arcs(p);
show_nodes(ns,'sup');



See Also : path_2_nodes X

10.57   nodes_degrees degrees of the nodes of a graph




CALLING SEQUENCE :

[outdegree,indegree] = graph_degree(g)



PARAMETERS :




DESCRIPTION :

nodes_degrees returns the 2 row vectors of the out and in degrees of the nodes of the graph g.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
[outdegree,indegree]=nodes_degrees(g)



See Also : adj_lists X

10.58   path_2_nodes set of nodes from a path




CALLING SEQUENCE :

ns = path_2_nodes(p,g)



PARAMETERS :




DESCRIPTION :

path_2_nodes returns the set of nodes ns corresponding to the path p given by its arc numbers ; if p is not a path, the empty vector [] is returned.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
p=[2 16 23 25 26 22 17 18 19 13 10 11];
g1=g; edgecolor=1*ones(ta); edgecolor(p)=11*ones(p);
g1('edge_color')=edgecolor;
show_graph(g1); show_arcs(p);
ns=path_2_nodes(p,g);
g1=g; nodecolor=1*ones(g1('node_number')); nodecolor(ns)=11*ones(ns);
g1('node_color')=nodecolor;
show_graph(g1);show_nodes(ns);
show_arcs(p,'sup');



See Also : nodes_2_path X

10.59   perfect_match min-cost perfect matching




CALLING SEQUENCE :

[cst,nmatch] = perfect_match(g,arcost)



PARAMETERS :




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 perfect 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 X

10.60   pipe_network solves the pipe network problem




CALLING SEQUENCE :

[x,pi] = pipe_network(g)



PARAMETERS :




DESCRIPTION :

pipe_network returns the value of the flows and of the potentials for the pipe network problem: flow problem with two Kirchhoff laws. The graph must be directed. The problem must be feasible (the sum of the node demands must be equal to 0). The resistances on the arcs must be strictly positive and are given as the values of the element 'edge_weigth' of the graph list.

The problem is solved by using sparse matrices LU factorization.


EXAMPLE :

ta=[1 1 2 2 3 3 4 4 5 5 5 5 6 6 6 7 7 15 15 15 15 15 15];
ta=[ta, 15 8 9 10 11 12 13 14];
he=[10 13 9 14 8 11 9 11 8 10 12 13 8 9 12 8 11 1 2 3 4];
he=[he, 5 6 7 16 16 16 16 16 16 16];
n=16;
g=make_graph('foo',1,n,ta,he);
g('node_x')=[42 615 231 505 145 312 403 233 506 34 400 312 142 614 260 257];
g('node_y')=[143 145 154 154 147 152 157 270 273 279 269 273 273 274 50 376];
show_graph(g);
g('node_demand')=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 -100 100];
w = [1 3 2 6 4 7 8 1 2 2 2 4 7 8 9 2 3 5 7 3 2 5 8 2 5 8];
g('edge_weight')=[w, 6 4 3 5 6];
[x,pi] = pipe_network(g)

10.61   plot_graph general plot of a graph




CALLING SEQUENCE :

plot_graph(g,[rep,rep1])



PARAMETERS :




DESCRIPTION :

plot_graph plots graph g in a Scilab graphical window. The optional arguments rep and rep1 define the parameters of the plot. If there are not given, a dialog box for the definition of these parameters is opened.

rep must be a row vector with 13 integer numbers which must be 1 or 2. The meaning of the values of rep are:

Frame definition: 1 = Automatic 2 = Given (see below)

Plotting arrows: 1 = yes, 2 = no

Plotting sink and source nodes: 1 = yes, 2 = no

Plotting node names: 1 = yes, 2 = no

Plotting node labels: 1 = yes, 2 = no

Plotting arc names : 1 = yes, 2 = no

Plotting arc labels: 1 = yes, 2 = no

Plotting node demand: 1 = yes, 2 = no

Plotting edge length: 1 = yes, 2 = no

Plotting edge cost: 1 = yes, 2 = no

Plotting edge min cap: 1 = yes, 2 = no

Plotting edge max cap: 1 = yes, 2 = no

Plotting edge weight: 1 = yes, 2 = no

If rep(1) is 2, the frame definition must be given by rep1. Otherwise, rep1can be omitted. rep1 must be a row vector [orx,ory,w,h] giving respectively the coordinates of the upper-left point, the width and the height of the plotting rectangle.


EXAMPLE :

// simple graph with different choices for the plot
ta=[2 2 1 1 2 4 3 3 4];
he=[2 2 3 2 3 2 1 2 1];
g=make_graph('foo',1,4,ta,he);
g('node_type')=[1 1 1 2];g('node_name')=string([1:4]);
g('node_x')=[73 737 381 391]; g('node_y')=[283 337 458 142];
g('node_color')=[3 3 3 11];
g('node_diam')=[30 30 30 60];
g('edge_color')=[10 0 2 6 11 11 0 0 11];
rep=[2 2 1 1 2 2 2 2 2 2 2 2 2];
rep1=[100 -400 650 300];
xbasc(); plot_graph(g,rep,rep1);
rep=[2 1 1 1 2 2 2 2 2 2 2 2 2];
x_message('plot the graph with different parameters');
xbasc(); plot_graph(g,rep,rep1);
// plotting using dialogs
xbasc(); plot_graph(g);
xset("thickness",4);
xbasc();
plot_graph(g);
xset('default');



See Also : show_graph X

10.62   predecessors tail nodes of incoming arcs of a node




CALLING SEQUENCE :

a = predecessors(i,g)



PARAMETERS :




DESCRIPTION :

predecessors returns the row vector of the numbers of the tail nodes of the incoming arcs to node i for a directed graph g .


EXAMPLE :

ta=[1  6  2  4  7  5  6  8  4  3  5 1];
he=[2  1  3  6  4  8  8  7  2  7  3 5];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[285  284  335  160  405  189  118  45];
g('node_y')=[266  179   83  176  368  252  64  309];
show_graph(g);
a=predecessors(8,g)
show_nodes(a);



See Also : neighbors X, successors X

10.63   qassign solves a quadratic assignment problem




CALLING SEQUENCE :

[crit,order] = qassign(c,f,d)



PARAMETERS :




DESCRIPTION :

qassign solves the quadratic assignment problem i.e. minimize the global criterium: crit = e(1)+...+e(n) where e(i) = c(i,l(i))+ fd(i) where fd(i) = f(i,1)*d(l(i),l(1))+...+f(i,n)*d(l(i),l(n)) c, f and d are n x n real arrays; their diagonal entries are zero.


EXAMPLE :

n=15;
d=100*rand(15,15);
d=d-diag(diag(d));
c=zeros(n,n);f=c;
f(2:n,1)=ones(1:n-1)';
[crit,order]=qassign(c,f,d)



See Also : knapsack X

10.64   salesman solves the travelling salesman problem




CALLING SEQUENCE :

cir = salesman(g,[nstac])



PARAMETERS :




DESCRIPTION :

salesman solves the travelling salesman problem. g is a directed graph; nstac is an optional integer which is a given bound for the allowed memory size for solving this problem. Its value is 100*n*n by default where n is the number of nodes.


EXAMPLE :

ta=[2  1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7 7 11 13 15 12 13  9 14 11 16 1 17 14 15];
g=make_graph('foo',0,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
g1=make_graph('foo1',1,17,[ta he],[he ta]);
m=arc_number(g1);
g1('edge_length')=5+round(30*rand(1,m));
cir = salesman(g1);
ii=find(cir > edge_number(g)); 
if(ii <> []) then cir(ii)=cir(ii)-edge_number(g);end;
show_arcs(cir);

10.65   save_graph saves a graph




CALLING SEQUENCE :

save_graph(g,path)



PARAMETERS :




DESCRIPTION :

save_graph saves the graph g in a graph file. path is the name of the graph file where the graph will be saved. path can be the name or the pathname of the file; if the "graph" extension is missing in path, it is assumed. If path is the name of a directory, the name of the graph is used as the name of the file.


EXAMPLE :

g=load_graph(SCI+'/demos/metanet/mesh100');
show_graph(g);
unix('rm mymesh100.graph')
save_graph(g,'mymesh100.graph');
g=load_graph('mymesh100');
show_graph(g,'new');



See Also : load_graph X

10.66   shortest_path shortest path




CALLING SEQUENCE :

[p,lp] = shortest_path(i,j,g,[typ])



PARAMETERS :




DESCRIPTION :

shortest_path returns the shortest path p from node i to node j if it exists, and the empty vector [] otherwise. The optional argument typ is a string which defines the type of shortest path, 'arc' for the shortest path with respect to the number of arcs and 'length' for the shortest path with respect to the length of the edges edge_length.

For the shortest path with respect to the length of the edges, the lengths are given by the element edge_length of the graph list. If its value is not given (empty vector []), it is assumed to be equal to 0 on each edge. Lengths can be positive, equal to 0 or negative.

When a shortest path exists, lp is the length of this path.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548]; 
g('node_y')=[56 181 276 278 276 103 174 281 177 86 175 90 290 397 399];
show_graph(g);
g1=g;ma=prod(size(g1('head')));
rand('uniform');
g1('edge_length')=int(20*rand(1,ma));
[p,lp]=shortest_path(13,1,g1,'length');
p
x_message(['Showing the arcs of the shortest path ';
           'Choose ""Display arc names"" in the Graph menu to see arc names']);
g1('edge_name')=string(g1('edge_length'));
edgecolor=ones(1:ma);edgecolor(p)=11*ones(p);
g1('edge_color')=edgecolor;
edgefontsize=12*ones(1,ma);edgefontsize(p)=18*ones(p);
g1('edge_font_size')=edgefontsize;
show_graph(g1);



See Also : find_path X, nodes_2_path X

10.67   show_arcs highlights a set of arcs




CALLING SEQUENCE :

show_arcs(p,[sup])



PARAMETERS :




DESCRIPTION :

show_arcs highlights the set of arcs or edges p of the displayed graph in the current Metanet window. If the optional argument sup is equal to the string 'sup', the highlighting is superposed on the previous one.

By default, this function works in asynchronous mode (see metanet_sync).


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
t=min_weight_tree(1,g); g1=g; ma=edge_number(g1);
edgecolor=1*ones(1,ma); g1('edge_color')=edgecolor;
edgewidth=1*ones(1,ma); edgewidth(t)=4*ones(t); g1('edge_width')=edgewidth;
for i=8:12,
 edgecolor(t)=i*ones(t); g1('edge_color')=edgecolor;
 unix('sleep 2'); show_graph(g1);
 show_arcs(t);
end;



See Also : metanet_sync X, show_nodes X

10.68   show_graph displays a graph




CALLING SEQUENCE :

nw = show_graph(g,[smode,scale])
nw = show_graph(g,'new',[scale,winsize])



PARAMETERS :




DESCRIPTION :

show_graph displays the graph g in the current Metanet window. If there is no current Metanet window, a Metanet window is created. The return value nw is the number of the Metanet window where the graph is displayed.

If the optional argument smode is equal to the string 'rep' or is not given and if there is already a graph displayed in the current Metanet window, the new graph is displayed instead.

If the optional argument smode is equal to the string 'new', a new Metanet window is created. In this case, if the optional argument winsize is given as a row vector [width height], it is the size in pixels of Metanet window. The default is [1000 1000].

The optional argument scale is the value of the scale factor when drawing the graph. The default value is 1.

The labels of the nodes and edges, if they exist, are displayed.

By default, this function works in asynchronous mode (see metanet_sync).


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g,2);
show_graph(g,0.5);
show_graph(g,1);



See Also : metanet_sync X

10.69   show_nodes highlights a set of nodes




CALLING SEQUENCE :

show_nodes(nodes,[sup])



PARAMETERS :




DESCRIPTION :

show_nodes highlights the set of nodes nodes of the displayed graph in the current Metanet window. If the optional argument sup is equal to the string 'sup', the highlighting is superposed on the previous one.

By default, this function works in asynchronous mode (see metanet_sync).


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
for i=2:3:g('node_number'), show_nodes([i]); end;
for i=1:3:g('node_number'), show_nodes([i],'sup'); end;



See Also : metanet_sync X, show_arcs X

10.70   split_edge splits an edge by inserting a node




CALLING SEQUENCE :

g1 = split_edge(i,j,g,name)



PARAMETERS :




DESCRIPTION :

split_edge returns the graph g1, the edge from node number i to node number j being splitted: a new node is created and located at the middle point between the 2 previous nodes. This new node is linked with the 2 nodes i and j. If name is given, it is the name of the new node, otherwise the number of nodes plus 1 is taken as the name of the new node.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
show_graph(g);
gt=split_edge(1,2,g);
show_graph(gt,'new');



See Also : add_edge X, add_node X, delete_arcs X, delete_nodes X

10.71   strong_con_nodes set of nodes of a strong connected component




CALLING SEQUENCE :

ns = strong_con_nodes(i,g)



PARAMETERS :




DESCRIPTION :

strong_con_nodes returns the row vector ns of the numbers of the nodes which belong to the strong connected component number i.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[197 191 106 194 296 305 305 418 422 432 552 550 549 416 548]; 
g('node_y')=[76 181 276 278 276 83 174 281 177 86 175 90 290 397 399];
show_graph(g);
ncomp=strong_con_nodes(3,g);
n=g('node_number');
nodecolor=0*ones(1,n); nodecolor(ncomp)=11*ones(ncomp);
g('node_color')=nodecolor;
nodediam=20*ones(1,n); nodediam(ncomp)=40*ones(ncomp);
g('node_diam')=nodediam;
x_message('Set of nodes of the strong connected component #3');
show_graph(g);



See Also : connex X, con_nodes X, strong_connex X

10.72   strong_connex strong connected components




CALLING SEQUENCE :

[nc,ncomp] = strong_connex(g)



PARAMETERS :




DESCRIPTION :

strong_connex returns the number nc of strong connected components for the graph g and a row vector ncomp giving the number of the strong connected component for each node. For instance, if i is a node number, ncomp[i] is the number of the strong connected component to which node i belongs.


EXAMPLE :

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[197 191 106 194 296 305 305 418 422 432 552 550 549 416 548]; 
g('node_y')=[76 181 276 278 276 83 174 281 177 86 175 90 290 397 399];
show_graph(g);
[nc,ncomp]=strong_connex(g);
g1=g; g1('node_color')=8+ncomp; g1('node_diam')=10+5*ncomp;
x_message('Connected components of the graph');
show_graph(g1);



See Also : connex X, con_nodes X, strong_con_nodes X

10.73   subgraph subgraph of a graph




CALLING SEQUENCE :

g1 = subgraph(v,ind,g)



PARAMETERS :




DESCRIPTION :

subgraph returns the graph g1, built with the numbers given by the the row vector v. If ind is the string 'nodes', g1 is built with the node numbers given by v and the connected edges of these nodes in g. If ind is the string 'edges', g1 is built with the edge numbers given by v and the tail-head nodes of these edges in g.

All the characteristics of the old nodes and edges of g are preserved.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('edge_color')=modulo([1:(edge_number(g))],15)+1;
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
metanet_sync(1);
v=[2 3 4 5 17 13 10];
show_nodes(v);
g1=subgraph(v,'nodes',g);
show_graph(g1);
v=[10 13 12 16 20 19];
show_graph(g);
show_arcs(v);
g1=subgraph(v,'edges',g);
show_graph(g1);
metanet_sync(0);



See Also : add_edge X, add_node X, delete_arcs X, delete_nodes X, supernode X

10.74   successors head nodes of outgoing arcs of a node




CALLING SEQUENCE :

a = successors(i,g)



PARAMETERS :




DESCRIPTION :

successors returns the row vector of the numbers of the head nodes of the outgoing arcs from node i for a directed graph g .


EXAMPLE :

ta=[1  6  2  4  7  5  6  8  4  3  5  1];
he=[2  1  3  6  4  8  8  7  2  7  3  5];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[285  284  335  160  405  189  118  45];
g('node_y')=[266  179   83  176  368  252  64  309];
show_graph(g);
a=successors(6,g)
show_nodes(a);



See Also : neighbors X, predecessors X

10.75   supernode replaces a group of nodes with a single node




CALLING SEQUENCE :

g1 = supernode(v,g)



PARAMETERS :




DESCRIPTION :

supernode returns the graph g1 with the nodes with numbers given by the vector v being contracted in a single node. The number of the supernode is the lowest number in v. The characteristics of the old nodes and edges are preserved. The supernode is located at the mean center of v. Its diameter and border are twice the previous of the replaced node.

The demand of the new node, if it exists, is the sum of the demands of the shrunken nodes.


EXAMPLE :

ta=[1 1 2 2 2 3 4 5 5 7 8 8 9 10 10 10 10 10 11 12 13 13 13 14 15 16 16 17 17];
he=[2 10 3 5 7 4 2 4 6 8 6 9 7 7 11 13 13 15 12 13 9 10 14 11 16 1 17 14 15];
g=make_graph('foo',1,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
g('edge_color')=modulo([1:(edge_number(g))],15)+1;
g('node_diam')=[1:(g('node_number'))]+20;
show_graph(g);
v=[7 10 13 9];
show_nodes(v);
g1=supernode(v,g);
show_graph(g1,'new');



See Also : add_edge X, add_node X, delete_arcs X, delete_nodes X

10.76   trans_closure transitive closure




CALLING SEQUENCE :

g1 = trans_closure(g)



PARAMETERS :




DESCRIPTION :

trans_closure returns as a new graph list g1 the transitive closure of the graph g. This graph must be directed and connected. If <name> if the name of graph g, <name>_trans_closure is the name of the transitive closure.


EXAMPLE :

ta=[2 3 3 5 3 4 4 5 8];
he=[1 2 4 2 6 6 7 7 4];
g=make_graph('foo',1,8,ta,he);
g('node_x')=[129 200 283 281 128 366 122 333];
g('node_y')=[61 125 129 189 173 135 236 249];
show_graph(g);
g1=trans_closure(g);
vv=1*ones(ta); aa=sparse([ta' he'],vv');
ta1=g1('tail'); he1=g1('head');
ww=1*ones(ta1); bb=sparse([ta1' he1'],ww');
dif=bb-aa; lim=size(ta1); edgecolor=0*ones(ta1);
for i=1:lim(2)
 if dif(ta1(i),he1(i))==1 then edgecolor(i)=11; end;
end;
g1('edge_color')=edgecolor;
x_message('Transitive closure of the graph');
show_graph(g1);
Previous Next Contents