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 /* Construct a subgraph of a graph. */
11 /* This reuses the graph storage, and can be undone. */
12
make_subgraph(graph,subgraph,subnvtxs,psubnedges,assignment,set,glob2loc,loc2glob,degree,using_ewgts)13 void make_subgraph(graph, subgraph, subnvtxs, psubnedges, assignment, set,
14 glob2loc, loc2glob, degree, using_ewgts)
15 struct vtx_data **graph; /* graph data structure */
16 struct vtx_data **subgraph; /* subgraph data structure */
17 int subnvtxs; /* number of vtxs in subgraph */
18 int *psubnedges; /* ptr to number of edges in subgraph */
19 short *assignment; /* values designating subgraph inclusion */
20 int set; /* assignment value indicating inclusion */
21 int *glob2loc; /* mapping from graph to subgraph numbering */
22 int *loc2glob; /* mapping from subgraph to graph numbering */
23 short *degree; /* degrees of vertices in graph */
24 int using_ewgts; /* are edge weights being used? */
25 {
26 struct vtx_data *subgptr; /* loops through subgraph */
27 float *fptr; /* loops through edge weights */
28 int *iptr; /* loops through edge list */
29 float tempwgt; /* weight of vertex being swapped */
30 double ewgtsum; /* sum of weights of subgraph edges */
31 int subnedges; /* number of edges in subgraph */
32 int neighbor; /* neighbor vertex in graph */
33 int newnedges; /* vertex degree in subgraph */
34 int tempvtx; /* vertex number being swapped */
35 int i, j; /* loop counter */
36
37 subnedges = 0;
38 for (i = 1; i <= subnvtxs; i++) {
39 /* First get the vertices organized properly. */
40 subgptr = subgraph[i] = graph[loc2glob[i]];
41 newnedges = degree[i] = subgptr->nedges;
42
43 /* Now work on the edges. */
44 subgptr->edges[0] = i;
45 ewgtsum = 0;
46 /* Move all deactivated edges to the end of the list. */
47 iptr = subgptr->edges + 1;
48 if (using_ewgts)
49 fptr = subgptr->ewgts + 1;
50 for (j = 1; j < newnedges;) {
51 neighbor = *iptr;
52 if (assignment[neighbor] == set) { /* Keep vertex in edge list. */
53 subgptr->edges[j] = glob2loc[neighbor];
54 if (using_ewgts)
55 ewgtsum += *fptr++;
56 j++;
57 iptr++;
58 }
59 else { /* Move vertex to back of edge list. */
60 --newnedges;
61 tempvtx = subgptr->edges[newnedges];
62 subgptr->edges[newnedges] = neighbor;
63 *iptr = tempvtx;
64 if (using_ewgts) {
65 tempwgt = subgptr->ewgts[newnedges];
66 subgptr->ewgts[newnedges] = *fptr;
67 *fptr = tempwgt;
68 }
69 }
70 }
71 subgptr->nedges = newnedges;
72 subnedges += newnedges;
73 if (using_ewgts)
74 subgptr->ewgts[0] = -ewgtsum;
75 }
76 *psubnedges = (subnedges - subnvtxs) / 2;
77 }
78
79
80 /* Undo the construction of the subgraph. */
remake_graph(subgraph,subnvtxs,loc2glob,degree,using_ewgts)81 void remake_graph(subgraph, subnvtxs, loc2glob, degree, using_ewgts)
82 struct vtx_data **subgraph; /* subgraph data structure */
83 int subnvtxs; /* number of vtxs in subgraph */
84 int *loc2glob; /* mapping from subgraph to graph numbering */
85 short *degree; /* degrees of vertices in graph */
86 int using_ewgts; /* are edge weights being used? */
87 {
88 struct vtx_data *subgptr; /* loops through subgraph */
89 float *fptr; /* loops through edge weights */
90 int *iptr; /* loops through adjacency list */
91 double ewgtsum; /* sum of weights of subgraph edges */
92 int nedges; /* vertex degree in subgraph */
93 int i, j; /* loop counter */
94
95 /* For each vertex in subgraph, expand the edge set back out. */
96 for (i = 1; i <= subnvtxs; i++) {
97 subgptr = subgraph[i];
98 subgptr->edges[0] = loc2glob[i];
99 nedges = subgptr->nedges;
100 /* Change edges back to global numbering system. */
101 iptr = subgptr->edges;
102 for (j = nedges - 1; j; j--) {
103 iptr++;
104 *iptr = loc2glob[*iptr];
105 }
106 subgptr->nedges = degree[i];
107
108 /* Now get the diagonal value right. */
109 if (using_ewgts) {
110 ewgtsum = 0;
111 fptr = subgptr->ewgts;
112 for (j = degree[i] - 1; j; j--)
113 ewgtsum += *(++fptr);
114 subgptr->ewgts[0] = -ewgtsum;
115 }
116 }
117 }
118