chain_struct — chained structure from adjacency lists of a graph
[fe,che,fn,chn] = chain_struct(g) [fe,che,fn,chn] = chain_struct(lp,la,ls)
row vector, pointer array of the adjacency lists description of the graph (its size is the number of nodes of the graph + 1)
row vector, arc array of the adjacency lists description of the graph (its size is the number of edges of the graph)
row vector, node array of the adjacency lists description of the graph (its size is the number of edges of the graph)
row vector of the numbers of the first edges starting from nodes (its size is the number of nodes of the graph)
row vector of the numbers of the chained edges (its size is the number of edges of the graph)
row vector of the numbers of the first nodes reached
by the edges of fe
(its size is the number of
nodes of the graph)
row vector of the nodes reached by the edges of che
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)
.
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.nodes.graphics.x=[116 231 192 323 354 454 305 155]; g.nodes.graphics.y=[118 116 212 219 117 185 334 316]; show_graph(g); [fe,che,fn,chn] = chain_struct(g) for i=1:node_number(g) hilite_nodes(i); xpause(1d6) cur=fe(i);while cur<>0;hilite_edges(cur);cur=che(cur);xpause(5d5);end unhilite_nodes(i); cur=fe(i);while cur<>0;unhilite_edges(cur);cur=che(cur);end end