Crossings Minimization  1.0
graph_io.c File Reference

Implementation of functions that create graph structures from input .dot and .ord files. More...

#include "graph.h"
#include "hash.h"
#include "defs.h"
#include "dot.h"
#include "ord.h"
#include "min_crossings.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
Include dependency graph for graph_io.c:

Go to the source code of this file.

Macros

#define MIN_LAYER_CAPACITY   1
 

Functions

Nodeptr makeNode (const char *name)
 
void addNodeToLayer (Nodeptr node, int layer)
 
void makeLayer ()
 
void addEdge (const char *name1, const char *name2)
 
static void setNumberOfNodes (int layer, int number)
 
static void allocateLayers (const char *ord_file)
 
static void assignNodesToLayers (const char *ord_file)
 
void incrementDegrees (const char *name1, const char *name2)
 
void allocateAdjacencyLists (const char *dot_file)
 
void createEdges (const char *dot_file)
 
static int countIsolatedNodes ()
 
void readGraph (const char *dot_file, const char *ord_file)
 
static void writeNodes (FILE *out, Layerptr layerptr)
 
void writeOrd (const char *ord_file)
 
void writeDot (const char *dot_file_name, const char *graph_name, const char *header_information, Edgeptr *edge_list, int edge_list_length)
 
static void printNode (Nodeptr node)
 
static void printLayer (int layer)
 
void printGraph ()
 

Variables

Nodeptrmaster_node_list
 
Edgeptrmaster_edge_list
 
int number_of_nodes = 0
 
int number_of_layers = 0
 
int number_of_edges = 0
 
int number_of_isolated_nodes = 0
 
Layerptrlayers = NULL
 
char graph_name [MAX_NAME_LENGTH]
 
static int layer_capacity = MIN_LAYER_CAPACITY
 

Detailed Description

Implementation of functions that create graph structures from input .dot and .ord files.

Author
Matt Stallmann, based on Saurabh Gupta's crossing heuristics implementation.
Date
2008/12/19
Id
graph_io.c 97 2014-09-10 17:05:19Z mfms

Definition in file graph_io.c.

Macro Definition Documentation

◆ MIN_LAYER_CAPACITY

#define MIN_LAYER_CAPACITY   1

Definition at line 23 of file graph_io.c.

Referenced by allocateLayers().

Function Documentation

◆ addEdge()

void addEdge ( const char *  name1,
const char *  name2 
)

Adds an edge to the graph. The edge comes directly from the dot file. Although instances usually direct edges from lower to higher layers, no such assumption is made here. A fatal error occurs if the nodes are not on adjacent layers.

Definition at line 135 of file graph_io.c.

References node_struct::down_degree, node_struct::down_edges, edge_struct::down_node, edge_struct::fixed, getFromHashTable(), node_struct::layer, node_struct::name, node_struct::up_degree, node_struct::up_edges, and edge_struct::up_node.

Referenced by createEdges().

Here is the call graph for this function:

◆ addNodeToLayer()

void addNodeToLayer ( Nodeptr  node,
int  layer 
)

Put a node in the next available position on a given layer

Definition at line 107 of file graph_io.c.

References node_struct::layer, layer_struct::nodes, and node_struct::position.

Referenced by assignNodesToLayers().

◆ allocateAdjacencyLists()

void allocateAdjacencyLists ( const char *  dot_file)

Reads the dot file and makes room for nodes on all the adjacency lists; resets up and down node degrees. This is the first pass of reading the dot file. Also saves the name of the graph.

Definition at line 272 of file graph_io.c.

References node_struct::down_degree, node_struct::down_edges, getNameFromDotFile(), graph_name, incrementDegrees(), initDot(), MAX_NAME_LENGTH, nextEdge(), layer_struct::nodes, number_of_edges, number_of_layers, layer_struct::number_of_nodes, node_struct::up_degree, and node_struct::up_edges.

Referenced by readGraph().

Here is the call graph for this function:

◆ allocateLayers()

static void allocateLayers ( const char *  ord_file)
static

Implements the first pass of reading the ord file: allocates a record for each layer and space for the nodes on each layer. Creates the nodes and maps their names to (pointers to) their records. Counts the total number of nodes.

Definition at line 186 of file graph_io.c.

References layer_capacity, makeLayer(), MAX_NAME_LENGTH, MIN_LAYER_CAPACITY, nextLayer(), nextNode(), number_of_nodes, and setNumberOfNodes().

Referenced by readGraph().

Here is the call graph for this function:

◆ assignNodesToLayers()

static void assignNodesToLayers ( const char *  ord_file)
static

Reads the ord file and put the nodes on their appropriate layers

Definition at line 224 of file graph_io.c.

References addNodeToLayer(), makeNode(), MAX_NAME_LENGTH, nextLayer(), and nextNode().

Referenced by readGraph().

Here is the call graph for this function:

◆ countIsolatedNodes()

static int countIsolatedNodes ( )
static
Returns
number of nodes whose up_degree and down_degree are both zero
Todo:
Should eliminate the isolated nodes altogether; on each layer -
 deallocate isolated nodes and mark positions with NULL
 position = real_position = 0;
 for position < number_of_nodes, position++
    while real_position < number_of_nodes and node[position] == NULL
       real_position++
    if node[position] == NULL && real_position < number_of_nodes
       node[position] = node[real_position++]

Definition at line 333 of file graph_io.c.

References node_struct::down_degree, layer_struct::nodes, number_of_layers, layer_struct::number_of_nodes, and node_struct::up_degree.

Referenced by readGraph().

◆ createEdges()

void createEdges ( const char *  dot_file)

