1 /* Copyright 2004,2007,2010,2012,2014 IPB, Universite de Bordeaux, INRIA & CNRS
2 **
3 ** This file is part of the Scotch software package for static mapping,
4 ** graph partitioning and sparse matrix ordering.
5 **
6 ** This software is governed by the CeCILL-C license under French law
7 ** and abiding by the rules of distribution of free software. You can
8 ** use, modify and/or redistribute the software under the terms of the
9 ** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
10 ** URL: "http://www.cecill.info".
11 **
12 ** As a counterpart to the access to the source code and rights to copy,
13 ** modify and redistribute granted by the license, users are provided
14 ** only with a limited warranty and the software's author, the holder of
15 ** the economic rights, and the successive licensors have only limited
16 ** liability.
17 **
18 ** In this respect, the user's attention is drawn to the risks associated
19 ** with loading, using, modifying and/or developing or reproducing the
20 ** software by the user in light of its specific status of free software,
21 ** that may mean that it is complicated to manipulate, and that also
22 ** therefore means that it is reserved for developers and experienced
23 ** professionals having in-depth computer knowledge. Users are therefore
24 ** encouraged to load and test the software's suitability as regards
25 ** their requirements in conditions enabling the security of their
26 ** systems and/or data to be ensured and, more generally, to use and
27 ** operate it in the same conditions as regards security.
28 **
29 ** The fact that you are presently reading this means that you have had
30 ** knowledge of the CeCILL-C license and that you accept its terms.
31 */
32 /************************************************************/
33 /** **/
34 /** NAME : hgraph_order_nd.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module orders graphs using the **/
39 /** nested dissection algorithm. **/
40 /** **/
41 /** DATES : # Version 3.2 : from : 17 oct 1996 **/
42 /** to : 21 aug 1998 **/
43 /** # Version 3.3 : from : 02 oct 1998 **/
44 /** to 13 mar 1999 **/
45 /** # Version 4.0 : from : 03 jan 2002 **/
46 /** to 24 dec 2004 **/
47 /** # Version 5.0 : from : 19 dec 2006 **/
48 /** to 25 jul 2007 **/
49 /** # Version 5.1 : from : 24 oct 2010 **/
50 /** to 24 oct 2010 **/
51 /** # Version 6.0 : from : 17 oct 2012 **/
52 /** to 05 aug 2014 **/
53 /** **/
54 /************************************************************/
55
56 /*
57 ** The defines and includes.
58 */
59
60 #define HGRAPH_ORDER_ND
61
62 #include "module.h"
63 #include "common.h"
64 #include "parser.h"
65 #include "graph.h"
66 #include "order.h"
67 #include "hgraph.h"
68 #include "hgraph_order_nd.h"
69 #include "hgraph_order_st.h"
70 #include "vgraph.h"
71 #include "vgraph_separate_st.h"
72
73 /*****************************/
74 /* */
75 /* This is the main routine. */
76 /* */
77 /*****************************/
78
79 /* This routine performs the ordering.
80 ** It returns:
81 ** - 0 : if the ordering could be computed.
82 ** - !0 : on error.
83 */
84
85 int
hgraphOrderNd(const Hgraph * restrict const grafptr,Order * restrict const ordeptr,const Gnum ordenum,OrderCblk * restrict const cblkptr,const HgraphOrderNdParam * restrict const paraptr)86 hgraphOrderNd (
87 const Hgraph * restrict const grafptr,
88 Order * restrict const ordeptr,
89 const Gnum ordenum,
90 OrderCblk * restrict const cblkptr,
91 const HgraphOrderNdParam * restrict const paraptr)
92 {
93 Hgraph indgrafdat; /* Halo graph data */
94 Gnum * vspvnumptr[3]; /* Pointers to vertex lists to fill */
95 VertList vsplisttab[3]; /* Array of separated part lists */
96 Vgraph vspgrafdat; /* Vertex separation graph data */
97 Gnum vspvertnum; /* Current vertex in separation graph */
98 int o;
99
100 hgraphUnhalo (grafptr, &vspgrafdat.s); /* Keep only non-halo vertices for separation */
101
102 if ((vspgrafdat.frontab = (Gnum *) memAlloc (vspgrafdat.s.vertnbr * sizeof (Gnum))) == NULL) {
103 errorPrint ("hgraphOrderNd: out of memory (1)");
104 return (1);
105 }
106 if ((vspgrafdat.parttax = (GraphPart *) memAlloc (vspgrafdat.s.vertnbr * sizeof (GraphPart))) == NULL) {
107 errorPrint ("hgraphOrderNd: out of memory (2)");
108 memFree (vspgrafdat.frontab);
109 return (1);
110 }
111 memSet (vspgrafdat.parttax, 0, vspgrafdat.s.vertnbr * sizeof (GraphPart)); /* Set all vertices to part 0 */
112 vspgrafdat.parttax -= vspgrafdat.s.baseval;
113 vspgrafdat.fronnbr = 0;
114 vspgrafdat.compload[0] = vspgrafdat.s.velosum;
115 vspgrafdat.compload[1] = 0;
116 vspgrafdat.compload[2] = 0;
117 vspgrafdat.comploaddlt = vspgrafdat.s.velosum;
118 vspgrafdat.compsize[0] = vspgrafdat.s.vertnbr;
119 vspgrafdat.compsize[1] = 0;
120 vspgrafdat.fronnbr = 0;
121 vspgrafdat.levlnum = grafptr->levlnum; /* Set level of separation graph as level of halo graph */
122
123 if (vgraphSeparateSt (&vspgrafdat, paraptr->sepstrat) != 0) { /* Separate vertex-separation graph */
124 vgraphExit (&vspgrafdat);
125 return (1);
126 }
127
128 if ((vspgrafdat.compsize[0] == 0) || /* If could not separate more */
129 (vspgrafdat.compsize[1] == 0)) {
130 vgraphExit (&vspgrafdat); /* Free useless space */
131 hgraphOrderSt (grafptr, ordeptr, ordenum, cblkptr, paraptr->ordstratlea); /* Order this leaf */
132 return (0); /* Leaf has been processed */
133 }
134
135 vsplisttab[0].vnumnbr = vspgrafdat.compsize[0]; /* Build vertex lists within frontier array */
136 vsplisttab[0].vnumtab = vspgrafdat.frontab + vspgrafdat.fronnbr;
137 vsplisttab[1].vnumnbr = vspgrafdat.compsize[1];
138 vsplisttab[1].vnumtab = vsplisttab[0].vnumtab + vsplisttab[0].vnumnbr;
139 vsplisttab[2].vnumnbr = vspgrafdat.fronnbr;
140 vsplisttab[2].vnumtab = vspgrafdat.frontab;
141 vspvnumptr[0] = vsplisttab[0].vnumtab;
142 vspvnumptr[1] = vsplisttab[1].vnumtab;
143 vspvnumptr[2] = vsplisttab[2].vnumtab;
144 for (vspvertnum = vspgrafdat.s.baseval; vspvertnum < vspgrafdat.s.vertnnd; vspvertnum ++) { /* Fill lists */
145 *vspvnumptr[vspgrafdat.parttax[vspvertnum]] ++ = vspvertnum;
146 #ifdef SCOTCH_DEBUG_HGRAPH2
147 if (vspgrafdat.parttax[vspvertnum] != 2) { /* If vertex does not separate */
148 Gnum vspedgenum;
149 GraphPart vsppartnum;
150
151 vsppartnum = 1 - vspgrafdat.parttax[vspvertnum]; /* Get opposite part value */
152 for (vspedgenum = vspgrafdat.s.verttax[vspvertnum];
153 vspedgenum < vspgrafdat.s.vendtax[vspvertnum]; vspedgenum ++) {
154 if (vspgrafdat.parttax[vspgrafdat.s.edgetax[vspedgenum]] == vsppartnum) { /* If an edge crosses the separator */
155 errorPrint ("hgraphOrderNd: internal error (1)");
156 vgraphExit (&vspgrafdat);
157 return (1);
158 }
159 }
160 }
161 #endif /* SCOTCH_DEBUG_HGRAPH2 */
162 }
163 #ifdef SCOTCH_DEBUG_HGRAPH2
164 if ((vspvnumptr[0] != vsplisttab[0].vnumtab + vsplisttab[0].vnumnbr) ||
165 (vspvnumptr[1] != vsplisttab[1].vnumtab + vsplisttab[1].vnumnbr) ||
166 (vspvnumptr[2] != vsplisttab[2].vnumtab + vsplisttab[2].vnumnbr)) {
167 errorPrint ("hgraphOrderNd: internal error (2)");
168 vgraphExit (&vspgrafdat);
169 return (1);
170 }
171 #endif /* SCOTCH_DEBUG_HGRAPH2 */
172
173 memFree (vspgrafdat.parttax + vspgrafdat.s.baseval); /* Free useless space */
174 #ifdef SCOTCH_DEBUG_HGRAPH2
175 vspgrafdat.parttax = NULL; /* Will cause bug if re-read */
176 #endif /* SCOTCH_DEBUG_HGRAPH2 */
177
178 cblkptr->typeval = ORDERCBLKNEDI; /* Node becomes a nested dissection node */
179 if ((cblkptr->cblktab = (OrderCblk *) memAlloc (3 * sizeof (OrderCblk))) == NULL) {
180 errorPrint ("hgraphOrderNd: out of memory (2)");
181 memFree (vspgrafdat.frontab); /* Free remaining space */
182 return (1);
183 }
184 cblkptr->cblktab[0].typeval = ORDERCBLKOTHR; /* Build column blocks */
185 cblkptr->cblktab[0].vnodnbr = vsplisttab[0].vnumnbr;
186 cblkptr->cblktab[0].cblknbr = 0;
187 cblkptr->cblktab[0].cblktab = NULL;
188 cblkptr->cblktab[1].typeval = ORDERCBLKOTHR;
189 cblkptr->cblktab[1].vnodnbr = vsplisttab[1].vnumnbr;
190 cblkptr->cblktab[1].cblknbr = 0;
191 cblkptr->cblktab[1].cblktab = NULL;
192
193 if (vsplisttab[2].vnumnbr != 0) { /* If separator not empty */
194 cblkptr->cblknbr = 3; /* It is a three-cell tree node */
195 ordeptr->cblknbr += 2; /* Two more column blocks created */
196 ordeptr->treenbr += 3; /* Three more tree nodes created */
197
198 cblkptr->cblktab[2].typeval = ORDERCBLKOTHR;
199 cblkptr->cblktab[2].vnodnbr = vsplisttab[2].vnumnbr;
200 cblkptr->cblktab[2].cblknbr = 0;
201 cblkptr->cblktab[2].cblktab = NULL;
202
203 if (graphInduceList (&grafptr->s, &vsplisttab[2], &indgrafdat.s) != 0) { /* Perform non-halo induction for separator, as it will get highest numbers */
204 errorPrint ("hgraphOrderNd: cannot build induced subgraph (1)");
205 memFree (vspgrafdat.frontab); /* Free remaining space */
206 return (1);
207 }
208 indgrafdat.vnohnbr = indgrafdat.s.vertnbr; /* Fill halo graph structure of non-halo graph */
209 indgrafdat.vnohnnd = indgrafdat.s.vertnnd;
210 indgrafdat.vnhdtax = indgrafdat.s.vendtax;
211 indgrafdat.vnlosum = indgrafdat.s.velosum;
212 indgrafdat.enohnbr = indgrafdat.s.edgenbr;
213 indgrafdat.enohsum = indgrafdat.s.edlosum;
214 indgrafdat.levlnum = grafptr->levlnum; /* Separator graph is at level of original graph */
215
216 o = hgraphOrderSt (&indgrafdat, ordeptr, ordenum + vsplisttab[0].vnumnbr + vsplisttab[1].vnumnbr,
217 cblkptr->cblktab + 2, paraptr->ordstratsep);
218 hgraphExit (&indgrafdat);
219 }
220 else { /* Separator is empty */
221 cblkptr->cblknbr = 2; /* It is a two-cell tree node */
222 ordeptr->cblknbr ++; /* One more column block created */
223 ordeptr->treenbr += 2; /* Two more tree nodes created */
224 o = 0; /* No separator ordering computed */
225 }
226 if (o == 0) {
227 if ((hgraphInduceList (grafptr, &vsplisttab[0], vsplisttab[2].vnumnbr + grafptr->s.vertnbr - grafptr->vnohnbr, &indgrafdat)) != 0) {
228 errorPrint ("hgraphOrderNd: cannot build induced subgraph (2)");
229 memFree (vspgrafdat.frontab); /* Free remaining space */
230 return (1);
231 }
232 o = hgraphOrderNd (&indgrafdat, ordeptr, ordenum, cblkptr->cblktab, paraptr);
233 hgraphExit (&indgrafdat);
234 }
235 if (o == 0) {
236 if ((hgraphInduceList (grafptr, &vsplisttab[1], vsplisttab[2].vnumnbr + grafptr->s.vertnbr - grafptr->vnohnbr, &indgrafdat)) != 0) {
237 errorPrint ("hgraphOrderNd: cannot build induced subgraph (3)");
238 memFree (vspgrafdat.frontab); /* Free remaining space */
239 return (1);
240 }
241 o = hgraphOrderNd (&indgrafdat, ordeptr, ordenum + vsplisttab[0].vnumnbr, cblkptr->cblktab + 1, paraptr);
242 hgraphExit (&indgrafdat);
243 }
244
245 memFree (vspgrafdat.frontab); /* Free remaining space */
246
247 return (o);
248 }
249