Crossings Minimization  1.0
stretch.c
Go to the documentation of this file.
1 /**
2  * @file stretch.c @brief implementation of utilities for computing and
3  * updating the "stretch" of edges, where stretch is of edge vw is defined to
4  * be
5  * abs( p(v)/(|L(v)|-1) - p(w)/(|L(w)|-1) )
6  * Here p(x), L(x) are the position and layer of x, respectively; if there is
7  * only one node on a layer, the denominator is replaced by 2.
8  */
9
10 #include <stdio.h>
11 #include <math.h>
12 #include "graph.h"
13 #include "stretch.h"
14
15 double stretch(Edgeptr e) {
16  Nodeptr v = e->down_node;
17  Nodeptr w = e->up_node;
18 #ifdef DEBUG
19  printf("-> stretch, %s, %s\n", v->name, w->name);
20 #endif
21  int v_layer = v->layer;
22  int w_layer = w->layer;
23  int v_layer_size = layers[v_layer]->number_of_nodes;
24  int w_layer_size = layers[w_layer]->number_of_nodes;
25  double v_scale = v_layer_size > 1 ? v_layer_size - 1.0 : 2.0;
26  double w_scale = w_layer_size > 1 ? w_layer_size - 1.0 : 2.0;
27  double stretch = fabs( v->position / v_scale - w->position / w_scale );
28 #ifdef DEBUG
29  printf("<- stretch, v: scale, position = %f, %d; w: scale, position = %f, %d;"
30  " stretch = %f\n",
31  v_scale, v->position, w_scale, w->position, stretch);
32 #endif
33  return stretch;
34 }
35
Nodeptr up_node
Definition: graph.h:98
char * name
Definition: graph.h:63
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
int position
Definition: graph.h:73
double stretch(Edgeptr e)
Definition: stretch.c:15
header for utilities for computing and updating the "stretch" of edges, where stretch is of edge vw i...
int layer
Definition: graph.h:65
Definition of data structures and access functions for a layered graph.
Nodeptr down_node
Definition: graph.h:99