1 /* This software was developed by Bruce Hendrickson and Robert Leland *
2 * at Sandia National Laboratories under US Department of Energy *
3 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
4
5 #include <stdio.h>
6 #include "defs.h"
7 #include "structs.h"
8
9
10 /* Find a maximal matching in a graph using one of several algorithms. */
11
maxmatch(graph,nvtxs,nedges,mflag,using_ewgts,igeom,coords)12 int maxmatch(graph, nvtxs, nedges, mflag, using_ewgts, igeom, coords)
13 struct vtx_data **graph; /* array of vtx data for graph */
14 int nvtxs; /* number of vertices in graph */
15 int nedges; /* number of edges in graph */
16 int *mflag; /* flag indicating vtx selected or not */
17 int using_ewgts; /* are edge weights being used? */
18 int igeom; /* geometric dimensionality */
19 float **coords; /* coordinates for each vertex */
20 {
21 extern int DEBUG_COARSEN; /* debug output for coarsening? */
22 extern int MATCH_TYPE; /* which matching routine to use */
23 int nmerged; /* number of matching edges found */
24 int maxmatch1(), maxmatch2(), maxmatch3(), maxmatch4();
25 int maxmatch5();
26
27 if (MATCH_TYPE == 1) { /* Dumb, fast routine. */
28 nmerged = maxmatch1(graph, nvtxs, mflag, using_ewgts);
29 }
30
31 else if (MATCH_TYPE == 2) { /* More random but somewhat slower. */
32 nmerged = maxmatch2(graph, nvtxs, mflag, using_ewgts);
33 }
34
35 else if (MATCH_TYPE == 3) { /* Much more random but slower still. */
36 nmerged = maxmatch3(graph, nvtxs, mflag, using_ewgts);
37 }
38
39 else if (MATCH_TYPE == 4) { /* Truly random but very slow. */
40 nmerged = maxmatch4(graph, nvtxs, nedges, mflag, using_ewgts);
41 }
42 else if (MATCH_TYPE == 5) { /* Geometric nearness. */
43 nmerged = maxmatch5(graph, nvtxs, mflag, igeom, coords);
44 }
45
46 if (DEBUG_COARSEN > 0) {
47 printf("Number of matching edges = %d\n", nmerged);
48 }
49
50 return (nmerged);
51 }
52