42 int num_shared_neighbors = 0;
44 for (j = 0; j <
graph[u].nedges; j++) {
48 num_shared_neighbors++;
55 return ((
double) num_shared_neighbors) / (
graph[v].nedges +
57 num_shared_neighbors);
63 for (j = 0; j <
graph[vtx].nedges; j++) {
64 vtx_vec[
graph[vtx].edges[j]] = fabsf(
graph[vtx].ewgts[j]);
67 for (j = 0; j <
graph[vtx].nedges; j++) {
68 vtx_vec[
graph[vtx].edges[j]] = 1;
78 for (j = 0; j <
graph[vtx].nedges; j++) {
79 vtx_vec[
graph[vtx].edges[j]] = 1;
86 for (j = 0; j <
graph[vtx].nedges; j++) {
87 vtx_vec[
graph[vtx].edges[j]] = 0;
97 for (i = 1; i <
graph[node1].nedges; i++) {
98 u =
graph[node1].edges[i];
102 for (j = 1; j <
graph[u].nedges; j++) {
103 v =
graph[u].edges[j];
107 for (k = 1; k <
graph[v].nedges; k++) {
108 if (
graph[v].edges[k] == node2) {
128 return hypot(x_v - x_u, y_v - y_u);
156 float max_norm_edge_weight;
158 double *matchability =
gv_calloc(nvtxs,
sizeof(
double));
160 double closest_val = -1, val;
161 int closest_neighbor;
162 float *vtx_vec =
gv_calloc(nvtxs,
sizeof(
float));
163 float *weighted_vtx_vec =
gv_calloc(nvtxs,
sizeof(
float));
166 double avg_edge_len = 0, avg_deg_2 = 0;
169 for (i = 0; i < nvtxs; i++) {
170 avg_deg_2 +=
graph[i].nedges;
171 for (j = 1; j <
graph[i].nedges; j++) {
172 avg_edge_len +=
ddist(geom_graph, i,
graph[i].edges[j]);
178 avg_deg_2 *= avg_deg_2;
184 max_norm_edge_weight = -1;
185 for (i = 0; i < nvtxs; i++) {
186 inv_size = sqrt(1.0 / geom_graph[i].size);
187 for (j = 1; j <
graph[i].nedges; j++) {
188 if (
graph[i].ewgts[j] * inv_size /
189 sqrt((
float) geom_graph[
graph[i].edges[j]].size) >
190 max_norm_edge_weight) {
191 max_norm_edge_weight =
192 (float) (
graph[i].ewgts[j] * inv_size /
194 geom_graph[
graph[i].edges[j]].size));
199 max_norm_edge_weight = 1;
203 iptr = order =
gv_calloc(nvtxs,
sizeof(
int));
205 for (i = 0; i < nvtxs; i++) {
215 for (i = 0; i < nvtxs; i++) {
217 matchability[vtx] =
graph[vtx].nedges;
218 matchability[vtx] += geom_graph[vtx].
size;
220 for (j = 1; j <
graph[vtx].nedges; j++) {
223 ddist(geom_graph, vtx,
224 graph[vtx].edges[j]) / avg_edge_len);
226 matchability[vtx] += min_edge_len;
227 matchability[vtx] += ((double) rand()) / RAND_MAX;
233 for (i = 0; i < nvtxs; i++) {
236 for (i = 0; i < nvtxs; i++) {
237 weighted_vtx_vec[i] = 0;
241 for (i = 0; i < nvtxs; i++) {
243 if (mflag[vtx] >= 0) {
246 inv_size = sqrt(1.0 / geom_graph[vtx].size);
249 closest_neighbor = -1;
259 for (j = 1; j < geom_graph[vtx].
nedges; j++) {
276 B * avg_deg_2 / (
graph[vtx].nedges *
285 (weighted_vtx_vec[
neighbor] * inv_size /
286 sqrt((
float) geom_graph[
neighbor].size)) /
287 max_norm_edge_weight;
291 if (val > closest_val || closest_neighbor == -1) {
297 if (closest_neighbor != -1) {
298 mflag[vtx] = closest_neighbor;
299 mflag[closest_neighbor] = vtx;
308 free(weighted_vtx_vec);
322 for (i = 0; i < nvtxs; i++) {
326 cv2v[2 * j + 1] = -1;
328 }
else if (mflag[i] > i) {
332 cv2v[2 * j + 1] = mflag[i];
351 int *index =
gv_calloc(cnvtxs,
sizeof(
int));
360 edges =
gv_calloc(2 * maxCnedges + cnvtxs,
sizeof(
int));
361 eweights =
gv_calloc(2 * maxCnedges + cnvtxs,
sizeof(
float));
365 for (cv = 0; cv < cnvtxs; cv++) {
369 cgraph[cv].
edges = edges;
370 cgraph[cv].
ewgts = eweights;
374 for (j = 1; j <
graph[v].nedges; j++) {
377 intra_weight = 2 *
graph[v].ewgts[j];
383 cgraph[cv].
ewgts[cv_nedges] =
graph[v].ewgts[j];
392 if ((v = cv2v[2 * cv + 1]) != -1) {
393 for (j = 1; j <
graph[v].nedges; j++) {
400 cgraph[cv].
ewgts[cv_nedges] =
graph[v].ewgts[j];
407 cgraph[cv].
ewgts[0] +=
graph[v].ewgts[0] + intra_weight;
409 cgraph[cv].
nedges = cv_nedges;
410 cgraph[cv].
edges[0] = cv;
412 eweights += cv_nedges;
413 cnedges += cv_nedges;
415 for (j = 1; j < cgraph[cv].
nedges; j++)
416 index[cgraph[cv].edges[j]] = 0;
419 int internal_weight = 0;
421 for (cv = 0; cv < cnvtxs; cv++) {
423 cgraph[cv].
edges = edges;
424 cgraph[cv].
ewgts = eweights;
428 for (j = 1; j <
graph[v].nedges; j++) {
437 cgraph[cv].
ewgts[cv_nedges] = -1;
443 cgraph[cv].
ewgts[0] = (float)
graph[v].edges[0];
444 if ((v = cv2v[2 * cv + 1]) != -1) {
445 for (j = 1; j <
graph[v].nedges; j++) {
452 cgraph[cv].
ewgts[cv_nedges] = -1;
459 cgraph[cv].
ewgts[0] +=
460 (float)
graph[v].edges[0] - internal_weight;
465 cgraph[cv].
nedges = cv_nedges;
466 cgraph[cv].
edges[0] = cv;
468 eweights += cv_nedges;
469 cnedges += cv_nedges;
471 for (j = 1; j < cgraph[cv].
nedges; j++)
472 index[cgraph[cv].edges[j]] = 0;
497 int *index =
gv_calloc(cnvtxs,
sizeof(
int));
505 edges =
gv_calloc(2 * cnedges + cnvtxs,
sizeof(
int));
507 for (cv = 0; cv < cnvtxs; cv++) {
509 cgraph[cv].
edges = edges;
513 for (j = 1; j <
graph[v].nedges; j++) {
527 if ((v = cv2v[2 * cv + 1]) != -1) {
528 for (j = 1; j <
graph[v].nedges; j++) {
541 graph[v].size *
graph[v].x_coord) / (cgraph[cv].size +
545 graph[v].size *
graph[v].y_coord) / (cgraph[cv].size +
549 cgraph[cv].
nedges = cv_nedges;
550 cgraph[cv].
edges[0] = cv;
553 for (j = 1; j < cgraph[cv].
nedges; j++)
554 index[cgraph[cv].edges[j]] = 0;
594 nmerged =
maxmatch(
graph, geom_graph, nvtxs, mflag, dist2_limit);
600 *cnp = cnvtxs = nvtxs - nmerged;
602 *v2cvp = v2cv =
gv_calloc(nvtxs,
sizeof(
int));
603 *cv2vp = cv2v =
gv_calloc(2 * cnvtxs,
sizeof(
int));
627 for (i = 0; i < n; i++) {
631 for (j = 0; j <
graph[i].nedges; j++) {
632 edges[j] =
graph[i].edges[j];
634 edges +=
graph[i].nedges;
636 for (j = 0; j <
graph[i].nedges; j++) {
637 ewgts[j] =
graph[i].ewgts[j];
639 ewgts +=
graph[i].nedges;
655 for (i = 0; i < n; i++) {
658 for (j = 0; j <
graph[i].nedges; j++) {
659 edges[j] =
graph[i].edges[j];
661 edges +=
graph[i].nedges;
671 int cngeom_edges = ngeom_edges;
675 static const int min_nvtxs = 20;
676 int nlevels =
MAX(5, 10 * (
int) log((
float) (nvtxs / min_nvtxs)));
687 hierarchy->
nvtxs[0] = nvtxs;
691 hierarchy->
nvtxs[cur_level] > min_nvtxs
692 && cur_level < 50 ; cur_level++) {
693 if (cur_level == nlevels - 1) {
705 ngeom_edges = cngeom_edges;
707 (hierarchy->
graphs[cur_level],
709 hierarchy->
nvtxs[cur_level], hierarchy->
nedges[cur_level],
710 ngeom_edges, &hierarchy->
graphs[cur_level + 1],
712 &hierarchy->
nvtxs[cur_level + 1],
713 &hierarchy->
nedges[cur_level + 1], &cngeom_edges,
714 &hierarchy->
v2cv[cur_level], &hierarchy->
cv2v[cur_level + 1],
718 hierarchy->
nlevels = cur_level + 1;
721 for (i = 0; i < hierarchy->
nlevels; i++) {
723 for (j = 0; j < hierarchy->
nvtxs[i]; j++) {
738 for (i = 1; i < num_foci; i++) {
770 n = hierarchy->
nvtxs[min_level];
774 distances =
gv_calloc(n,
sizeof(
double));
775 for (i = 0; i < n; i++) {
788 group_size =
parms->num_fine_nodes * num_foci;
790 for (i = 0; i < n; i++) {
792 if (i > thresh && level < hierarchy->nlevels - 1) {
794 group_size = (int) (group_size *
parms->coarsening_rate);
795 thresh += group_size;
797 graph[vtx].active_level = level;
807 for (level = min_level + 1; level < hierarchy->
nlevels; level++) {
810 cv2v = hierarchy->
cv2v[level];
811 n = hierarchy->
nvtxs[level];
812 for (i = 0; i < n; i++) {
816 if (
graph[v].active_level < level
817 ||
graph[u].active_level < level) {
821 graph[v].active_level =
822 MIN(
graph[v].active_level, level - 1);
823 graph[u].active_level =
824 MIN(
graph[u].active_level, level - 1);
838 for (level = hierarchy->
nlevels - 1; level > 0; level--) {
841 cv2v = hierarchy->
cv2v[level];
842 n = hierarchy->
nvtxs[level];
843 for (i = 0; i < n; i++) {
844 if (cgraph[i].active_level < level) {
868 int level,
double x,
double y,
869 double closest_dist,
int *closest_node,
870 int *closest_node_level)
878 double delx = x -
graph[
node].physical_x_coord;
879 double dely = y -
graph[
node].physical_y_coord;
880 double dist = delx*delx + dely*dely;
882 if (
dist < closest_dist)
885 *closest_node =
node;
886 *closest_node_level = level;
895 level - 1, x, y, closest_dist, closest_node,
898 if (hierarchy->
cv2v[level][2 *
node + 1] >= 0) {
901 hierarchy->
cv2v[level][2 *
node + 1],
902 level - 1, x, y, closest_dist,
903 closest_node, closest_node_level);
916 while (level > cur_level)
930 int *closest_fine_node)
932 int i, closest_node, closest_node_level;
933 int top_level = hierarchy->
nlevels - 1;
934 double min_dist = 1e20;
936 for (i = 0; i < hierarchy->
nvtxs[top_level]; i++)
938 min_dist =
findClosestActiveNode(hierarchy, i, top_level, x, y,min_dist, &closest_node, &closest_node_level);
947 double *x_coords,
double *y_coords,
ex_vtx_data ** gp)
953 int nedges1 = 0, nedges2 = 0;
955 int i, j, k, l, first_nedges;
957 for (i = 0; i < n; i++) {
958 nedges1 += graph1[i].
nedges;
959 nedges2 += graph2[i].
nedges;
961 int *edges =
gv_calloc(nedges1 + nedges2,
sizeof(
int));
964 for (i = 0; i < n; i++) {
965 geom_graph[i].
edges = edges;
966 geom_graph[i].
size = 1;
967 geom_graph[i].
x_coord = (float) x_coords[i];
968 geom_graph[i].
y_coord = (float) y_coords[i];
969 geom_graph[i].
edges[0] = i;
970 for (j = 1; j < graph1[i].
nedges; j++) {
971 edges[j] = graph1[i].
edges[j];
973 first_nedges = k = graph1[i].
nedges;
974 for (j = 1; j < graph2[i].
nedges; j++) {
976 for (l = 1; l < first_nedges; l++) {
981 if (l == first_nedges) {
1000 double *x_coords,
double *y_coords,
1005 if (
graph[
node].active_level == level) {
1006 x_coords[counter] =
graph[
node].x_coord;
1007 y_coords[counter++] =
graph[
node].y_coord;
1014 level - 1, x_coords, y_coords,
1017 if (hierarchy->
cv2v[level][2 *
node + 1] >= 0) {
1022 level - 1, x_coords, y_coords,
1034 double *x_coords,
double *y_coords,
int counter)
1039 if (
graph[
node].active_level == level) {
1040 graph[
node].physical_x_coord = (float) x_coords[counter];
1041 graph[
node].physical_y_coord = (float) y_coords[counter++];
1048 level - 1, x_coords, y_coords, counter);
1050 if (hierarchy->
cv2v[level][2 *
node + 1] >= 0) {
1053 hierarchy->
cv2v[level][2*
node + 1],
1054 level - 1, x_coords, y_coords,
1068 while (active_level > level) {
1081 while (active_level > level) {
1101 while (active_level > level) {
1118 while (active_level > level) {
1123 if (active_level == level)
1133 for (i=0; i<hierarchy->
nlevels; i++) {
1135 for (j=0; j<hierarchy->
nvtxs[i]; j++) {
1136 graph->active_level = level;
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
static double dist(int dim, double *x, double *y)
double distance(double *x, int dim, int i, int j)
Agraph_t * graph(char *name)
static double findClosestActiveNode(Hierarchy *hierarchy, int node, int level, double x, double y, double closest_dist, int *closest_node, int *closest_node_level)
void set_active_levels(Hierarchy *hierarchy, int *foci_nodes, int num_foci, levelparms_t *parms)
static double unweighted_common_fraction(v_data *graph, int v, int u, float *v_vector)
void quicksort_place(double *, int *, size_t size)
size_t extract_active_logical_coords(Hierarchy *hierarchy, int node, int level, double *x_coords, double *y_coords, size_t counter)
static void fill_neighbors_vec_unweighted(v_data *graph, int vtx, float *vtx_vec)
static double dist_from_foci(ex_vtx_data *graph, int node, int *foci, int num_foci)
int find_active_ancestor(Hierarchy *hierarchy, int level, int node)
Hierarchy * create_hierarchy(v_data *graph, int nvtxs, int nedges, ex_vtx_data *geom_graph, int ngeom_edges, bool dist2_limit)
int set_active_physical_coords(Hierarchy *hierarchy, int node, int level, double *x_coords, double *y_coords, int counter)
static void fill_neighbors_vec(v_data *graph, int vtx, float *vtx_vec)
double find_closest_active_node(Hierarchy *hierarchy, double x, double y, int *closest_fine_node)
void find_active_ancestor_info(Hierarchy *hierarchy, int level, int node, int *levell, int *nodee)
static double ddist(ex_vtx_data *geom_graph, int v, int u)
void init_active_level(Hierarchy *hierarchy, int level)
static void empty_neighbors_vec(v_data *graph, int vtx, float *vtx_vec)
static int make_coarse_ex_graph(ex_vtx_data *graph, int nedges, ex_vtx_data **cgp, int cnvtxs, int *v2cv, int *cv2v)
static ex_vtx_data * cpExGraph(ex_vtx_data *graph, int n, int nedges)
static void makev2cv(int *mflag, int nvtxs, int *v2cv, int *cv2v)
void find_old_physical_coords(Hierarchy *hierarchy, int level, int node, double *x, double *y)
static int make_coarse_graph(v_data *graph, int nedges, v_data **cgp, int cnvtxs, int *v2cv, int *cv2v)
static int maxmatch(v_data *graph, ex_vtx_data *geom_graph, int nvtxs, int *mflag, bool dist2_limit)
static v_data * cpGraph(v_data *graph, int n, int nedges)
static int dist3(v_data *graph, int node1, int node2)
static void coarsen_match(v_data *graph, ex_vtx_data *geom_graph, int nvtxs, int nedges, int geom_nedges, v_data **cgraph, ex_vtx_data **cgeom_graph, int *cnp, int *cnedges, int *cgeom_nedges, int **v2cvp, int **cv2vp, bool dist2_limit)
void find_physical_coords(Hierarchy *hierarchy, int level, int node, double *x, double *y)
int init_ex_graph(v_data *graph1, v_data *graph2, int n, double *x_coords, double *y_coords, ex_vtx_data **gp)
static int find_leftmost_descendant(Hierarchy *hierarchy, int node, int level, int cur_level)
#define neighbor(t, i, edim, elist)
static int nedges
total no. of edges used in routing
ex_vtx_data ** geom_graphs
float old_physical_y_coord
float old_physical_x_coord