Graphviz 14.0.2~dev.20251008.0253
Loading...
Searching...
No Matches
country_graph_coloring.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#define STANDALONE
13#include <math.h>
14#include "power.h"
15#include <stdbool.h>
16#include <time.h>
17
18static double get_local_12_norm(int n, int i, const int *ia, const int *ja,
19 const int *p) {
20 double norm = n;
21 for (int j = ia[i]; j < ia[i+1]; j++){
22 if (ja[j] == i) continue;
23 norm = fmin(norm, abs(p[i] - p[ja[j]]));
24 }
25 return norm;
26}
27
28static void get_12_norm(int n, const int *ia, const int *ja, int *p,
29 double *norm) {
30 /* norm[0] := antibandwidth
31 norm[1] := (\sum_{i\in V} (Min_{{j,i}\in E} |p[i] - p[j]|)/|V|
32 */
33 norm[0] = n; norm[1] = 0;
34 for (int i = 0; i < n; i++){
35 double tmp = n;
36 for (int j = ia[i]; j < ia[i+1]; j++){
37 if (ja[j] == i) continue;
38 norm[0] = fmin(norm[0], abs(p[i] - p[ja[j]]));
39 tmp = fmin(tmp, abs(p[i] - p[ja[j]]));
40 }
41 norm[1] += tmp;
42 }
43 norm[1] /= n;
44}
45
47 int cnt = 1, n = A->m, *ia = A->ia, *ja = A->ja;
48 double norm1[2];
49 clock_t start = clock();
50 FILE *fp = NULL;
51
52 if (Verbose){
53 fprintf(stderr,"saving timing vs antiband data to timing_greedy\n");
54 fp = fopen("timing_greedy","w");
55 }
56 assert(SparseMatrix_is_symmetric(A, true));
57 for (bool improved = true; improved; ) {
58 improved = false;
59 for (int i = 0; i < n; i++) {
60 norm1[0] = get_local_12_norm(n, i, ia, ja, p);
61 for (int j = 0; j < n; j++) {
62 if (j == i) continue;
63 const double norm2 = get_local_12_norm(n, j, ia, ja, p);
64 const int pi = p[i];
65 const int pj = p[j];
66 p[i] = pj;
67 p[j] = pi;
68 const double norm11 = get_local_12_norm(n, i, ia, ja, p);
69 const double norm22 = get_local_12_norm(n, j, ia, ja, p);
70 if (fmin(norm11, norm22) > fmin(norm1[0], norm2)){
71 improved = true;
72 norm1[0] = norm11;
73 continue;
74 }
75 p[i] = pi;
76 p[j] = pj;
77 }
78 if (i%100 == 0 && Verbose) {
79 get_12_norm(n, ia, ja, p, norm1);
80 fprintf(fp, "%f %f %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC,
81 norm1[0], norm1[1]);
82 }
83 }
84 if (Verbose) {
85 get_12_norm(n, ia, ja, p, norm1);
86 fprintf(stderr, "[%d] aband = %f, aband_avg = %f\n", cnt++, norm1[0], norm1[1]);
87 fprintf(fp,"%f %f %f\n", ((double)(clock() - start)) / CLOCKS_PER_SEC,
88 norm1[0], norm1[1]);
89 }
90 }
91 if (fp != NULL) {
92 fclose(fp);
93 }
94}
95
97 int n = A->m;
98
99 clock_t start = clock();
100 assert(A->m == A->n);
102 const int *const ia = A2->ia;
103 const int *const ja = A2->ja;
104
105 /* Laplacian */
107 for (int i = 0; i < n; i++){
108 double nrow = 0.;
109 for (int j = ia[i]; j < ia[i+1]; j++){
110 const int jj = ja[j];
111 if (jj != i){
112 nrow ++;
113 L = SparseMatrix_coordinate_form_add_entry(L, i, jj, &(int){-1});
114 }
115 }
117 }
118 {
121 L = new;
122 }
123
124 /* largest eigen vector */
125 double *v = power_method(L, L->n, seed);
126
127 vector_ordering(n, v, p);
128 if (Verbose)
129 fprintf(stderr, "cpu time for spectral ordering (before greedy) = %f\n",
130 ((double)(clock() - start)) / CLOCKS_PER_SEC);
131
132 clock_t start2 = clock();
133 /* swapping */
135 if (Verbose) {
136 fprintf(stderr, "cpu time for greedy refinement = %f\n",
137 ((double)(clock() - start2)) / CLOCKS_PER_SEC);
138
139 fprintf(stderr, "cpu time for spectral + greedy = %f\n",
140 ((double)(clock() - start)) / CLOCKS_PER_SEC);
141
142 }
143
144 if (A2 != A) SparseMatrix_delete(A2);
146}
SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A)
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, bool pattern_symmetric_only)
SparseMatrix SparseMatrix_coordinate_form_add_entry(SparseMatrix A, int irn, int jcn, const void *val)
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format)
@ MATRIX_TYPE_REAL
@ FORMAT_COORD
void country_graph_coloring(int seed, SparseMatrix A, int **p)
void improve_antibandwidth_by_swapping(SparseMatrix A, int *p)
static double get_local_12_norm(int n, int i, const int *ia, const int *ja, const int *p)
static void get_12_norm(int n, const int *ia, const int *ja, int *p, double *norm)
static double norm(int n, const double *x)
static long seed
Definition exeval.c:1005
#define A(n, t)
Definition expr.h:76
void vector_ordering(int n, double *v, int **p)
Definition general.c:91
static bool Verbose
Definition gml2gv.c:24
static attrs_t * L
Definition gmlparse.c:94
node NULL
Definition grammar.y:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
double * power_method(void *A, int n, int random_seed)
Definition power.c:21