Crossings Minimization  1.0
crossing_utilities.h File Reference

Definition of functions that are used to count and update crossings locally. Used both by crossings.c and by sifting.c. More...

#include <stdbool.h>
#include "defs.h"
#include "graph.h"
Include dependency graph for crossing_utilities.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

int count_inversions_up (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_down (Edgeptr *edge_array, int number_of_edges, int diff)
 
int insert_and_count_inversions_down (Edgeptr *edge_array, int starting_index, int diff)
 
void add_edges_to_array (Edgeptr *edge_array, Edgeptr *edges_to_add, int num_edges, int start_pos)
 

Detailed Description

Definition of functions that are used to count and update crossings locally. Used both by crossings.c and by sifting.c.

Author
Matt Stallmann
Date
2009/05/15
Id
crossing_utilities.h 56 2014-03-13 21:12:01Z mfms

Definition in file crossing_utilities.h.

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: