Crossings Minimization  1.0
swap.c File Reference

Implementation of functions that compute the change in crossing number (or max edge crossings if desired) when two neighboring nodes are swapped. More...

#include "graph.h"
#include "defs.h"
#include "crossings.h"
#include "crossing_utilities.h"
#include "swap.h"
#include "sorting.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <limits.h>
Include dependency graph for swap.c:

Go to the source code of this file.

Functions

void create_sorted_up_edge_array (Edgeptr *edge_array, Nodeptr first_node, Nodeptr second_node)
 
void create_sorted_down_edge_array (Edgeptr *edge_array, Nodeptr first_node, Nodeptr second_node)
 
int edge_crossings_for_node (Nodeptr node)
 
int node_crossings (Nodeptr node_a, Nodeptr node_b)
 
void change_crossings (Nodeptr left_node, Nodeptr right_node, int diff)
 
int edge_crossings_after_swap (Nodeptr left_node, Nodeptr right_node)
 

Detailed Description

Implementation of functions that compute the change in crossing number (or max edge crossings if desired) when two neighboring nodes are swapped.

Author
Matt Stallmann
Date
2011/05/21
Id
swap.c 2 2011-06-07 19:50:41Z mfms

Definition in file swap.c.

Function Documentation

◆ change_crossings()

void change_crossings ( Nodeptr  left_node,
Nodeptr  right_node,
int  diff 
)

Change counts based on crossings when left_node appears to the left and right node to the right.

Parameters
diff+1 to increase crossing counts, -1 to decrease
  • used by mce heuristic only

Definition at line 93 of file swap.c.

References count_inversions_down(), count_inversions_up(), create_sorted_down_edge_array(), create_sorted_up_edge_array(), node_struct::down_degree, node_struct::layer, number_of_layers, and node_struct::up_degree.

Referenced by edge_crossings_after_swap().

Here is the call graph for this function:

◆ create_sorted_down_edge_array()

void create_sorted_down_edge_array ( Edgeptr edge_array,
Nodeptr  first_node,
Nodeptr  second_node 
)

Fills edge_array with downward edges of the two nodes, each set of edges sorted by their endpoint positions on the layer above and those of the first node coming first. Used to compute number of swaps by counting inversions [reference to paper by Jünger and Mutzel needed]

Definition at line 149 of file swap.c.

References add_edges_to_array(), node_struct::down_degree, node_struct::down_edges, and sortByDownNodePosition().

Referenced by change_crossings(), and node_crossings().

Here is the call graph for this function:

◆ create_sorted_up_edge_array()

void create_sorted_up_edge_array ( Edgeptr edge_array,
Nodeptr  first_node,
Nodeptr  second_node 
)

Fills edge_array with upward edges of the two nodes, each set of edges sorted by their endpoint positions on the layer above and those of the first node coming first. Used to compute number of swaps by counting inversions [reference to paper by Jünger and Mutzel needed]

Definition at line 136 of file swap.c.

References add_edges_to_array(), sortByUpNodePosition(), node_struct::up_degree, and node_struct::up_edges.

Referenced by change_crossings(), and node_crossings().

Here is the call graph for this function:

◆ edge_crossings_after_swap()

int edge_crossings_after_swap ( Nodeptr  left_node,
Nodeptr  right_node 
)
Returns
the maximum number of crossings for an edge incident on left_node or right_node after the two are swapped. *** Side effect: crossings on all relevant nodes and edges are updated in accordance with the swap. ***
  • used by mce heuristic only

Definition at line 124 of file swap.c.

References change_crossings(), and edge_crossings_for_node().

Referenced by sift_node_for_edge_crossings().

Here is the call graph for this function:

◆ edge_crossings_for_node()

int edge_crossings_for_node ( Nodeptr  node)
Returns
the maximum number of edge crossings involving this node
  • used by mce heuristic only

Definition at line 43 of file swap.c.

References edge_struct::crossings, node_struct::down_degree, node_struct::down_edges, node_struct::up_degree, and node_struct::up_edges.

Referenced by edge_crossings_after_swap().

◆ node_crossings()

int node_crossings ( Nodeptr  node_a,
Nodeptr  node_b 
)
Returns
the number of crossings among the edges of node_a and node_b if node_a is to the left of node_b

Definition at line 57 of file swap.c.

References count_inversions_down(), count_inversions_up(), create_sorted_down_edge_array(), create_sorted_up_edge_array(), node_struct::down_degree, node_struct::layer, number_of_layers, total_crossings, and node_struct::up_degree.

Referenced by sift(), and swapping_iteration().

Here is the call graph for this function: