Crossings Minimization  1.0
swap.h
Go to the documentation of this file.
1 /**
2  * @file swap.h
3  * @brief Headers of functions that compute the change in crossing
4  * number or max edge crossings when two neighboring nodes are swapped; the
5  * only function used by heuristics that minimize total crossings is
6  * node_crossings()
7  *
8  * @author Matt Stallmann
9  * @date 2011/05/21
10  * $Id: swap.h 2 2011-06-07 19:50:41Z mfms $
11  */
12 
13 #ifndef SWAP_H
14 #define SWAP_H
15 
16 #include"defs.h"
17 #include"graph.h"
18 
19 /**
20  * @return the number of crossings among the edges of node_a and node_b if
21  * node_a is to the left of node_b
22  */
23 int node_crossings( Nodeptr node_a, Nodeptr node_b );
24 
25 /**
26  * Change counts based on crossings when left_node appears to the left and
27  * right node to the right.
28  * @param diff +1 to increase crossing counts, -1 to decrease
29  * - used by mce heuristic only
30  */
31 void change_crossings( Nodeptr left_node, Nodeptr right_node, int diff );
32 
33 /**
34  * @return the maximum number of edge crossings involving this node
35  * - used by mce heuristic only
36  */
38 
39 /**
40  * @return the maximum number of crossings for an edge incident on left_node
41  * or right_node after the two are swapped. *** Side effect: crossings on all
42  * relevant nodes and edges are updated in accordance with the swap. ***
43  * - used by mce heuristic only
44  */
45 int edge_crossings_after_swap( Nodeptr left_node, Nodeptr right_node );
46 
47 #endif
48 
49 /* [Last modified: 2011 05 22 at 17:45:36 GMT] */
int edge_crossings_after_swap(Nodeptr left_node, Nodeptr right_node)
Definition: swap.c:124
void change_crossings(Nodeptr left_node, Nodeptr right_node, int diff)
Definition: swap.c:93
int node_crossings(Nodeptr node_a, Nodeptr node_b)
Definition: swap.c:57
Definitions common to all edge crossing heuristic source files.
Definition of data structures and access functions for a layered graph.
int edge_crossings_for_node(Nodeptr node)
Definition: swap.c:43