Crossings Minimization  1.0
graph.h File Reference

Definition of data structures and access functions for a layered graph. More...

#include <stdbool.h>
#include "defs.h"
Include dependency graph for graph.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  node_struct
struct  edge_struct
struct  layer_struct


#define DEGREE(node)   ( node->up_degree + node->down_degree )
#define CROSSINGS(node)   ( node->up_crossings + node->down_crossings )


typedef struct node_structNodeptr
typedef struct edge_structEdgeptr
typedef struct layer_structLayerptr


int number_of_layers
int number_of_nodes
int number_of_edges
int number_of_isolated_nodes
char graph_name [MAX_NAME_LENGTH]

Detailed Description

Definition of data structures and access functions for a layered graph.

Matt Stallmann, based on Saurabh Gupta's crossing heuristics implementation.
graph.h 90 2014-08-13 20:31:25Z mfms

Global data

  • number_of_layers
  • layers: an array of pointers to layer_struct's
  • graph_name: used for output Layers are referred to by number except when internal info is needed.
    Nodes are referred to by pointers to node_struct's and all information about a node (including layer and position) is stored in the struct.

To traverse all the nodes of a graph, do the following; see also master_node_list:

for( int layer = 0; layer < number_of_layers; layer++ ) { for( int position = 0; position < layers[ layer ]->number_of_nodes; position++ ) { Nodeptr node = layers[ layer ]->nodes[ position ]; do something with the node } }

To traverse all the edges of the graph (as down edges of layers 1 through number_of_layers - 1), do – this is O(m); see also master_edge_list:

for( int layer = 1; layer < number_of_layers; layer++ ) { for( int node_position = 0; node_position < layers[ layer ]->number_of_nodes; node_position++ ) { Nodeptr node = layers[ layer ]->nodes[ node_position ]; for( int edge_position = 0; edge_position < node->down_degree; edge_position++ ) { Edgeptr edge = node->down_edges[ edge_position ]; do something with the edge } } }

Definition in file graph.h.

Macro Definition Documentation


#define CROSSINGS (   node)    ( node->up_crossings + node->down_crossings )

Definition at line 95 of file graph.h.


#define DEGREE (   node)    ( node->up_degree + node->down_degree )

Definition at line 94 of file graph.h.

Typedef Documentation

◆ Edgeptr

typedef struct edge_struct* Edgeptr

Definition at line 58 of file graph.h.

◆ Layerptr

typedef struct layer_struct* Layerptr

Definition at line 59 of file graph.h.

◆ Nodeptr

typedef struct node_struct* Nodeptr

Definition at line 57 of file graph.h.

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().

◆ 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.

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

Definition at line 30 of file graph_io.c.

Referenced by print_graph_statistics(), and readGraph().

◆ number_of_layers

◆ number_of_nodes