Crossings Minimization  1.0
order.c
Go to the documentation of this file.
1 /**
2  * @file order.c
3  * @brief implementation of functions for saving/restoring order
4  * information.
5  * @author Matt Stallmann
6  * @date 2009/07/27
7  * $Id: order.c 2 2011-06-07 19:50:41Z mfms $
8  */
9 
10 #include"order.h"
11 #include"graph.h"
12 
13 #ifdef DEBUG
14 #include"crossings.h"
15 #endif
16 
17 #include<stdio.h>
18 #include<stdlib.h>
19 #include<assert.h>
20 
21 void init_order( Orderptr ord_info )
22 {
23  ord_info->num_layers = number_of_layers;
24  ord_info->num_nodes_on_layer
25  = (int *) calloc( number_of_layers, sizeof(int) );
26  ord_info->node_ptr_on_layer
27  = (Nodeptr * *) calloc( number_of_layers, sizeof(Nodeptr *) );
28  for ( int i = 0; i < number_of_layers; i++ )
29  {
30  ord_info->num_nodes_on_layer[i] = layers[i]->number_of_nodes;
31  ord_info->node_ptr_on_layer[i]
32  = (Nodeptr *) calloc( layers[i]->number_of_nodes, sizeof(Nodeptr) );
33  }
34  save_order( ord_info );
35 }
36 
37 void cleanup_order( Orderptr ord_info )
38 {
39  if ( ord_info->num_layers == 0 ) return;
40  for ( int i = 0; i < ord_info->num_layers; i++ )
41  {
42  free( ord_info->node_ptr_on_layer[i] );
43  }
44  free( ord_info->node_ptr_on_layer );
45  free( ord_info->num_nodes_on_layer );
46 }
47 
48 void save_order( Orderptr ord_info )
49 {
50  ord_info->num_layers = number_of_layers;
51  for ( int i = 0; i < number_of_layers; i++ )
52  {
53  for( int j = 0; j < layers[i]->number_of_nodes; j++ )
54  {
55  Nodeptr node = layers[i]->nodes[j];
56  ord_info->node_ptr_on_layer[i][j] = node;
57  }
58  }
59 }
60 
61 void restore_order( Orderptr ord_info )
62 {
63 #ifdef DEBUG
65  printf( "-> restore_order, num_layers = %d, crossings = %d\n", ord_info->num_layers, numberOfCrossings() );
66 #endif
67  // reorder each layer according to the information stored in ord_info
68  for ( int i = 0; i < ord_info->num_layers; i++ )
69  {
70  for( int j = 0; j < ord_info->num_nodes_on_layer[i]; j++ )
71  {
72  Nodeptr node = ord_info->node_ptr_on_layer[i][j];
73  layers[i]->nodes[j] = node;
74  node->position = j;
75  }
76 #ifdef DEBUG
78  printf( " - restore_order, i = %d, num_nodes = %d, crossings = %d\n",
79  i, ord_info->num_nodes_on_layer[i], numberOfCrossings() );
80 #endif
81  }
82 #ifdef DEBUG
84  printf( "<- restore_order, crossings = %d\n", numberOfCrossings() );
85 #endif
86 }
87 
88 /* [Last modified: 2011 05 23 at 21:09:34 GMT] */
void cleanup_order(Orderptr ord_info)
Definition: order.c:37
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
int position
Definition: graph.h:73
int * num_nodes_on_layer
Definition: order.h:21
int number_of_nodes
Definition: graph_io.c:27
Nodeptr ** node_ptr_on_layer
Definition: order.h:22
void restore_order(Orderptr ord_info)
Definition: order.c:61
Definition of functions that keep track of and update the number of crossings for each node...
data structure and function headers for saving/restoring order information.
Definition of data structures and access functions for a layered graph.
Nodeptr * nodes
Definition: graph.h:116
void save_order(Orderptr ord_info)
Definition: order.c:48
int number_of_layers
Definition: graph_io.c:28
void init_order(Orderptr ord_info)
Definition: order.c:21
void updateAllCrossings(void)
Definition: crossings.c:138
int num_layers
Definition: order.h:20
int numberOfCrossings(void)
Definition: crossings.c:93