Crossings Minimization  1.0
swap.h File Reference

Headers of functions that compute the change in crossing number or max edge crossings when two neighboring nodes are swapped; the only function used by heuristics that minimize total crossings is node_crossings() More...

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

Go to the source code of this file.

Functions

int node_crossings (Nodeptr node_a, Nodeptr node_b)
 
void change_crossings (Nodeptr left_node, Nodeptr right_node, int diff)
 
int edge_crossings_for_node (Nodeptr node)
 
int edge_crossings_after_swap (Nodeptr left_node, Nodeptr right_node)
 

Detailed Description

Headers of functions that compute the change in crossing number or max edge crossings when two neighboring nodes are swapped; the only function used by heuristics that minimize total crossings is node_crossings()

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

Definition in file swap.h.

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:

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