Crossings Minimization
1.0

#include "graph.h"
#include "defs.h"
#include "crossing_utilities.h"
#include "sorting.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
Go to the source code of this file.
Functions  
static void  update_crossings (Edgeptr edge_one, Edgeptr edge_two, int diff) 
int  insert_and_count_inversions_down (Edgeptr *edge_array, int starting_index, int diff) 
int  count_inversions_down (Edgeptr *edge_array, int number_of_edges, int diff) 
int  insert_and_count_inversions_up (Edgeptr *edge_array, int starting_index, int diff) 
int  count_inversions_up (Edgeptr *edge_array, int number_of_edges, int diff) 
void  add_edges_to_array (Edgeptr *edge_array, Edgeptr *edges_to_add, int num_edges, int start_pos) 
void add_edges_to_array  (  Edgeptr *  edge_array, 
Edgeptr *  edges_to_add,  
int  num_edges,  
int  start_pos  
) 
Adds edges to an array of edges. Assumes that there is enough space in the array. Similar to strcat()
edge_array  the array to which edges are to be added 
edges_to_add  an array of the edges to be added 
num_edges  the number of edges to add 
start_pos  the starting position at which the edges are to be added. 
Definition at line 148 of file crossing_utilities.c.
Referenced by create_sorted_down_edge_array(), create_sorted_up_edge_array(), and updateCrossingsBetweenLayers().
int count_inversions_down  (  Edgeptr *  edge_array, 
int  number_of_edges,  
int  diff  
) 
Counts the inversions when an array of edges and updates crossings for the edges and their nodes accordingly [*** this is a side effect ***].
edge_array  an array of edges sorted by their up nodes 
number_of_edges  number of edges in the array 
diff  indicates whether to increment the crossing counts (+1) or decrement them (1); the latter is used for updates during sifting. 
Definition at line 85 of file crossing_utilities.c.
References insert_and_count_inversions_down(), and number_of_edges.
Referenced by change_crossings(), node_crossings(), and updateCrossingsBetweenLayers().
int count_inversions_up  (  Edgeptr *  edge_array, 
int  number_of_edges,  
int  diff  
) 
Counts the inversions when an array of edges and updates crossings for the edges and their nodes accordingly [*** this is a side effect ***].
edge_array  an array of edges sorted by their down nodes 
number_of_edges  number of edges in the array 
diff  indicates whether to increment the crossing counts (+1) or decrement them (1); the latter is used for updates during sifting. 
Definition at line 128 of file crossing_utilities.c.
References insert_and_count_inversions_up(), and number_of_edges.
Referenced by change_crossings(), and node_crossings().
int insert_and_count_inversions_down  (  Edgeptr *  edge_array, 
int  starting_index,  
int  diff  
) 
Inserts the edge at starting_index into the already sorted edges with indices 0, ..., starting_index  1. Sort is by down_node. Each inversion either increments (diff=1) or decrements (diff=1) the number of crossings for the edges involved and their endpoints.
Definition at line 65 of file crossing_utilities.c.
References edge_struct::down_node, node_struct::position, and update_crossings().
Referenced by count_inversions_down().
int insert_and_count_inversions_up  (  Edgeptr *  edge_array, 
int  starting_index,  
int  diff  
) 
Inserts the edge at starting_index into the already sorted edges with indices 0, ..., starting_index  1. Sort is by up_node. Each inversion either increments (diff=1) or decrements (diff=1) the number of crossings for the edges involved and their endpoints.
Definition at line 109 of file crossing_utilities.c.
References node_struct::position, edge_struct::up_node, and update_crossings().
Referenced by count_inversions_up().
Updates crossings for edges and their endpoints when two edges form an inversion.
diff  indicates whether to increment the number of crossings for nodes and edges (+1) or decrement them (1) 
Definition at line 51 of file crossing_utilities.c.
References edge_struct::crossings, node_struct::down_crossings, edge_struct::down_node, node_struct::up_crossings, and edge_struct::up_node.
Referenced by insert_and_count_inversions_down(), and insert_and_count_inversions_up().