3 static void cs_augment (
int k,
const cs *
A,
int *jmatch,
int *cheap,
int *w,
4 int *js,
int *is,
int *ps)
6 int found = 0, p, i = -1, *Ap = A->
p, *Ai = A->
i,
head = 0, j ;
15 for (p = cheap [j] ; p < Ap [j+1] && !found ; p++)
18 found = (jmatch [i] == -1) ;
29 for (p = ps [
head] ; p < Ap [j+1] ; p++)
32 if (w [jmatch [i]] == k) continue ;
35 js [++
head] = jmatch [i] ;
38 if (p == Ap [j+1])
head-- ;
40 if (found)
for (p =
head ; p >= 0 ; p--) jmatch [is [p]] = js [p] ;
46 int i, j, k, n, m, p, n2 = 0, m2 = 0, *Ap, *jimatch, *w, *cheap, *js, *is,
47 *ps, *Ai, *
Cp, *jmatch, *imatch, *q ;
49 if (!
CS_CSC (A))
return (NULL) ;
50 n = A->
n ; m = A->
m ; Ap = A->
p ; Ai = A->
i ;
51 w = jimatch = (
int*)
cs_calloc (m+n,
sizeof (
int)) ;
52 if (!jimatch)
return (NULL) ;
53 for (k = 0, j = 0 ; j < n ; j++)
55 n2 += (Ap [j] < Ap [j+1]) ;
56 for (p = Ap [j] ; p < Ap [j+1] ; p++)
64 jmatch = jimatch ; imatch = jimatch + m ;
65 for (i = 0 ; i < k ; i++) jmatch [i] = i ;
66 for ( ; i < m ; i++) jmatch [i] = -1 ;
67 for (j = 0 ; j < k ; j++) imatch [j] = j ;
68 for ( ; j < n ; j++) imatch [j] = -1 ;
69 return (
cs_idone (jimatch, NULL, NULL, 1)) ;
71 for (i = 0 ; i < m ; i++) m2 += w [i] ;
73 if (!C)
return (
cs_idone (jimatch, (m2 < n2) ? C : NULL, NULL, 0)) ;
74 n = C->
n ; m = C->
m ; Cp = C->
p ;
75 jmatch = (m2 < n2) ? jimatch + n : jimatch ;
76 imatch = (m2 < n2) ? jimatch : jimatch + m ;
78 if (!w)
return (
cs_idone (jimatch, (m2 < n2) ? C : NULL, w, 0)) ;
79 cheap = w + n ; js = w + 2*n ; is = w + 3*n ; ps = w + 4*n ;
80 for (j = 0 ; j < n ; j++) cheap [j] = Cp [j] ;
81 for (j = 0 ; j < n ; j++) w [j] = -1 ;
82 for (i = 0 ; i < m ; i++) jmatch [i] = -1 ;
84 for (k = 0 ; k < n ; k++)
86 cs_augment (q ? q [k]: k, C, jmatch, cheap, w, js, is, ps) ;
89 for (j = 0 ; j < n ; j++) imatch [j] = -1 ;
90 for (i = 0 ; i < m ; i++) if (jmatch [i] >= 0) imatch [jmatch [i]] = i ;
91 return (
cs_idone (jimatch, (m2 < n2) ? C : NULL, w, 1)) ;
static void cs_augment(int k, const cs *A, int *jmatch, int *cheap, int *w, int *js, int *is, int *ps)
int * cs_maxtrans(const cs *A, int seed)
cs * cs_transpose(const cs *A, int values)
int * cs_idone(int *p, cs *C, void *w, int ok)
void * cs_calloc(int n, size_t size)
void * cs_malloc(int n, size_t size)
SegmentReturnType head(Index vecSize)
int * cs_randperm(int n, int seed)