← Back to branch summary

~logan/ubuntu/trusty/suitesparse/4.2.1-3ubuntu1

« back to all changes in this revision

Viewing changes to CSparse/MATLAB/CSparse/cs_scc2.m

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme
  • Date: 2007-05-29 09:36:29 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20070529093629-zowquo0b7slkk6nc
Tags: 3.0.0-2
http://bugs.debian.org/426349
http://bugs.debian.org/426354
* suitesparse builds properly twice in a row
* Bug fix: "suitesparse - FTBFS: Broken build depens: libgfortran1-dev",
  thanks to Bastian Blank (Closes: #426349).
* Bug fix: "suitesparse_3.0.0-1: FTBFS: build-depends on
  libgfortran1-dev", thanks to Steve Langasek (Closes: #426354).

Show diffs side-by-side

added added

removed removed

Lines of Context:
CSparse/MATLAB/CSparse/cs_scc2.m
1
1
function [p, q, r, s] = cs_scc2 (A, bipartite)
2
 
%CS_SCC2 strongly-connected components of a square or rectangular sparse matrix.
 
2
%CS_SCC2 cs_scc, or connected components of a bipartite graph.
3
3
%   [p,q,r,s] = cs_scc2(A) finds a permutation p so that A(p,q) is permuted into
4
4
%   block upper triangular form (if A is square).  In this case, r=s, p=q and
5
5
%   the kth diagonal block is given by A (t,t) where t = r(k):r(k)+1. 
9
9
%   If A is not square (or for [p,q,r,s] = cs_scc2(A,1)), then the connected
10
10
%   components of the bipartite graph of A are found.  A(p,q) is permuted into
11
11
%   block diagonal form, where the diagonal blocks are rectangular.  The kth
12
 
%   block is given by A(r(k):r(k)+1,s(k):s(k)+1).  A can be rectangular.
 
12
%   block is given by A(r(k):r(k+1)-1,s(k):s(k+1)-1).  A can be rectangular.
13
13
%
14
14
%   Example:
15
15
%       Prob = UFget ('HB/arc130') ; A = Prob.A ; [p q r s] = cs_scc2 (A) ;
19
19
%
20
20
%   See also CS_DMPERM, DMPERM, CS_SCC, CCSPY.
21
21
 
22
 
%   Copyright 2006, Timothy A. Davis.
 
22
%   Copyright 2006-2007, Timothy A. Davis.
23
23
%   http://www.cise.ufl.edu/research/sparse
24
24
 
25
25
[m n] = size (A) ;
26
 
if (m ~= n | (nargin > 1 & bipartite))
 
26
if (nargin < 2)
 
27
    bipartite = 0 ;
 
28
end
 
29
 
 
30
if (m ~= n | bipartite)                                                     %#ok
27
31
 
28
32
    % find the connected components of [I A ; A' 0]
29
33
    S = spaugment (A) ;
30
34
    [psym,rsym] = cs_scc (S) ;
31
 
    p = psym (find (psym <= m)) ;
32
 
    q = psym (find (psym > m)) - m ;
 
35
    p = psym (find (psym <= m)) ;                                           %#ok
 
36
    q = psym (find (psym > m)) - m ;                                        %#ok
33
37
    nb = length (rsym) - 1 ;
34
 
    comp = zeros (1,m+n) ;
35
38
    r = zeros (1,nb+1) ;
36
39
    s = zeros (1,nb+1) ;
37
40
    krow = 1 ;