V10/cmd/dag/draw_dag.c

#include	"draw_dag.h"

#include	<sys/types.h>
#include	<sys/times.h>
#define TIC 60

int	N_real_nodes,	// actual number of input nodes
	N_nodes,	// number of nodes at various phases
	N_edges,	// total number of edges
	N_self_edges,	// # of loops detected
	N_flat_edges,	// # of edges whose ends are at the same level
	N_repeat_edges,	// # of multi-edges deleted
	N_revert_edges, // # of edges whose direction is reverted
	N_component;	// # of connected components
edge_t	**Inedges,	// in-edges for each node
	**Outedges,	// out-edges
	**Noedges,	// self-edges and flat edges
	**Istems,	// stem edges
	**Ostems;
int	*Stems;
int	*Root,		// space to store union trees of vertices at same ranks
	*Component,	// connected component numbers
	*Invert,	// inversion of nodes in their ranks
	*Level,		// level assignment of nodes
	Maxlevel,	// maximum level assigned to any node
	*N_level,	// number of nodes at each level
	**Rank;		// array of ordered lists of nodes
int	*Nodepos,	// node positions
	*Deleted,	// virtual nodes that were deleted
	*Width,		// widths of nodes
	Nodesep,	// minimum separation between nodes
	*Height,	// height of nodes
	Levelsep,	// separation between levels
	*Levelheight,	// height of layers
	*Levelpos;	// position of levels

int	Xbound,Ybound;	// if "fill" then size of box to fill, else 0

int	Verbose;	// say lots of things

/*
	Draw any directed graphs.
	This function works best with directed acyclic graphs.
	Cycles are broken using a depth-first search.
*/

void draw_dag(int n_nodes, node_t **nodes, edge_t **edges, options_t options)
{
	struct tms begtm, endtm;
	Verbose = options.verbose;

	if(options.verbose)
	{
#ifndef TIMING
		fprintf(stderr,"Start graph drawing\n");
#endif
		times(&begtm);
	}

	// Create Inedges[], Outedges[], Width[], N_nodes, and N_edges
	dag_start(n_nodes,nodes,edges,options);

	// remove stem edges
	if(N_flat_edges <= 0)
		dag_delstem();

	// Create Level[], Maxlevel
	int *srcs = options.source_nodes;
	int source = (srcs && srcs[0] != -1) ? Root[srcs[0]] : -1;
	int *sinks = options.sink_nodes;
	int sink = (sinks && sinks[0] != -1) ? Root[sinks[0]] : -1;
	if(sink == source)
		sink = -1;
	int **same = options.same_nodes;
	dag_levels(source,sink,same ? 1 : 0);

	// Make long edges into short edges by inserting dummy nodes
	dag_unitedges();

	// Create N_level[], Rank[][]
	dag_ranks();

	// reinsert stems
	if(N_flat_edges <= 0)
		dag_insstem();

	// Create Positions[], Maxpos 
	dag_positions(options.ranksep,!options.quick);

	// Create splines
	dag_spline();

	// Return values to user
	dag_end(nodes,edges);

	if(Verbose)
	{
		times(&endtm);
		int total = (endtm.tms_utime-begtm.tms_utime) +
				(endtm.tms_stime-begtm.tms_stime);
		int percent = (total - (total/TIC)*TIC)*100/TIC;
#ifdef TIMING
		fprintf(stderr,"%d.%02d\n",total/TIC, percent);
#else
		fprintf(stderr,"Total time in graph drawing: %d.%02ds\n",
				total/TIC, percent);
#endif
	}
}