Crossings Minimization  1.0
median.c
Go to the documentation of this file.
1 /**
2  * @file median.c
3  * @brief implements various functions related to median heuristics
4  * @author Matthias Stallmann
5  * @date 2008/12/29
6  * $Id: median.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"median.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  * @return the median position of the nodes adjacent to 'node' on the layer
24  * above 'node'
25  */
26 static double upper_median( Nodeptr node )
27 {
28  // -1 indicates no up edges -- see the adjust_weights functions below
29  if ( node->up_degree == 0 ) return -1;
30  sortByUpNodePosition( node->up_edges, node->up_degree );
31  int median_position = (node->up_degree - 1) / 2;
32  Edgeptr median_edge = node->up_edges[ median_position ];
33  return median_edge->up_node->position;
34 }
35 
36 /**
37  * @return the median position of the nodes adjacent to 'node' on the layer
38  * below 'node'
39  */
40 static double lower_median( Nodeptr node )
41 {
42  // -1 indicates no down edges -- see the adjust_weights functions below
43  if ( node->down_degree == 0 ) return -1;
45  int median_position = (node->down_degree - 1) / 2;
46  Edgeptr median_edge = node->down_edges[ median_position ];
47  return median_edge->down_node->position;
48 }
49 
50 /**
51  * Computes the weight of a node based on the median position of its
52  * neighbors according to the given orientation.
53  */
54 static void node_weight( Nodeptr node, Orientation orientation )
55 {
56 #ifdef DEBUG
57  printf("-> (median) node_weight, node = %s, orientation = %d\n", node->name, orientation );
58 #endif
59  assert( orientation != BOTH );
60  if( orientation == UPWARD )
61  {
62  node->weight = upper_median( node );
63  }
64  else if ( orientation == DOWNWARD )
65  {
66  node->weight = lower_median( node );
67  }
68 #ifdef DEBUG
69  printf("<- (median) node_weight, node = %s, weight = %f\n", node->name, node->weight );
70 #endif
71 }
72 
73 /**
74  * computes weight based on two neighboring layers as
75  * 1/2 * (upper_median + lower_median)
76  */
77 static void two_layer_node_weight( Nodeptr node )
78 {
79  node->weight = ( upper_median(node) + lower_median(node) ) / 2;
80 }
81 
82 /**
83  * Some nodes may have weight -1 because they have no edges in the
84  * desired direction. This function gives them a weight identical to that of
85  * their left neighbor on the layer, or 0 if all nodes to the left have
86  * weight -1.
87  * Note: If the node to the left has weight -1 originally, its weight will
88  * have been changed by the time the node is processed.
89  */
90 static void adjust_weights_left( int layer )
91 {
92  Layerptr layerptr = layers[ layer ];
93  int i = 0;
94  for( ; i < layerptr->number_of_nodes; i++ )
95  {
96  Nodeptr node = layerptr->nodes[i];
97  if( node->weight == -1 )
98  {
99  if( i == 0 ) node->weight = 0;
100  else node->weight = layerptr->nodes[i-1]->weight;
101 #ifdef DEBUG
102  printf(" adjust_weight (left), node = %s, weight = %f\n",
103  node->name, node->weight );
104 #endif
105  }
106  }
107 }
108 
109 /**
110  * Some nodes may have weight -1 because they have no edges in the
111  * desired direction. This function gives them a weight that is the average
112  * of that of the two neighbors on the layer - or just the weight of one of
113  * the neighbors if the other is absent or also has weight -1.
114  */
115 static void adjust_weights_avg( int layer )
116 {
117  Layerptr layerptr = layers[ layer ];
118  int i = 0;
119  for( ; i < layerptr->number_of_nodes; i++ )
120  {
121  Nodeptr node = layerptr->nodes[i];
122  if( node->weight == -1 )
123  {
124  int number_of_weights = 0;
125  double total_weight = 0;
126  if( i > 0 )
127  {
128  number_of_weights++;
129  total_weight += layerptr->nodes[i-1]->weight;
130  }
131  if( i < layerptr->number_of_nodes - 1
132  && layerptr->nodes[i+1]->weight >= 0 )
133  {
134  number_of_weights++;
135  total_weight += layerptr->nodes[i+1]->weight;
136  }
137  if( number_of_weights > 0 )
138  node->weight = total_weight / number_of_weights;
139  else
140  // this happens if the leftmost node has a right neighbor with
141  // weight of -1
142  node->weight = 0;
143 #ifdef DEBUG
144  printf(" adjust_weight (avg), node = %s, weight = %f\n",
145  node->name, node->weight );
146 #endif
147  }
148  }
149 }
150 
151 /**
152  * Assigns weights to nodes on the given layer based on positions of their
153  * edges above, below, or both, as specified by the orientation.
154  */
155 void medianWeights( int layer, Orientation orientation )
156 {
157 #ifdef DEBUG
158  printf("-> medianWeights, layer = %d, orientation = %d\n",
159  layer, orientation );
160 #endif
161  Layerptr layerptr = layers[ layer ];
162  int i = 0;
163  int num_nodes = layerptr->number_of_nodes;
164 /*
165 #ifdef _OPENMP
166 #pragma omp parallel for default(none) private(i) \
167  shared(num_nodes, orientation, balanced_weight, \
168  layerptr, trace_freq, number_of_processors)
169 #endif
170 */
171  for(i = 0 ; i < num_nodes; i++ )
172  {
173  if ( orientation == BOTH )
174  two_layer_node_weight( layerptr->nodes[i] );
175  else
176  node_weight( layerptr->nodes[i], orientation );
177  }
178  if( adjust_weights == LEFT )
179  adjust_weights_left( layer );
180  else if( adjust_weights == AVG )
181  adjust_weights_avg( layer );
182 #ifdef DEBUG
183  printf( "<- medianWeights\n" );
184 #endif
185 }
186 
187 bool medianUpSweep( int starting_layer )
188 {
189  int layer = starting_layer;
190  for( ; layer < number_of_layers; layer++ )
191  {
192  medianWeights( layer, DOWNWARD );
193  layerSort( layer );
194  updateCrossingsForLayer( layer );
195  tracePrint( layer, "median upsweep" );
196  if ( end_of_iteration() )
197  return true;
198  }
199  return false;
200 }
201 
202 /**
203  * Repeats median heuristic moving downward from the starting layer to the
204  * bottom layer, layer 0. Orientation of each heuristic application is upward.
205  */
206 bool medianDownSweep( int starting_layer )
207 {
208  int layer = starting_layer;
209  for( ; layer >= 0; layer-- )
210  {
211  medianWeights( layer, UPWARD );
212  layerSort( layer );
213  updateCrossingsForLayer( layer );
214  tracePrint( layer, "median downsweep" );
215  if ( end_of_iteration() )
216  return true;
217  }
218  return false;
219 }
220 
221 /* [Last modified: 2014 09 09 at 15:54:14 GMT] */
enum adjust_weights_enum adjust_weights
Definition: min_crossings.c:47
Nodeptr up_node
Definition: graph.h:98
bool medianUpSweep(int starting_layer)
Definition: median.c:187
Definition: defs.h:43
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 adjust_weights_left(int layer)
Definition: median.c:90
bool end_of_iteration(void)
Definition: heuristics.c:183
void medianWeights(int layer, Orientation orientation)
Definition: median.c:155
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
static double upper_median(Nodeptr node)
Definition: median.c:26
static void two_layer_node_weight(Nodeptr node)
Definition: median.c:77
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
static double lower_median(Nodeptr node)
Definition: median.c:40
int up_degree
Definition: graph.h:74
int number_of_nodes
Definition: graph_io.c:27
Definition of functions for reading and writing graphs.
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 medianDownSweep(int starting_layer)
Definition: median.c:206
Definition of data structures and access functions for a layered graph.
static void adjust_weights_avg(int layer)
Definition: median.c:115
Definition: defs.h:43
void tracePrint(int layer, const char *message)
Definition: heuristics.c:122
static void node_weight(Nodeptr node, Orientation orientation)
Definition: median.c:54
void sortByUpNodePosition(Edgeptr *edge_array, int num_edges)
Definition: sorting.c:209
void layerSort(int layer)
Definition: sorting.c:159
Nodeptr * nodes
Definition: graph.h:116
interface for various functions related to median heuristics
Nodeptr down_node
Definition: graph.h:99
int number_of_layers
Definition: graph_io.c:28
void sortByDownNodePosition(Edgeptr *edge_array, int num_edges)
Definition: sorting.c:200
Definition: defs.h:43