Crossings Minimization  1.0
priority_edges.c
Go to the documentation of this file.
1 /**
2  * @file priority_edges.c
3  *
4  * @brief Implementation of unctions for setting up priority edges and
5  * retrieving the number of crossings involving them.
6  *
7  * @author Matthias Stallmann
8  * @date April, 2011
9  * $Id: priority_edges.c 2 2011-06-07 19:50:41Z mfms $
10  */
11 
12 #include"graph.h"
13 #include"defs.h"
14 #include"crossings.h"
15 #include"heuristics.h" /* clearFixedNodes() */
16 #include"priority_edges.h"
17 
18 #include<stdio.h>
19 #include<stdlib.h>
20 #include<assert.h>
21 #include<string.h>
22 
26 
27 void initPriorityEdges( void )
28 {
29  priority_edge_list = (Edgeptr *) malloc( CAPACITY_INCREMENT * sizeof(Edgeptr) );
32 }
33 
34 void freePriorityEdges( void )
35 {
36  free( priority_edge_list );
37  priority_edge_list = NULL;
39 }
40 
42 {
45  priority_edge_list = realloc( priority_edge_list,
47  }
48  priority_edge_list[ number_of_priority_edges++ ] = edge;
49 }
50 
52 {
54 }
55 
56 const Edgeptr * favoredEdges( void )
57 {
58  return priority_edge_list;
59 }
60 
62 {
63  int total_crossings = 0;
64  for ( int i = 0; i < number_of_priority_edges; i++ )
65  total_crossings += priority_edge_list[ i ]->crossings;
66  return total_crossings;
67 }
68 
69 /**
70  * @brief Adds edges along all paths going upward from the node to the
71  * priority list.
72  */
73 static void upDFS( Nodeptr node ) {
74  for ( int i = 0; i < node->up_degree; i++ ) {
75  Edgeptr current_edge = node->up_edges[i];
76  Nodeptr current_node = current_edge->up_node;
77  if ( ! current_node->fixed ) {
78  current_node->fixed = true;
79  addToPriorityEdges( current_edge );
80  upDFS( current_node );
81  }
82  }
83 }
84 
85 /**
86  * @brief Adds edges along all paths going downward from the node to the
87  * priority list.
88  */
89 static void downDFS( Nodeptr node ) {
90  for ( int i = 0; i < node->down_degree; i++ ) {
91  Edgeptr current_edge = node->down_edges[i];
92  Nodeptr current_node = current_edge->down_node;
93  if ( ! current_node->fixed ) {
94  current_node->fixed = true;
95  addToPriorityEdges( current_edge );
96  downDFS( current_node );
97  }
98  }
99 }
100 
101 /* Caution: uses the 'fixed' field of nodes that are encountered during the
102  * search as markers so should not be used in the middle of an mcn or mce
103  * heuristic */
105 {
106  clearFixedNodes();
107  upDFS( node );
108  downDFS( node );
109  clearFixedNodes();
110 }
111 
113  char * file_name_buffer,
114  char * graph_name_buffer,
115  char * comment_buffer
116  )
117 {
118  createDotFileName( file_name_buffer, "favored_edges" );
119  strcpy( graph_name_buffer, graph_name );
120  strcat( graph_name_buffer, "_" );
121  /**
122  * @todo put more information into the graph name and/or comments; also,
123  * most graph names have characters such as - and + in them; these must be
124  * converted to _'s
125  */
126  strcat( graph_name_buffer, "favored_edges" );
127  strcpy( comment_buffer,
128  "Favored edges created as "
129  "ancestors and descendants of a central node" );
130 }
131 
132 /* [Last modified: 2011 04 29 at 19:39:15 GMT] */
Nodeptr up_node
Definition: graph.h:98
int numberOfFavoredEdges(void)
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
const Edgeptr * favoredEdges(void)
static void upDFS(Nodeptr node)
Adds edges along all paths going upward from the node to the priority list.
Functions for setting up priority edges and retrieving the number of crossings involving them...
Edgeptr * down_edges
Definition: graph.h:78
static int number_of_priority_edges
void freePriorityEdges(void)
Definitions common to all edge crossing heuristic source files.
int priorityEdgeCrossings(void)
static Edgeptr * priority_edge_list
void clearFixedNodes(void)
Definition: heuristics.c:315
static int priority_edge_list_capacity
void addToPriorityEdges(Edgeptr edge)
static void downDFS(Nodeptr node)
Adds edges along all paths going downward from the node to the priority list.
CROSSING_STATS_INT total_crossings
Definition: stats.c:147
Edgeptr * up_edges
Definition: graph.h:77
int up_degree
Definition: graph.h:74
bool fixed
Definition: graph.h:85
Definition of functions that keep track of and update the number of crossings for each node...
int down_degree
Definition: graph.h:75
void createDotFileName(char *output_file_name, const char *appendix)
Definition: heuristics.c:83
Definition of data structures and access functions for a layered graph.
#define CAPACITY_INCREMENT
Definition: defs.h:36
static char graph_name[MAX_NAME_LENGTH]
Definition: dot.c:42
void createFavoredEdgeInfo(char *file_name_buffer, char *graph_name_buffer, char *comment_buffer)
Nodeptr down_node
Definition: graph.h:99
void initPriorityEdges(void)
void createFanoutList(Nodeptr node)
Takes all the edges that are accessible via a path from the node and adds them to the priority list...