Crossings Minimization  1.0
ord.c
Go to the documentation of this file.
1 /// @file ord.c
2 /// @brief implementation of utility functions that read and write .ord
3 /// files (node ordering on layers of a graph)
4 /// @author Matt Stallmann
5 /// @date 1 Jan 1999
6 ///
7 /// $Id: ord.c 97 2014-09-10 17:05:19Z mfms $
8 
9 // Copyright (C) 2001 Matthias Stallmann.
10 // Contact: matt_stallmann@ncsu.edu
11 //
12 // This program is free software; you can redistribute it and/or modify
13 // it under the terms of the GNU General Public License as published by
14 // the Free Software Foundation; either version 2 of the License, or
15 // (at your option) any later version.
16 //
17 // This program is distributed in the hope that it will be useful,
18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 // GNU General Public License for more details.
21 //
22 // You should have received a copy of the GNU General Public License along
23 // with this program (file COPYING.txt); if not, write to the Free Software
24 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
25 // USA.
26 
27 // 20 May 2002 - added get_graph_name()
28 // 09 Sep 2008 - modified as a C implementation
29 
30 #include"defs.h"
31 #include"ord.h"
32 #include<stdlib.h> // abort()
33 #include<stdio.h>
34 #include<string.h>
35 #include<ctype.h>
36 #include<assert.h>
37 
38 const char * ORD_SUFFIX = ".ord";
39  // suffix for ordering files
40 
41 // characters with special meaning
42 const char NULL_CHAR = '\0';
43 const char BLANK_CHAR = ' ';
44 const char COMMENT_CHAR = '#';
45 const char END_OF_LINE = '\n';
46 const char OPEN_LIST = '{';
47 const char CLOSE_LIST = '}';
48 
49 static char name_buffer[MAX_NAME_LENGTH]; // used to report graph name
50 static bool valid_name = false; // true if an actual name was found
51 
52 static bool eatSpaceAndComments( FILE * in )
53  // POST: 'in' is at the first non-blank character after its initial
54  // position (with comments excluded);
55  // retval == true iff there is another non-blank character before
56  // the end of file
57 {
58  static bool first_comment = true; // name appears at the end of first comment
59  enum { NOT_IN_COMMENT, IN_COMMENT } local_state = NOT_IN_COMMENT;
60  int ch;
61  int index = 0;
62  while ( (ch = getc( in )) != EOF ) {
63  switch ( local_state ) {
64  case NOT_IN_COMMENT:
65  if ( COMMENT_CHAR == ch ) local_state = IN_COMMENT;
66  else if ( ! isspace( ch ) ) {
67  ungetc( ch, in );
68  return true;
69  }
70  break;
71  case IN_COMMENT:
72  if ( END_OF_LINE == ch ) local_state = NOT_IN_COMMENT;
73  // if this is the first comment line, save the last "word" -- it's
74  // the name of the graph.
75  if( first_comment ) {
76  if ( END_OF_LINE == ch ) {
77  name_buffer[index] = NULL_CHAR;
78  if( index > 0 ) {
79  valid_name = true;
80  }
81  first_comment = false;
82  }
83  else if ( BLANK_CHAR == ch ) {
84  index = 0;
85  }
86  else {
87  name_buffer[index++] = ch;
88  }
89  } // if this is the first comment
90  break;
91  default: assert( "bad local state" && false );
92  }
93  }
94  return false;
95 }
96 
97 bool getGraphName( FILE * in, char * buffer ) {
98  eatSpaceAndComments( in );
99  if( valid_name ) {
100  strcpy( buffer, name_buffer );
101  return true;
102  }
103  return false;
104 }
105 
106 static enum { OUTSIDE_LAYER,
109 
110 static int hold_layer = -1; // most recent layer number encountered
111 
112 bool nextLayer( FILE * in, int * layer )
113 {
114  * layer = -1;
115  int ch;
116  while ( eatSpaceAndComments( in ) && (ch = getc( in )) != EOF ) {
117  switch ( state ) {
118  case OUTSIDE_LAYER:
119  ungetc( ch, in ); // put back first digit of expected int
120  fscanf( in, "%d", layer );
121  hold_layer = * layer;
123  break;
124  case LAYER_NUMBER:
125  if ( OPEN_LIST == ch ) {
127  assert( * layer >= 0 );
128  return true;
129  }
130  else {
131  fprintf( stderr, "\nRead error in .ord file: %d"
132  " expected, reading %c instead.", OPEN_LIST, ch );
133  abort();
134  }
135  break;
136  case INSIDE_LAYER:
137  if ( CLOSE_LIST == ch )
138  state = OUTSIDE_LAYER;
139  break;
140  default: assert( "bad state" && false );
141  }
142  }
143  return false;
144 }
145 
146 bool nextNode( FILE * in, char * node_buffer )
147 {
148  assert( INSIDE_LAYER == state );
149  if ( ! eatSpaceAndComments( in ) ) {
150  fprintf( stderr, "Read error in .ord file: unexpected end of file\n"
151  "while reading nodes in layer %d\n", hold_layer );
152  abort();
153  }
154  int index = 0;
155  int ch;
156  while ( (ch = getc( in )) != EOF ) {
157  if ( CLOSE_LIST == ch || COMMENT_CHAR == ch || isspace( ch ) ) {
158  ungetc( ch, in );
159  if ( 0 == index )
160  return false;
161  node_buffer[ index ] = '\0';
162 #ifdef DEBUG
163  printf( "<- nextNode: %s\n", node_buffer );
164 #endif
165  return true;
166  }
167  else {
168  node_buffer[ index++ ] = ch;
169  }
170  }
171  // should never get here
172  assert( false && "Unexpected end of file while reading layer\n" );
173  return false;
174 }
175 
176 static int current_column = 0; // keeps track of column while printing
177 static int number_of_nodes = 0; // number of nodes on current line
178 static int output_layer = -1; // current layer during output
179 
180 void ordPreamble( FILE * out, const char * graph_name,
181  const char * generation_method )
182 {
183  fprintf( out, "# Ordering for graph %s\n", graph_name );
184  fprintf( out, "# %s\n\n", generation_method );
185 }
186 
187 void beginLayer( FILE * out, int layer, const char * type )
188 {
189  fprintf( out, "# Order for layer %d: %s\n", layer, type );
190  fprintf( out, "%d {\n ", layer );
191  output_layer = layer;
192  current_column = 0;
193  number_of_nodes = 0;
194 }
195 
196 void endLayer( FILE * out )
197 {
198  assert( 0 <= output_layer );
199  if ( 0 < number_of_nodes ) fprintf( out, "\n" );
200  fprintf( out, "} # end of layer %d\n\n", output_layer );
201  output_layer = -1;
202 }
203 
204 void outputNode( FILE * out, const char * node )
205 {
206  assert( 0 <= output_layer );
207  if ( 0 < number_of_nodes
208  && LINE_LENGTH <= current_column + (int) strlen( node ) ) {
209  fprintf( out, "\n" );
210  current_column = 0;
211  number_of_nodes = 0;
212  }
213  if ( 0 < number_of_nodes ) {
214  fprintf( out, " " );
215  ++current_column;
216  }
217  fprintf( out, "%s", node );
218  current_column += strlen( node );
219  ++number_of_nodes;
220 }
221 
222 // [Last modified: 2014 09 10 at 14:15:06 GMT]
void beginLayer(FILE *out, int layer, const char *type)
Definition: ord.c:187
void ordPreamble(FILE *out, const char *graph_name, const char *generation_method)
Definition: ord.c:180
static char buffer[MAX_NAME_LENGTH]
Definition: heuristics.c:59
const char BLANK_CHAR
Definition: ord.c:43
static char name_buffer[MAX_NAME_LENGTH]
Definition: ord.c:49
static int current_column
Definition: ord.c:176
bool nextLayer(FILE *in, int *layer)
Definition: ord.c:112
Definitions common to all edge crossing heuristic source files.
void endLayer(FILE *out)
Definition: ord.c:196
#define LINE_LENGTH
Definition: defs.h:34
const char COMMENT_CHAR
Definition: ord.c:44
static enum @0 state
static int output_layer
Definition: ord.c:178
static int hold_layer
Definition: ord.c:110
const char NULL_CHAR
Definition: ord.c:42
const char CLOSE_LIST
Definition: ord.c:47
bool nextNode(FILE *in, char *node_buffer)
Definition: ord.c:146
static int number_of_nodes
Definition: ord.c:177
static char graph_name[MAX_NAME_LENGTH]
Definition: dot.c:42
static bool valid_name
Definition: ord.c:50
void outputNode(FILE *out, const char *node)
Definition: ord.c:204
const char OPEN_LIST
Definition: ord.c:46
header for utility functions that read and write .ord files (node ordering on layers of a graph) ...
const char * ORD_SUFFIX
Definition: ord.c:38
#define MAX_NAME_LENGTH
Definition: defs.h:32
bool getGraphName(FILE *in, char *buffer)
Definition: ord.c:97
const char END_OF_LINE
Definition: ord.c:45
static bool eatSpaceAndComments(FILE *in)
Definition: ord.c:52