Crossings Minimization  1.0
swap.c
Go to the documentation of this file.
1 /**
2  * @file swap.c
3  * @brief Implementation of functions that compute the change in crossing
4  * number (or max edge crossings if desired) when two neighboring nodes are swapped.
5  * @author Matt Stallmann
6  * @date 2011/05/21
7  * $Id: swap.c 2 2011-06-07 19:50:41Z mfms $
8  */
9 
10 #include"graph.h"
11 #include"defs.h"
12 #include"crossings.h"
13 #include"crossing_utilities.h"
14 #include"swap.h"
15 #include"sorting.h"
16 
17 #include<stdio.h>
18 #include<stdlib.h>
19 #include<assert.h>
20 #include<stdbool.h>
21 #include<limits.h>
22 
23 /**
24  * Fills edge_array with upward edges of the two nodes, each set of edges
25  * sorted by their endpoint positions on the layer above and those of the
26  * first node coming first. Used to compute number of swaps by counting
27  * inversions [reference to paper by Jünger and Mutzel needed]
28  */
29 void create_sorted_up_edge_array( Edgeptr * edge_array,
30  Nodeptr first_node,
31  Nodeptr second_node );
32 
33 /**
34  * Fills edge_array with downward edges of the two nodes, each set of edges
35  * sorted by their endpoint positions on the layer above and those of the
36  * first node coming first. Used to compute number of swaps by counting
37  * inversions [reference to paper by Jünger and Mutzel needed]
38  */
39 void create_sorted_down_edge_array( Edgeptr * edge_array,
40  Nodeptr first_node,
41  Nodeptr second_node );
42 
44 {
45  int edge_crossings = 0;
46  // update max_edge_crossings based on upward edges
47  for ( int i = 0; i < node->up_degree; i++ )
48  if ( node->up_edges[i]->crossings > edge_crossings )
49  edge_crossings = node->up_edges[i]->crossings;
50  // update max_edge_crossings based on downward edges
51  for ( int i = 0; i < node->down_degree; i++ )
52  if ( node->down_edges[i]->crossings > edge_crossings )
53  edge_crossings = node->down_edges[i]->crossings;
54  return edge_crossings;
55 }
56 
57 int node_crossings( Nodeptr node_a, Nodeptr node_b )
58 {
59  assert( node_a->layer == node_b->layer );
60  int layer = node_a->layer;
61 
62  int total_crossings = 0;
63 
64  // count crossings among upward edges (if any)
65  if ( layer < number_of_layers - 1 )
66  {
67  Edgeptr * edge_array
68  = (Edgeptr *) calloc( node_a->up_degree + node_b->up_degree,
69  sizeof(Edgeptr) );
70  create_sorted_up_edge_array( edge_array, node_a, node_b );
71  total_crossings += count_inversions_up( edge_array,
72  node_a->up_degree
73  + node_b->up_degree, 1 );
74  free( edge_array );
75  }
76 
77  // count crossings among downward edges (if any)
78  if ( layer > 0 )
79  {
80  Edgeptr * edge_array
81  = (Edgeptr *) calloc( node_a->down_degree + node_b->down_degree,
82  sizeof(Edgeptr) );
83 
84  create_sorted_down_edge_array( edge_array, node_a, node_b );
85  total_crossings += count_inversions_down( edge_array,
86  node_a->down_degree
87  + node_b->down_degree, 1 );
88  free( edge_array );
89  }
90  return total_crossings;
91 }
92 
93 void change_crossings( Nodeptr left_node, Nodeptr right_node, int diff )
94 {
95  int layer = left_node->layer;
96 
97  // update crossings on upward edges (if any)
98  if ( layer < number_of_layers - 1 )
99  {
100  Edgeptr * edge_array
101  = (Edgeptr *) calloc( left_node->up_degree + right_node->up_degree,
102  sizeof(Edgeptr) );
103  create_sorted_up_edge_array( edge_array, left_node, right_node );
104  count_inversions_up( edge_array,
105  left_node->up_degree + right_node->up_degree,
106  diff );
107  free( edge_array );
108  }
109 
110  // update crossings on downward edges (if any)
111  if ( layer > 0 )
112  {
113  Edgeptr * edge_array
114  = (Edgeptr *) calloc( left_node->down_degree + right_node->down_degree,
115  sizeof(Edgeptr) );
116  create_sorted_down_edge_array( edge_array, left_node, right_node );
117  count_inversions_down( edge_array,
118  left_node->down_degree + right_node->down_degree,
119  diff );
120  free( edge_array );
121  }
122 }
123 
124 int edge_crossings_after_swap( Nodeptr left_node, Nodeptr right_node )
125 {
126  change_crossings( left_node, right_node, -1 );
127  change_crossings( right_node, left_node, +1 );
128  int left_node_edge_crossings = edge_crossings_for_node( left_node );
129  int right_node_edge_crossings = edge_crossings_for_node( right_node );
130  if( left_node_edge_crossings > right_node_edge_crossings )
131  return left_node_edge_crossings;
132  else
133  return right_node_edge_crossings;
134 }
135 
137  Nodeptr first_node,
138  Nodeptr second_node )
139 {
140  sortByUpNodePosition( first_node->up_edges, first_node->up_degree );
141  sortByUpNodePosition( second_node->up_edges, second_node->up_degree );
142  add_edges_to_array( edge_array,
143  first_node->up_edges, first_node->up_degree, 0 );
144  add_edges_to_array( edge_array,
145  second_node->up_edges, second_node->up_degree,
146  first_node->up_degree );
147 }
148 
150  Nodeptr first_node,
151  Nodeptr second_node )
152 {
153  sortByDownNodePosition( first_node->down_edges, first_node->down_degree );
154  sortByDownNodePosition( second_node->down_edges, second_node->down_degree );
155  add_edges_to_array( edge_array,
156  first_node->down_edges, first_node->down_degree, 0 );
157  add_edges_to_array( edge_array,
158  second_node->down_edges, second_node->down_degree,
159  first_node->down_degree );
160 }
161 
162 /* [Last modified: 2011 05 24 at 15:59:47 GMT] */
Definition of functions that are used to count and update crossings locally. Used both by crossings...
int edge_crossings_after_swap(Nodeptr left_node, Nodeptr right_node)
Definition: swap.c:124
Edgeptr * down_edges
Definition: graph.h:78
Definitions common to all edge crossing heuristic source files.
Interface for functions that perform various sorts. All sorts are stable.
int edge_crossings_for_node(Nodeptr node)
Definition: swap.c:43
CROSSING_STATS_INT total_crossings
Definition: stats.c:147
Edgeptr * up_edges
Definition: graph.h:77
int up_degree
Definition: graph.h:74
void add_edges_to_array(Edgeptr *edge_array, Edgeptr *edges_to_add, int num_edges, int start_pos)
Definition of functions that keep track of and update the number of crossings for each node...
int layer
Definition: graph.h:65
int down_degree
Definition: graph.h:75
int crossings
Definition: graph.h:100
void create_sorted_up_edge_array(Edgeptr *edge_array, Nodeptr first_node, Nodeptr second_node)
Definition: swap.c:136
void create_sorted_down_edge_array(Edgeptr *edge_array, Nodeptr first_node, Nodeptr second_node)
Definition: swap.c:149
Definition of data structures and access functions for a layered graph.
int count_inversions_down(Edgeptr *edge_array, int number_of_edges, int diff)
void sortByUpNodePosition(Edgeptr *edge_array, int num_edges)
Definition: sorting.c:209
int node_crossings(Nodeptr node_a, Nodeptr node_b)
Definition: swap.c:57
Headers of functions that compute the change in crossing number or max edge crossings when two neighb...
int number_of_layers
Definition: graph_io.c:28
void change_crossings(Nodeptr left_node, Nodeptr right_node, int diff)
Definition: swap.c:93
int count_inversions_up(Edgeptr *edge_array, int number_of_edges, int diff)
void sortByDownNodePosition(Edgeptr *edge_array, int num_edges)
Definition: sorting.c:200