Crossings Minimization  1.0
sorting.h File Reference

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

#include "graph.h"
Include dependency graph for sorting.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void layerSort (int layer)
 
void layerQuicksort (int layer)
 
void layerUnstableSort (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)
 
void updateNodePositions (int layer)
 
void updateAllPositions (void)
 

Detailed Description

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

Author
Matthias Stallmann
Date
2009/01/03
Id
sorting.h 28 2011-07-18 19:52:04Z mfms

Definition in file sorting.h.

Function Documentation

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

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

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 
)

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

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:

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