Reads the dot file and adds all the edges. This is the second pass.

Definition at line 316 of file graph_io.c.

References addEdge(), initDot(), MAX_NAME_LENGTH, and nextEdge().

Referenced by readGraph().

Here is the call graph for this function:

◆ incrementDegrees()

void incrementDegrees ( const char *  name1,
const char *  name2 
)

Increments the degrees of the endpoints of an edge between name1 and name2

Definition at line 243 of file graph_io.c.

References node_struct::down_degree, getFromHashTable(), node_struct::layer, and node_struct::up_degree.

Referenced by allocateAdjacencyLists().

Here is the call graph for this function:

◆ makeLayer()

void makeLayer ( )

Creates a new layer; the number is assumed to be the next available layer number, i.e., layers are always created in ascending numerical order

Definition at line 121 of file graph_io.c.

References layer_capacity, layer_struct::nodes, number_of_layers, and layer_struct::number_of_nodes.

Referenced by allocateLayers().

◆ makeNode()

Nodeptr makeNode ( const char *  name)

Creates a new node and maps its name to (a pointer to) its record

Parameters
namethe name of the node
Returns
(a pointer to) the newly created node

Definition at line 86 of file graph_io.c.

References node_struct::down_crossings, node_struct::down_degree, node_struct::down_edges, node_struct::fixed, node_struct::id, insertInHashTable(), node_struct::layer, node_struct::marked, node_struct::name, node_struct::position, node_struct::preorder_number, node_struct::up_crossings, node_struct::up_degree, and node_struct::up_edges.

Referenced by assignNodesToLayers().

Here is the call graph for this function:

◆ printGraph()

void printGraph ( )

Prints the graph in a verbose format on standard output for debugging purposes. May also be used for piping to a graphical trace later.

Definition at line 486 of file graph_io.c.

References getAverageNumberOfProbes(), graph_name, main(), number_of_layers, number_of_nodes, printGraph(), printLayer(), and readGraph().

Referenced by printGraph().

Here is the call graph for this function:

◆ printLayer()

static void printLayer ( int  layer)
static

Definition at line 475 of file graph_io.c.

References number_of_nodes, layer_struct::number_of_nodes, and printNode().

Referenced by printGraph().

Here is the call graph for this function:

◆ printNode()

◆ readGraph()

void readGraph ( const char *  dot_file,
const char *  ord_file 
)

Reads the graph from the given files, specified by their names. Each file is read twice so that arrays can be allocated to the correct size on the first pass. Also initializes all graph-related data structures and global variables.

Definition at line 363 of file graph_io.c.

References allocateAdjacencyLists(), allocateLayers(), assignNodesToLayers(), countIsolatedNodes(), createEdges(), initHashTable(), number_of_edges, number_of_isolated_nodes, number_of_layers, number_of_nodes, and removeHashTable().

Referenced by main(), printCrossings(), and printGraph().

Here is the call graph for this function:

◆ setNumberOfNodes()

static void setNumberOfNodes ( int  layer,
int  number 
)
static

Sets number of nodes for the layer and allocates space for them. Note: the global number of nodes is updated in allocateLayers().

Definition at line 174 of file graph_io.c.

References layer_struct::nodes, and layer_struct::number_of_nodes.

Referenced by allocateLayers().

◆ writeDot()

void writeDot ( const char *  dot_file_name,
const char *  graph_name,
const char *  header_information,
Edgeptr edge_list,
int  edge_list_length 
)

Definition at line 424 of file graph_io.c.

References dotPreamble(), edge_struct::down_node, endDot(), node_struct::name, outputEdge(), and edge_struct::up_node.

Referenced by create_random_tree(), and main().

Here is the call graph for this function:

◆ writeNodes()

static void writeNodes ( FILE *  out,
Layerptr  layerptr 
)
static

Definition at line 389 of file graph_io.c.

References node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, and outputNode().

Referenced by writeOrd().

Here is the call graph for this function:

◆ writeOrd()

void writeOrd ( const char *  ord_file)
Todo:
ord file should have information about heuristic that created it, etc., embedded in it. Use of the file/graph name can be problematic if we want to check what happens when one heuristic follows another for a whole class using a script. There needs to be some way to differentiate among these files.

Definition at line 405 of file graph_io.c.

References beginLayer(), endLayer(), graph_name, number_of_layers, ordPreamble(), and writeNodes().

Referenced by create_random_tree(), end_of_iteration(), and main().

Here is the call graph for this function:

Variable Documentation

◆ graph_name

char graph_name[MAX_NAME_LENGTH]

Definition at line 32 of file graph_io.c.

Referenced by allocateAdjacencyLists(), printGraph(), and writeOrd().

◆ layer_capacity

int layer_capacity = MIN_LAYER_CAPACITY
static

Definition at line 35 of file graph_io.c.

Referenced by allocateLayers(), and makeLayer().

◆ layers

◆ master_edge_list

◆ master_node_list

Nodeptr* master_node_list

Allows nodes to be accessed randomly by their unique id #'s; not used for anything at this point.

Todo:
this and master_edge_list could really be useful for heuristics such as mcn and mce.

Definition at line 25 of file graph_io.c.

Referenced by add_edges(), add_node_to_list(), assign_child_layer_and_direction(), create_master_node_list(), create_random_dag(), create_random_tree(), maxCrossingsNode(), and sifting().

◆ number_of_edges

◆ number_of_isolated_nodes

int number_of_isolated_nodes = 0

Definition at line 30 of file graph_io.c.

Referenced by print_graph_statistics(), and readGraph().

◆ number_of_layers

◆ number_of_nodes