← Back to branch summary

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

« back to all changes in this revision

Viewing changes to macros/metanet/girth.sci

  • 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:
macros/metanet/girth.sci
 
1
function [d]=girth(g)
 
2
// Copyright INRIA
 
3
[lhs,rhs]=argn(0)
 
4
if rhs<>1 then error(39), end
 
5
// check g
 
6
if g('directed')<>1 then
 
7
  error('The graph must be directed')
 
8
end
 
9
// girth of graph g (length of the shortest cycle)
 
10
[p,r] = circuit(g);
 
11
if p==[] then 
 
12
   d=0
 
13
end
 
14
l=size(p,2);
 
15
d=l;
 
16
ta=g('tail');he=g('head');
 
17
n=g('node_number'); 
 
18
X=sparse([ta' he'],ones(ta)',[n n]);Y=X;
 
19
for i=2:(l-1),
 
20
  Y=Y*X;
 
21
  if sum(diag(Y))<>0 then
 
22
    d=i;
 
23
  end
 
24
end