Crossings Minimization  1.0
sorting.c File Reference

Interface for functions that perform various sorts. All sorts are stable. More...

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "sorting.h"
#include "graph.h"
Include dependency graph for sorting.c:

Go to the source code of this file.

Functions

static bool insertion_sort (void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
 
static bool unstable_insertion_sort (void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
 
static int compare_weights (const void *ptr_i, const void *ptr_j)
 
static int compare_degrees (const void *ptr_i, const void *ptr_j)
 
static int compare_down_edges (const void *ptr_i, const void *ptr_j)
 
static int compare_up_edges (const void *ptr_i, const void *ptr_j)
 
void updateAllPositions (void)
 
void updateNodePositions (int layer)
 
void layerSort (int layer)
 
void layerUnstableSort (int layer)
 
void layerQuicksort (int layer)
 
void sortByDownNodePosition (Edgeptr *edge_array, int num_edges)
 
void sortByUpNodePosition (Edgeptr *edge_array, int num_edges)
 
void sortByDegree (Nodeptr *node_array, int num_nodes)
 

Detailed Description

Interface for functions that perform various sorts. All sorts are stable.

Author
Matthias Stallmann
Date
2009/01/03
Id
sorting.c 76 2014-07-21 21:10:32Z mfms

Definition in file sorting.c.

Function Documentation

◆ compare_degrees()

static int compare_degrees ( const void *  ptr_i,
const void *  ptr_j 
)
static

Comparison function to be used by qsort to compare degrees of nodes.

Definition at line 99 of file sorting.c.

References node_struct::down_degree, and node_struct::up_degree.

Referenced by sortByDegree().

◆ compare_down_edges()

static int compare_down_edges ( const void *  ptr_i,
const void *  ptr_j 
)
static

Comparison function to be used by qsort to compare the weights of two nodes. Assumes that each array element is a pointer to a node.

Definition at line 115 of file sorting.c.

References edge_struct::down_node, and node_struct::position.

Referenced by sortByDownNodePosition().

◆ compare_up_edges()

static int compare_up_edges ( const void *  ptr_i,
const void *  ptr_j 
)
static

Comparison function to be used by qsort to compare the weights of two nodes. Assumes that each array element is a pointer to a node.

Definition at line 130 of file sorting.c.

References node_struct::position, and edge_struct::up_node.

Referenced by sortByUpNodePosition().

◆ compare_weights()

static int compare_weights ( const void *  ptr_i,
const void *  ptr_j 
)
static

Comparison function to be used by qsort or insertion_sort to compare the weights of two nodes. Assumes that each array element is a pointer to a node. Insertion sort is preferred in most cases because it is stable (and usually does not increase the asymptotic time).

Definition at line 86 of file sorting.c.

References node_struct::weight.

Referenced by layerQuicksort(), layerSort(), and layerUnstableSort().

◆ insertion_sort()

static bool insertion_sort ( void *  base,
size_t  nmemb,
size_t  size,
int(*)(const void *, const void *)  compar 
)
static

Performs an insertion sort using the same argument types as qsort

Returns
true if the original order has changed

Definition at line 22 of file sorting.c.

Referenced by layerSort(), sortByDownNodePosition(), and sortByUpNodePosition().

◆ layerQuicksort()

void layerQuicksort ( int  layer)

Sorts the nodes of the given layer by increasing weight and updates the position fields of the nodes accordingly. Uses Quicksort.

Definition at line 189 of file sorting.c.

References compare_weights(), layers, layer_struct::nodes, layer_struct::number_of_nodes, and updateNodePositions().

Referenced by middleDegreeSort().

Here is the call graph for this function:

◆ layerSort()

void layerSort ( int  layer)

Sorts the nodes of the given layer by increasing weight and updates the position fields of the nodes accordingly. Uses insertion sort.

Definition at line 159 of file sorting.c.

References compare_weights(), node_struct::id, insertion_sort(), layers, layer_struct::nodes, layer_struct::number_of_nodes, updateNodePositions(), and node_struct::weight.

Referenced by barycenterDownSweep(), barycenterUpSweep(), depthFirstSearch(), evenOddBarycenter(), medianDownSweep(), medianUpSweep(), modifiedBarycenter(), rotatingBarycenter(), slab_bary_iteration(), staticBarycenter(), and upDownBarycenter().

Here is the call graph for this function:

◆ layerUnstableSort()

void layerUnstableSort ( int  layer)

Sorts the nodes of the given layer by increasing weight and updates the position fields of the nodes accordingly. Uses insertion sort with equal elements in reverse order.

Definition at line 181 of file sorting.c.

References compare_weights(), layers, layer_struct::nodes, layer_struct::number_of_nodes, unstable_insertion_sort(), and updateNodePositions().

Here is the call graph for this function:

◆ sortByDegree()

void sortByDegree ( Nodeptr node_array,
int  num_nodes 
)

Sorts the array of nodes by increasing degree

Definition at line 215 of file sorting.c.

References compare_degrees().

Referenced by middleDegreeSort(), and sifting().

Here is the call graph for this function:

◆ sortByDownNodePosition()

void sortByDownNodePosition ( Edgeptr edge_array,
int  num_edges 
)

Sort the array of edges by the positions of the nodes on the lower layer

Definition at line 200 of file sorting.c.

References compare_down_edges(), and insertion_sort().

Referenced by create_sorted_down_edge_array(), lower_median(), and updateCrossingsBetweenLayers().

Here is the call graph for this function:

◆ sortByUpNodePosition()

void sortByUpNodePosition ( Edgeptr edge_array,
int  num_edges 
)

Sort the array of edges by the positions of the nodes on the upper layer

Definition at line 209 of file sorting.c.

References compare_up_edges(), and insertion_sort().

Referenced by create_sorted_up_edge_array(), and upper_median().

Here is the call graph for this function:

◆ unstable_insertion_sort()

static bool unstable_insertion_sort ( void *  base,
size_t  nmemb,
size_t  size,
int(*)(const void *, const void *)  compar 
)
static

Performs an "unstable" insertion sort using the same argument types as qsort; unstable means that elements with equal keys will be put in reverse of their original order

Returns
true if the original order has changed

Definition at line 54 of file sorting.c.

Referenced by layerUnstableSort().

◆ updateAllPositions()

void updateAllPositions ( void  )

Updates position fields for all nodes

Definition at line 141 of file sorting.c.

References number_of_layers, and updateNodePositions().

Referenced by updateAllCrossings().

Here is the call graph for this function:

◆ updateNodePositions()

void updateNodePositions ( int  layer)

Updates the position field of each node on the layer to reflect the current position in the nodes array.

Definition at line 149 of file sorting.c.

References layers, layer_struct::nodes, layer_struct::number_of_nodes, and node_struct::position.

Referenced by layerQuicksort(), layerSort(), layerUnstableSort(), updateAllPositions(), and updateCrossingsForLayer().