Crossings Minimization  1.0
barycenter.c
Go to the documentation of this file.
1 /**
2  * @file barycenter.c
3  * @brief implements various functions related to barycenter heuristics
4  * @author Matthias Stallmann
5  * @date 2008/12/29
6  * \$Id: barycenter.c 96 2014-09-09 16:37:16Z mfms \$
7  */
8
9 #include<stdio.h>
10 #include<stdlib.h>
11 #include<assert.h>
12
13 #include"defs.h"
14 #include"min_crossings.h"
15 #include"barycenter.h"
16 #include"graph.h"
17 #include"sorting.h"
18 #include"crossings.h"
19 #include"graph_io.h"
20 #include"heuristics.h"
21
22 /**
23  * Computes the weight of a node based on the average position of its
24  * neighbors according to the given orientation.
25  * If the node has no neighbors in the direction specified by the
26  * orientation, its neighbors in the other direction are taken into
27  * account. Isolated nodes have 0 weight.
28  */
29 static void node_weight( Nodeptr node, Orientation orientation )
30 {
31  int total_degree = 0;
32  int total_of_positions = 0;
34  if( orientation != UPWARD )
35  {
36  total_degree += node->down_degree;
38  {
39  total_of_positions
41  }
42  }
43  if( orientation != DOWNWARD )
44  {
45  total_degree += node->up_degree;
47  {
48  total_of_positions
50  }
51  }
52  if( total_degree > 0 )
53  node->weight = (double) total_of_positions / total_degree;
54  else if( adjust_weights == NONE
55  // put isolated nodes to the far left
56  || node->up_degree + node->down_degree == 0 ) node->weight = 0;
57  else
58  // indicate that this is a special case - no edges in the given
59  // orientation - and needs to be fixed
60  node->weight = -1;
61 #ifdef DEBUG
62  printf(" node_weight, node = %d, weight = %f\n", node->id, node->weight );
63 #endif
64 }
65
66 /**
67  * computes weight based on two neighboring layers, but does it as
68  * 1/2 * (upper_average + lower_average)
70  * sum_of_positions / total_degree
71  */
72 static void balanced_node_weight( Nodeptr node ) {
73 #ifdef DEBUG
74  printf( "-> balanced_node_weight, node = %d\n", node->id );
75 #endif
77  int degree;
78  int total_of_positions;
79
80  // compute average position in the downward direction
81  total_of_positions = 0;
82  degree = node->down_degree;
84  total_of_positions
86  }
87  double downward_average;
88  if ( degree > 0 ) downward_average = (double) total_of_positions / degree;
89  else downward_average = 0;
90
91  // compute average position in the upward direction
92  total_of_positions = 0;
93  degree = node->up_degree;
95  total_of_positions
97  }
98  double upward_average;
99  if ( degree > 0 ) upward_average = (double) total_of_positions / degree;
100  else upward_average = 0;
101
102  node->weight = (downward_average + upward_average) / 2;
103 #ifdef DEBUG
104  printf( "<- balanced_node_weight, node = %d, weight = %4.1f,"
105  " down_avg = %4.1f, up_avg = %4.1f\n",
106  node->id, node->weight, downward_average, upward_average );
107 #endif
108 }
109
110 /**
111  * Some nodes may have weight -1 because they have no edges in the
112  * desired direction. This function gives them a weight identical to that of
113  * their left neighbor on the layer, or 0 if all nodes to the left have
114  * weight -1.
115  * Note: If the node to the left has weight -1 originally, its weight will
116  * have been changed by the time the node is processed.
117  *
119  * counterparts in median.c
120  */
121 static void adjust_weights_left( int layer )
122 {
123  Layerptr layerptr = layers[ layer ];
124  int i = 0;
125  for( ; i < layerptr->number_of_nodes; i++ )
126  {
127  Nodeptr node = layerptr->nodes[i];
128  if( node->weight == -1 )
129  {
130  if( i == 0 ) node->weight = 0;
131  else node->weight = layerptr->nodes[i-1]->weight;
132 #ifdef DEBUG
133  printf(" adjust_weight (left), node = %s, weight = %f\n",
134  node->name, node->weight );
135 #endif
136  }
137  }
138 }
139
140 /**
141  * Some nodes may have weight -1 because they have no edges in the
142  * desired direction. This function gives them a weight that is the average
143  * of that of the two neighbors on the layer - or just the weight of one of
144  * the neighbors if the other is absent or also has weight -1.
145  */
146 static void adjust_weights_avg( int layer ) {
147  Layerptr layerptr = layers[ layer ];
148  int num_nodes = layerptr->number_of_nodes;
149  // this method of adjusting weights is used in parallel barycenter
150  // versions, so it is important that the adjusted weight of a node is not
151  // influenced by the already adjusted weight of its left neighbor;
152  // temp_weights holds the unadjusted weights
153  double * temp_weights;
154  bool parallel = (number_of_processors != 1);
155  if ( parallel ) {
156  temp_weights = (double *) calloc( num_nodes, sizeof(double) );
157  for ( int i = 0; i < num_nodes; i++ ) {
158  temp_weights[i] = layerptr->nodes[i]->weight;
159  }
160  }
161  for ( int i = 0; i < num_nodes; i++ ) {
162  Nodeptr node = layerptr->nodes[i];
163  double weight = parallel ? temp_weights[i] : layerptr->nodes[i]->weight;
164  // Do nothing if node already has a weight
165  if ( weight != -1 ) continue;
166
167  double left_weight = -1;
168  double right_weight = -1;
169  if ( i > 0 ) {
170  left_weight = parallel ? temp_weights[i-1] : layerptr->nodes[i-1]->weight;
171  }
172  if ( i < num_nodes - 1 ) {
173  right_weight = parallel ? temp_weights[i+1] : layerptr->nodes[i+1]->weight;
174  }
175
176  // if both neighbors are present and have weights, take the
177  // average of their weights
178  if ( left_weight != -1 && right_weight != -1 ) {
179  node->weight = (left_weight + right_weight) / 2;
180  }
181  else if ( left_weight != -1 ) {
182  // only the left neighbor has a weight
183  node->weight = left_weight;
184  }
185  else if ( right_weight != -1 ) {
186  // only the right neighbor has a weight
187  node->weight = right_weight;
188  }
189  else {
190  // neither neighbor has a weight: can propagate from left if not parallel
191  node->weight = parallel ? 0 : left_weight;
192  }
193 #ifdef DEBUG
194  printf(" adjust_weight (avg), node = %s, weight = %f\n",
195  node->name, node->weight );
196 #endif
197  } // for nodes on this layer
198  if ( parallel )
199  free( temp_weights );
201
202 /**
203  * Assigns weights to nodes on the given layer based on positions of their
204  * edges above, below, or both, as specified by the orientation.
205  */
206 void barycenterWeights( int layer, Orientation orientation )
207 {
208 #ifdef DEBUG
209  printf("-> barycenterWeights, layer = %d, orientation = %d"
210  ", balanced_weight = %d\n",
211  layer, orientation, balanced_weight );
212 #endif
213  Layerptr layerptr = layers[ layer ];
214  int i = 0;
215  int num_nodes = layerptr->number_of_nodes;
216 /*
217 #ifdef _OPENMP
218 #pragma omp parallel for default(none) private(i) \
219  shared(num_nodes, orientation, balanced_weight, \
220  layerptr, trace_freq, number_of_processors)
221 #endif
222 */
223  for(i = 0 ; i < num_nodes; i++ )
224  {
225  if ( orientation == BOTH && balanced_weight )
226  balanced_node_weight( layerptr->nodes[i] );
227  else
228  node_weight( layerptr->nodes[i], orientation );
229  }
230  if( adjust_weights == LEFT )
232  else if( adjust_weights == AVG )
234 #ifdef DEBUG
235  printf( "<- barycenterWeights\n" );
236 #endif
237 }
238
239 bool barycenterUpSweep( int starting_layer )
240 {
241  int layer = starting_layer;
242  for( ; layer < number_of_layers; layer++ )
243  {
244  barycenterWeights( layer, DOWNWARD );
245  layerSort( layer );
246  // layerQuicksort( layer );
247  // layerUnstableSort( layer );
248  updateCrossingsForLayer( layer );
249  tracePrint( layer, "barycenter upsweep" );
250  if ( end_of_iteration() )
251  return true;
252  }
253  return false;
254 }
255
256 /**
257  * Repeats barycenter heuristic moving downward from the starting layer to the
258  * bottom layer, layer 0. Orientation of each heuristic application is upward.
259  */
260 bool barycenterDownSweep( int starting_layer )
261 {
262  int layer = starting_layer;
263  for( ; layer >= 0; layer-- )
264  {
265  barycenterWeights( layer, UPWARD );
266  layerSort( layer );
267  // layerQuicksort( layer );
268  // layerUnstableSort( layer );
269  updateCrossingsForLayer( layer );
270  tracePrint( layer, "barycenter downsweep" );
271  if ( end_of_iteration() )
272  return true;
273  }
274  return false;
275 }
276
Definition: min_crossings.c:47
Nodeptr up_node
Definition: graph.h:98
Definition: defs.h:43
int id
Definition: graph.h:64
Orientation
Definition: defs.h:43
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
char * name
Definition: graph.h:63
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
Edgeptr * down_edges
Definition: graph.h:78
static void balanced_node_weight(Nodeptr node)
Definition: barycenter.c:72
bool end_of_iteration(void)
Definition: heuristics.c:183
Global variables, functions, and parameters specified on the command line.
Definitions common to all edge crossing heuristic source files.
int position
Definition: graph.h:73
bool barycenterDownSweep(int starting_layer)
Definition: barycenter.c:260
Interface for functions that perform various sorts. All sorts are stable.
void updateCrossingsForLayer(int layer)
Definition: crossings.c:147
Edgeptr * up_edges
Definition: graph.h:77
int up_degree
Definition: graph.h:74
Definition of functions for reading and writing graphs.
static void node_weight(Nodeptr node, Orientation orientation)
Definition: barycenter.c:29
Definition: barycenter.c:121
double weight
Definition: graph.h:82
Definition of functions that keep track of and update the number of crossings for each node...
int down_degree
Definition: graph.h:75
bool balanced_weight
Definition: min_crossings.c:58
Definition of data structures and access functions for a layered graph.
Definition: defs.h:43
void tracePrint(int layer, const char *message)
Definition: heuristics.c:122
void barycenterWeights(int layer, Orientation orientation)
Definition: barycenter.c:206
void layerSort(int layer)
Definition: sorting.c:159
Nodeptr * nodes
Definition: graph.h:116
Nodeptr down_node
Definition: graph.h:99
int number_of_layers
Definition: graph_io.c:28
int number_of_processors
Definition: min_crossings.c:45