Crossings Minimization  1.0
crossing_utilities.c File Reference
#include "graph.h"
#include "defs.h"
#include "crossing_utilities.h"
#include "sorting.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
Include dependency graph for crossing_utilities.c:

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)
 

Function Documentation

◆ add_edges_to_array()

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()

Parameters
edge_arraythe array to which edges are to be added
edges_to_addan array of the edges to be added
num_edgesthe number of edges to add
start_posthe 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().

◆ count_inversions_down()

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 ***].

Parameters
edge_arrayan array of edges sorted by their up nodes
number_of_edgesnumber of edges in the array
diffindicates whether to increment the crossing counts (+1) or decrement them (-1); the latter is used for updates during sifting.
Returns
the total number of crossings (inversions)

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().

Here is the call graph for this function:

◆ count_inversions_up()

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 ***].

Parameters
edge_arrayan array of edges sorted by their down nodes
number_of_edgesnumber of edges in the array
diffindicates whether to increment the crossing counts (+1) or decrement them (-1); the latter is used for updates during sifting.
Returns
the total number of crossings (inversions)

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().

Here is the call graph for this function:

◆ insert_and_count_inversions_down()

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.

Returns
the total number of crossings (inversions)

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().

Here is the call graph for this function:

◆ insert_and_count_inversions_up()

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.

Returns
the total number of crossings (inversions)

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().

Here is the call graph for this function:

◆ update_crossings()

static void update_crossings ( Edgeptr  edge_one,
Edgeptr  edge_two,
int  diff 
)
static

Updates crossings for edges and their endpoints when two edges form an inversion.

Parameters
diffindicates 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().