Crossings Minimization  1.0
channel.c
Go to the documentation of this file.
1 /**
2  * @file channel.h
3  * @brief implementation of utilities that maintain information about channels;
4  * eventually these will replace the interlayer structures in crossings.c
5  * since they serve more general purposes.
6  */
7 
8 #include<stdio.h>
9 #include <stdlib.h>
10 #include "graph.h"
11 #include "min_crossings.h"
12 #include "heuristics.h"
13 #include "channel.h"
14 #include "stretch.h"
15 #include "random.h"
16 
18 
19 /**
20  * @return the number of edges between layers i-1 and i
21  */
22 static int count_down_edges(int i)
23 {
24  Layerptr layer = layers[i];
25  int count = 0;
26  for( int j = 0; j < layer->number_of_nodes; j++ ) {
27  count += layer->nodes[j]->down_degree;
28  }
29  return count;
30 }
31 
32 /**
33  * @return a pointer to the list of edges for channel i and fills in
34  * appropriate data: number of edges and the actual edges; note: channel i is
35  * between layers i-1 and i
36  */
37 static Channelptr initChannel(int i) {
38  Channelptr new_channel
39  = (Channelptr) calloc(1, sizeof(struct channel_struct));
40  new_channel->number_of_edges = count_down_edges(i);
41  new_channel->edges
42  = (Edgeptr *) calloc(new_channel->number_of_edges,
43  sizeof(Edgeptr));
44  int edge_position = 0;
45  for (int j = 0; j < layers[i]->number_of_nodes; j++) {
46  Nodeptr current_node = layers[i]->nodes[j];
47  for (int k = 0; k < current_node->down_degree; k++) {
48  new_channel->edges[edge_position++] = current_node->down_edges[k];
49  }
50  }
51  return new_channel;
52 }
53 
54 /**
55  * initializes data structures relevant to channels
56  */
57 void initChannels(void) {
58  channels
59  = (Channelptr *) calloc( number_of_layers, sizeof(Channelptr) );
60  for( int i = 1; i < number_of_layers; i++ ) {
61  channels[i] = initChannel(i);
62  }
63 }
64 
65 /**
66  * @return the total stretch of edges in channel i; assumes the positions of
67  * nodes on the two layers have been updated correctly
68  */
69 double totalChannelStretch(int i) {
70  double total_stretch = 0.0;
71  for ( int j = 0; j < channels[i]->number_of_edges; j++ ) {
72  total_stretch += stretch(channels[i]->edges[j]);
73  }
74  return total_stretch;
75 }
76 
77 /**
78  * @return the total stretch of edges incident on layer i
79  */
80 double totalLayerStretch(int i) {
81  double total_stretch = 0.0;
82  if ( i > 0 ) {
83  total_stretch += totalChannelStretch(i);
84  }
85  if ( i < number_of_layers - 1 ) {
86  total_stretch += totalChannelStretch(i + 1);
87  }
88  return total_stretch;
89 }
90 
91 /**
92  * @return the total stretch of edges in channel i; assumes the positions of
93  * nodes on the two layers have been updated correctly
94  */
95 double maxEdgeStretchInChannel(int i) {
96  double max_stretch = 0.0;
97  for ( int j = 0; j < channels[i]->number_of_edges; j++ ) {
98  double current_stretch = stretch(channels[i]->edges[j]);
99  if ( current_stretch > max_stretch ) {
100  max_stretch = current_stretch;
101  }
102  }
103  return max_stretch;
104 }
105 
106 /**
107  * @return the total stretch of all edges
108  */
109 double totalStretch() {
110 #ifdef DEBUG
111  printf("-> totalStretch, iteration = %d\n", iteration);
112 #endif
113  double total_stretch = 0.0;
114  for ( int i = 1; i < number_of_layers; i++ ) {
115  total_stretch += totalChannelStretch(i);
116  }
117 #ifdef DEBUG
118  printf("<- totalStretch, total_stretch = %7.2f\n", total_stretch);
119 #endif
120  return total_stretch;
121 }
122 
123 /**
124  * @return the maximum stretch among all edges
125  */
126 double maxEdgeStretch() {
127 #ifdef DEBUG
128  printf("-> maxEdgeStretch, iteration = %d\n", iteration);
129 #endif
130  double max_stretch = 0.0;
131  for ( int i = 1; i < number_of_layers; i++ ) {
132  double channel_stretch = maxEdgeStretchInChannel(i);
133  if ( channel_stretch > max_stretch ) {
134  max_stretch = channel_stretch;
135  }
136  }
137 #ifdef DEBUG
138  printf("<- maxEdgeStretch, max_stretch = %7.2f\n", max_stretch);
139 #endif
140  return max_stretch;
141 }
142 
143 /**
144  * @return the edge with maximum stretch among edges that have not been fixed
145  */
147  Edgeptr max_stretch_edge = NULL;
148  double max_stretch = -1.0;
149  if ( randomize_order ) {
151  }
152  for ( int i = 0; i < number_of_edges; i++ ) {
153  Edgeptr edge = master_edge_list[i];
154  double current_stretch = stretch(edge);
155  if( current_stretch > max_stretch && ! isFixedEdge( edge ) ) {
156  max_stretch = current_stretch;
157  max_stretch_edge = edge;
158  }
159  }
160  return max_stretch_edge;
161 }
162 
163 /* [Last modified: 2016 05 20 at 18:48:51 GMT] */
double maxEdgeStretchInChannel(int i)
Definition: channel.c:95
int number_of_edges
Definition: channel.h:20
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
struct channel_struct * Channelptr
Channelptr * channels
Definition: channel.c:17
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
double totalLayerStretch(int i)
Definition: channel.c:80
Edgeptr * down_edges
Definition: graph.h:78
Global variables, functions, and parameters specified on the command line.
void initChannels(void)
Definition: channel.c:57
bool randomize_order
Definition: min_crossings.c:54
double maxEdgeStretch()
Definition: channel.c:126
double stretch(Edgeptr e)
Definition: stretch.c:15
int iteration
Definition: heuristics.c:47
implementation of utilities that maintain information about channels; eventually these will replace t...
static Channelptr initChannel(int i)
Definition: channel.c:37
double totalStretch()
Definition: channel.c:109
Edgeptr * edges
Definition: channel.h:26
header for utilities for computing and updating the "stretch" of edges, where stretch is of edge vw i...
int down_degree
Definition: graph.h:75
Definition of data structures and access functions for a layered graph.
CROSSING_STATS_DOUBLE total_stretch
Definition: stats.c:150
static int count_down_edges(int i)
Definition: channel.c:22
bool isFixedEdge(Edgeptr edge)
Definition: heuristics.c:295
int number_of_edges
Definition: graph_io.c:29
Nodeptr * nodes
Definition: graph.h:116
double totalChannelStretch(int i)
Definition: channel.c:69
int number_of_layers
Definition: graph_io.c:28
Edgeptr maxStretchEdge()
Definition: channel.c:146
Edgeptr * master_edge_list
Definition: graph_io.c:26
void genrand_permute(void *A, int length, int element_size)
Definition: random.c:183