1
/* Copyright 2004,2007 ENSEIRB, INRIA & CNRS
3
** This file is part of the Scotch software package for static mapping,
4
** graph partitioning and sparse matrix ordering.
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".
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
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.
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.
32
/************************************************************/
34
/** NAME : hgraph_order_hf.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module orders a subgraph using **/
39
/** the block-oriented Halo Approximate **/
40
/** (Multiple) Minimum Fill algorithm, **/
41
/** with super-variable accounting **/
42
/** R2HAMDf4 v2.0). **/
44
/** DATES : # Version 3.4 : from : 15 may 2001 **/
45
/** to : 23 nov 2001 **/
46
/** # Version 4.0 : from : 10 jan 2003 **/
47
/** to : 24 jan 2004 **/
48
/** # Version 5.0 : from : 10 sep 2007 **/
49
/** to : 10 sep 2007 **/
51
/************************************************************/
54
** The defines and includes.
57
#define HGRAPH_ORDER_HF
64
#include "hall_order_hf.h"
65
#include "hall_order_hx.h"
66
#include "hgraph_order_hf.h"
67
#include "hgraph_order_hx.h"
68
#include "hgraph_order_si.h"
70
/*****************************/
72
/* This is the main routine. */
74
/*****************************/
76
/* This routine performs the ordering.
78
** - 0 : if the ordering could be computed.
84
const Hgraph * restrict const grafptr,
85
Order * restrict const ordeptr,
86
const Gnum ordenum, /*+ Zero-based ordering number +*/
87
OrderCblk * restrict const cblkptr, /*+ Multiple column-block +*/
88
const HgraphOrderHfParam * restrict const paraptr)
91
Gnum * restrict petab;
94
Gnum * restrict iwtab;
95
Gnum * restrict lentab;
96
Gnum * restrict nvartab;
97
Gnum * restrict elentab;
98
Gnum * restrict lasttab;
99
Gnum * restrict leaftab;
100
Gnum * restrict secntab; /* Array of index to first secondary variable */
101
Gnum * restrict nexttab; /* Array of index of next principal variable */
102
Gnum * restrict frsttab;
103
Gnum * restrict headtab; /* Head array : nbbuck = 2 * n */
105
Gnum n; /* Number of nodes to order (with halo or not) */
108
if (grafptr->s.vertnbr < paraptr->colmin) /* If graph is too small, order simply */
109
return (hgraphOrderSi (grafptr, ordeptr, ordenum, cblkptr));
111
n = grafptr->s.vertnbr;
113
iwlen = (Gnum) ((double) grafptr->s.edgenbr * HGRAPHORDERHFCOMPRAT) + 32;
114
if (iwlen < n) /* Prepare to re-use array */
117
if (memAllocGroup ((void **) (void *)
118
&petab, (size_t) (n * sizeof (Gnum)),
119
&iwtab, (size_t) (iwlen * sizeof (Gnum)),
120
&lentab, (size_t) (n * sizeof (Gnum)),
121
&nvartab, (size_t) (n * sizeof (Gnum)),
122
&elentab, (size_t) (n * sizeof (Gnum)),
123
&lasttab, (size_t) (n * sizeof (Gnum)),
124
&leaftab, (size_t) (n * sizeof (Gnum)),
125
&frsttab, (size_t) (n * sizeof (Gnum)),
126
&secntab, (size_t) (n * sizeof (Gnum)),
127
&nexttab, (size_t) (n * sizeof (Gnum)),
128
&headtab, (size_t) ((nbbuck + 2) * sizeof (Gnum)), NULL) == NULL) {
129
errorPrint ("hgraphOrderHf: out of memory");
133
hgraphOrderHxFill (grafptr, petab, lentab, iwtab, elentab, &pfree);
135
hallOrderHfR2hamdf4 (n, 0, nbbuck, iwlen, petab, pfree, /* No elements here */
136
lentab, iwtab, nvartab, elentab, lasttab, &ncmpa,
137
leaftab, secntab, nexttab, frsttab, headtab);
139
errorPrint ("hgraphOrderHf: internal error");
140
memFree (petab); /* Free group leader */
144
o = hallOrderHxBuild (grafptr->s.baseval, n, grafptr->vnohnbr,
145
grafptr->s.vnumtax, ordeptr, cblkptr,
146
nvartab - grafptr->s.baseval,
147
lentab - grafptr->s.baseval,
148
petab - grafptr->s.baseval,
149
frsttab - grafptr->s.baseval,
150
nexttab - grafptr->s.baseval,
151
secntab - grafptr->s.baseval,
152
iwtab - grafptr->s.baseval,
153
elentab - grafptr->s.baseval,
154
ordeptr->peritab + ordenum, /* Use given inverse permutation as inverse permutation space, never based */
156
paraptr->colmin, paraptr->colmax, (float) paraptr->fillrat);
158
memFree (petab); /* Free group leader */
added
removed
src/libscotch/hgraph_order_hf.c
