Graphviz: lib/dotgen/mincross.c File Reference

Searching...

No Matches

#include "config.h"
#include <assert.h>
#include <cgraph/cgraph.h>
#include <common/utils.h>
#include <dotgen/dot.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <util/alloc.h>
#include <util/bitarray.h>
#include <util/exit.h>
#include <util/gv_math.h>
#include <util/itos.h>
#include <util/list.h>
#include <util/streq.h>

Include dependency graph for mincross.c:

Go to the source code of this file.

Data Structures
struct	adjmatrix_t

struct	info_t

Macros
#define	MARK(v) (ND_mark(v))

#define	saveorder(v) (ND_coord(v)).x

#define	flatindex(v) ((size_t)ND_low(v))

#define	ND_x(n) (((info_t *)AGDATA(n))->x)

#define	ND_lo(n) (((info_t *)AGDATA(n))->lo)

#define	ND_hi(n) (((info_t *)AGDATA(n))->hi)

#define	ND_np(n) (((info_t *)AGDATA(n))->np)

#define	ND_idx(n) (ND_order(ND_np(n)))

#define	isBackedge(e) (ND_idx(aghead(e)) > ND_idx(agtail(e)))

#define	VAL(node, port) (MC_SCALE * ND_order(node) + (port).order)

#define	ORDINARY 0

#define	SINGLETON 1

#define	VIRTUALNODE 2

#define	NTYPES 3

#define	C_EE 1

#define	C_VS 2

#define	C_SS 2

#define	C_VV 4

Functions
static bool	matrix_get (adjmatrix_t *me, size_t row, size_t col)

static void	matrix_set (adjmatrix_t *me, size_t row, size_t col)

static bool	medians (graph_t *g, int r0, int r1)

static int	nodeposcmpf (const void , const void )

static int	edgeidcmpf (const void , const void )

static void	flat_breakcycles (graph_t *g)

static void	flat_reorder (graph_t *g)

static void	flat_search (graph_t g, node_t v)

static void	init_mincross (graph_t *g)

static void	merge2 (graph_t *g)

static void	init_mccomp (graph_t *g, size_t c)

static void	cleanup2 (graph_t *g, int64_t nc, bool have_vlists)

static int64_t	mincross_clust (graph_t *g)

static int64_t	mincross (graph_t *g, int startpass)

static void	mincross_step (graph_t *g, int pass)

static void	mincross_options (graph_t *g)

static void	save_best (graph_t *g)

static void	restore_best (graph_t *g)

static adjmatrix_t *	new_matrix (size_t initial_rows, size_t initial_columns)

static void	free_matrix (adjmatrix_t *p)

static int	ordercmpf (const void , const void )

static int64_t	ncross (void)

static void	emptyComp (graph_t *sg)

static Agnode_t *	findSource (Agraph_t g, Agraph_t sg)

typedef	LIST (node_t *)

static int	getComp (graph_t g, node_t n, graph_t comp, int indices)

static void	fixLabelOrder (graph_t g, rank_t rk)
	for each pair of nodes (labels), we add an edge

void	checkLabelOrder (graph_t *g)

int	dot_mincross (graph_t *g)

static int	betweenclust (edge_t *e)

static void	do_ordering_node (graph_t g, node_t n, bool outflag)

static void	do_ordering (graph_t *g, bool outflag)

static void	do_ordering_for_nodes (graph_t *g)

static void	ordered_edges (graph_t *g)

static bool	left2right (graph_t g, node_t v, node_t *w)

static int64_t	in_cross (node_t v, node_t w)

static int	out_cross (node_t v, node_t w)

static void	exchange (node_t v, node_t w)

static int64_t	transpose_step (graph_t *g, int r, bool reverse)

static void	transpose (graph_t *g, bool reverse)

static void	merge_components (graph_t *g)

static node_t *	neighbor (node_t *v, int dir)

static bool	is_a_normal_node_of (graph_t g, node_t v)

static bool	is_a_vnode_of_an_edge_of (graph_t g, node_t v)

static bool	inside_cluster (graph_t g, node_t v)

static node_t *	furthestnode (graph_t g, node_t v, int dir)

void	save_vlist (graph_t *g)

void	rec_save_vlists (graph_t *g)

void	rec_reset_vlists (graph_t *g)

static Agraph_t *	realFillRanks (Agraph_t g, bitarray_t ranks, Agraph_t *sg)

static void	fillRanks (Agraph_t *g)

static void	flat_rev (Agraph_t g, Agedge_t e)

void	allocate_ranks (graph_t *g)

int	install_in_rank (graph_t g, node_t n)

int	build_ranks (graph_t *g, int pass)

void	enqueue_neighbors (node_queue_t q, node_t n0, int pass)

static bool	constraining_flat_edge (Agraph_t g, Agedge_t e)

static void	postorder (graph_t g, node_t v, nodes_t *list, int r)

static void	reorder (graph_t *g, int r, bool reverse, bool hasfixed)

static int	local_cross (elist l, int dir)

static int64_t	rcross (graph_t *g, int r)

static bool	flat_mval (node_t *n)

static int	endpoint_class (node_t *n)

void	virtual_weight (edge_t *e)

Variables
static int	MinQuit

static const double	Convergence = .995

static graph_t *	Root

static int	GlobalMinRank

static int	GlobalMaxRank

static edge_t **	TE_list

static int *	TI_list

static bool	ReMincross

static const int	table [NTYPES][NTYPES]

Macro Definition Documentation

◆ C_EE

#define C_EE 1

Definition at line 1696 of file mincross.c.

◆ C_SS

#define C_SS 2

Definition at line 1698 of file mincross.c.

◆ C_VS

#define C_VS 2

Definition at line 1697 of file mincross.c.

◆ C_VV

#define C_VV 4

Definition at line 1699 of file mincross.c.

◆ flatindex

#define flatindex ( v ) ((size_t)ND_low(v))

Definition at line 114 of file mincross.c.

◆ isBackedge

#define isBackedge ( e ) (ND_idx(aghead(e)) > ND_idx(agtail(e)))

Definition at line 190 of file mincross.c.

◆ MARK

#define MARK ( v ) (ND_mark(v))

Definition at line 112 of file mincross.c.

◆ ND_hi

#define ND_hi ( n ) (((info_t *)AGDATA(n))->hi)

Definition at line 176 of file mincross.c.

◆ ND_idx

#define ND_idx ( n ) (ND_order(ND_np(n)))

Definition at line 178 of file mincross.c.

◆ ND_lo

#define ND_lo ( n ) (((info_t *)AGDATA(n))->lo)

Definition at line 175 of file mincross.c.

◆ ND_np

#define ND_np ( n ) (((info_t *)AGDATA(n))->np)

Definition at line 177 of file mincross.c.

◆ ND_x

#define ND_x ( n ) (((info_t *)AGDATA(n))->x)

Definition at line 174 of file mincross.c.

◆ NTYPES

#define NTYPES 3

Definition at line 1694 of file mincross.c.

◆ ORDINARY

#define ORDINARY 0

Definition at line 1691 of file mincross.c.

◆ saveorder

#define saveorder ( v ) (ND_coord(v)).x

Definition at line 113 of file mincross.c.

◆ SINGLETON

#define SINGLETON 1

Definition at line 1692 of file mincross.c.

◆ VAL

#define VAL	(	node,
		port
	)	(MC_SCALE * ND_order(node) + (port).order)

Definition at line 1606 of file mincross.c.

◆ VIRTUALNODE

#define VIRTUALNODE 2

Definition at line 1693 of file mincross.c.

Function Documentation

◆ allocate_ranks()

void allocate_ranks ( graph_t * g )

Definition at line 1118 of file mincross.c.

References agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), agtail, free(), GD_maxrank, GD_minrank, GD_rank, gv_calloc(), ND_rank, and SWAP.

Referenced by expand_cluster(), and init_mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ betweenclust()

static int betweenclust ( edge_t * e )

static

Definition at line 430 of file mincross.c.

References aghead, agtail, ED_to_orig, and ND_clust.

Referenced by do_ordering_node().

Here is the caller graph for this function:

◆ build_ranks()

int build_ranks	(	Agraph_t *	g,
		int	pass
	)

Returns: 0 on success

Definition at line 1195 of file mincross.c.

References aghead, agroot(), agtail, CLUSTER, dot_root(), enqueue_neighbors(), exchange(), GD_flip, GD_maxrank, GD_minrank, GD_nlist, GD_rank, install_cluster(), install_in_rank(), LIST_FREE, LIST_IS_EMPTY, LIST_POP_FRONT, LIST_PUSH_BACK, MARK, ncross(), ND_in, ND_next, ND_out, ND_prev, ND_ranktype, NULL, Root, and transpose().

Referenced by expand_cluster(), and mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ checkLabelOrder()

void checkLabelOrder ( graph_t * g )

Definition at line 293 of file mincross.c.

References agbindrec(), agclose(), aghead, agnnodes(), agnode(), agopen(), Agstrictdirected, fixLabelOrder(), GD_maxrank, GD_minrank, GD_rank, ITOS, rank_t::n, ND_alg, ND_hi, ND_lo, ND_np, ND_order, ND_out, NULL, SWAP, and rank_t::v.

Referenced by flat_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cleanup2()

static void cleanup2	(	graph_t *	g,
		int64_t	nc,
		bool	have_vlists
	)

static

Parameters

have_vlists Are there vlists that need resetting?

Definition at line 828 of file mincross.c.

References agnameof(), Agedge_s::base, Agobj_s::data, delete_flat_edge(), ED_edge_type, elapsed_sec(), FLATORDER, free(), free_matrix(), GD_clust, GD_maxrank, GD_minrank, GD_n_cluster, GD_rank, ND_flat_out, ND_order, NULL, rec_reset_vlists(), TE_list, TI_list, and Verbose.

Referenced by conjugate_gradient_mkernel(), and dot_mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ constraining_flat_edge()

static bool constraining_flat_edge	(	Agraph_t *	g,
		Agedge_t *	e
	)

static

Definition at line 1293 of file mincross.c.

References aghead, agtail, ED_weight, and inside_cluster().

Referenced by flat_reorder(), and postorder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_ordering()

static void do_ordering	(	graph_t *	g,
		bool	outflag
	)

static

Definition at line 475 of file mincross.c.

References agfstnode(), agnxtnode(), and do_ordering_node().

Referenced by ordered_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_ordering_for_nodes()

static void do_ordering_for_nodes ( graph_t * g )

static

Definition at line 484 of file mincross.c.

References agerrorf(), agfstnode(), agnameof(), agnxtnode(), do_ordering_node(), late_string(), N_ordering, NULL, and streq().

Referenced by ordered_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ do_ordering_node()

static void do_ordering_node	(	graph_t *	g,
		node_t *	n,
		bool	outflag
	)

static

Definition at line 436 of file mincross.c.

References aghead, agtail, betweenclust(), ED_edge_type, edgeidcmpf(), find_flat_edge(), flat_edge(), FLATORDER, ND_clust, ND_in, ND_out, new_virtual_edge(), NULL, and TE_list.

Referenced by do_ordering(), and do_ordering_for_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dot_mincross()

int dot_mincross ( Agraph_t * g )

Returns: 0 on success

Definition at line 328 of file mincross.c.

References agfstnode(), agget(), agwarningf(), cleanup2(), GD_clust, GD_comp, GD_n_cluster, init_mccomp(), init_mincross(), mapbool(), mark_lowclusters(), merge2(), mincross(), mincross_clust(), NULL, and ReMincross.

Referenced by dotLayout(), and make_flat_adj_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ edgeidcmpf()

static int edgeidcmpf	(	const void *	x,
		const void *	y
	)

static

Definition at line 1678 of file mincross.c.

References AGSEQ.

Referenced by do_ordering_node().

Here is the caller graph for this function:

◆ emptyComp()

static void emptyComp ( graph_t * sg )

static

Definition at line 180 of file mincross.c.

References agdelnode(), agfstnode(), and agnxtnode().

Referenced by fixLabelOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ endpoint_class()

static int endpoint_class ( node_t * n )

static

Definition at line 1706 of file mincross.c.

References ND_node_type, ND_weight_class, ORDINARY, SINGLETON, VIRTUAL, and VIRTUALNODE.

Referenced by virtual_weight().

Here is the caller graph for this function:

◆ enqueue_neighbors()

void enqueue_neighbors	(	node_queue_t *	q,
		node_t *	n0,
		int	pass
	)

Definition at line 1271 of file mincross.c.

References aghead, agtail, LIST_PUSH_BACK, MARK, ND_in, and ND_out.

Referenced by build_ranks(), and install_cluster().

Here is the caller graph for this function:

◆ exchange()

static void exchange	(	node_t *	v,
		node_t *	w
	)

static

Definition at line 619 of file mincross.c.

References GD_rank, ND_order, ND_rank, and Root.

Referenced by build_ranks(), reorder(), and transpose_step().

Here is the caller graph for this function:

◆ fillRanks()

static void fillRanks ( Agraph_t * g )

static

Definition at line 999 of file mincross.c.

References bitarray_new(), bitarray_reset(), GD_maxrank, NULL, and realFillRanks().

Referenced by init_mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findSource()

static Agnode_t * findSource	(	Agraph_t *	g,
		Agraph_t *	sg
	)

static

Definition at line 192 of file mincross.c.

References agdegree(), agfstnode(), agnxtnode(), and NULL.

Referenced by LIST().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fixLabelOrder()

static void fixLabelOrder	(	graph_t *	g,
		rank_t *	rk
	)

static

Definition at line 243 of file mincross.c.

References agdegree(), agedge(), agfstnode(), agnnodes_z(), agnxtnode(), agsubg(), emptyComp(), free(), getComp(), gv_calloc(), LIST_FREE, LIST_GET, LIST_SIZE, ND_hi, ND_lo, ND_order, ND_x, NULL, ordercmpf(), and rank_t::v.

Referenced by checkLabelOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ flat_breakcycles()

static void flat_breakcycles ( graph_t * g )

static

Definition at line 1088 of file mincross.c.

References flat_search(), GD_maxrank, GD_minrank, GD_rank, ND_flat_out, ND_low, ND_mark, ND_onstack, and new_matrix().

Referenced by mincross(), and mincross_clust().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ flat_mval()

static bool flat_mval ( node_t * n )

static

Definition at line 1577 of file mincross.c.

References aghead, agtail, ND_flat_in, ND_flat_out, ND_mval, and ND_order.

Referenced by medians().

Here is the caller graph for this function:

◆ flat_reorder()

static void flat_reorder ( graph_t * g )

static

Definition at line 1323 of file mincross.c.

References aghead, agtail, constraining_flat_edge(), delete_flat_edge(), flat_rev(), GD_flip, GD_has_flat_edges, GD_maxrank, GD_minrank, GD_rank, LIST_APPEND, LIST_CLEAR, LIST_FREE, LIST_GET, LIST_IS_EMPTY, LIST_REVERSE, MARK, ND_flat_in, ND_flat_out, ND_order, postorder(), and Root.

Referenced by mincross(), and mincross_clust().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ flat_rev()

static void flat_rev	(	Agraph_t *	g,
		Agedge_t *	e
	)

static

Definition at line 1029 of file mincross.c.

References aghead, agtail, ED_edge_type, ED_label, ED_to_orig, elist_append, flat_edge(), FLATORDER, merge_oneway(), ND_flat_out, ND_other, new_virtual_edge(), NULL, and REVERSED.

Referenced by flat_reorder(), and flat_search().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ flat_search()

static void flat_search	(	graph_t *	g,
		node_t *	v
	)

static

Definition at line 1055 of file mincross.c.

References agcontains(), aghead, agtail, delete_flat_edge(), dot_root(), ED_edge_type, ED_weight, flat_rev(), flat_search(), flatindex, FLATORDER, GD_n_cluster, GD_rank, M, matrix_set(), ND_flat_out, ND_mark, ND_onstack, and ND_rank.

Referenced by flat_breakcycles(), and flat_search().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ free_matrix()

static void free_matrix ( adjmatrix_t * p )

static

Definition at line 411 of file mincross.c.

References adjmatrix_t::data, and free().

Referenced by cleanup2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ furthestnode()

static node_t * furthestnode	(	graph_t *	g,
		node_t *	v,
		int	dir
	)

static

Definition at line 898 of file mincross.c.

References is_a_normal_node_of(), is_a_vnode_of_an_edge_of(), and neighbor.

Referenced by rec_reset_vlists().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getComp()

static int getComp	(	graph_t *	g,
		node_t *	n,
		graph_t *	comp,
		int *	indices
	)

static

Definition at line 220 of file mincross.c.

References agfstin(), agfstout(), aghead, agnnodes(), agnxtin(), agnxtout(), agsubnode(), agtail, getComp(), isBackedge, ND_idx, and ND_x.

Referenced by fixLabelOrder(), and getComp().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ in_cross()

static int64_t in_cross	(	node_t *	v,
		node_t *	w
	)

static

Definition at line 583 of file mincross.c.

References agtail, cnt(), cross(), ED_tail_port, ED_xpenalty, ND_in, and ND_order.

Referenced by transpose_step().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init_mccomp()

static void init_mccomp	(	graph_t *	g,
		size_t	c
	)

static

Definition at line 418 of file mincross.c.

References GD_comp, GD_maxrank, GD_minrank, GD_nlist, and GD_rank.

Referenced by dot_mincross().

Here is the caller graph for this function:

◆ init_mincross()

static void init_mincross ( graph_t * g )

static

Definition at line 1006 of file mincross.c.

References agnedges(), allocate_ranks(), class2(), decompose(), dot_root(), fillRanks(), GD_flags, GD_maxrank, GD_minrank, GlobalMaxRank, GlobalMinRank, gv_calloc(), mincross_options(), NEW_RANK, ordered_edges(), ReMincross, Root, start_timer(), TE_list, TI_list, and Verbose.

Referenced by dot_mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inside_cluster()

static bool inside_cluster	(	graph_t *	g,
		node_t *	v
	)

static

Definition at line 894 of file mincross.c.

References is_a_normal_node_of(), and is_a_vnode_of_an_edge_of().

Referenced by constraining_flat_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ install_in_rank()

int install_in_rank	(	Agraph_t *	g,
		Agnode_t *	n
	)

Returns: 0 on success

Definition at line 1146 of file mincross.c.

References agerrorf(), agnameof(), GD_maxrank, GD_minrank, GD_nlist, GD_rank, ND_next, ND_order, ND_rank, NULL, and Root.

Referenced by build_ranks(), and install_cluster().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_a_normal_node_of()

static bool is_a_normal_node_of	(	graph_t *	g,
		node_t *	v
	)

static

Definition at line 879 of file mincross.c.

References agcontains(), ND_node_type, and NORMAL.

Referenced by furthestnode(), and inside_cluster().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_a_vnode_of_an_edge_of()

static bool is_a_vnode_of_an_edge_of	(	graph_t *	g,
		node_t *	v
	)

static

Definition at line 883 of file mincross.c.

References agcontains(), ED_edge_type, ED_to_orig, ND_in, ND_node_type, ND_out, NORMAL, and VIRTUAL.

Referenced by furthestnode(), and inside_cluster().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ left2right()

static bool left2right	(	graph_t *	g,
		node_t *	v,
		node_t *	w
	)

static

Definition at line 559 of file mincross.c.

References CLUSTER, flatindex, GD_flip, GD_rank, M, matrix_get(), ND_clust, ND_node_type, ND_rank, ND_ranktype, NULL, ReMincross, SWAP, and VIRTUAL.

Referenced by reorder(), and transpose_step().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LIST()

typedef LIST ( node_t * )

Definition at line 201 of file mincross.c.

References agdeledge(), agdelnode(), agfstout(), agnxtout(), findSource(), LIST_APPEND, and ND_np.

Here is the call graph for this function:

◆ local_cross()

static int local_cross	(	elist	l,
		int	dir
	)

static

Definition at line 1476 of file mincross.c.

References aghead, agtail, cross(), ED_head_port, ED_tail_port, ED_xpenalty, elist::list, and ND_order.

Referenced by rcross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_get()

static bool matrix_get	(	adjmatrix_t *	me,
		size_t	row,
		size_t	col
	)

static

get the value of a matrix cell

Parameters

me	Matrix to inspect
row	Row coordinate
col	Column coordinate

Returns: True if the given cell was set

Definition at line 50 of file mincross.c.

References adjmatrix_t::data, adjmatrix_t::ncols, adjmatrix_t::nrows, NULL, and row.

Referenced by left2right(), and matrix_set().

Here is the caller graph for this function:

◆ matrix_set()

static void matrix_set	(	adjmatrix_t *	me,
		size_t	row,
		size_t	col
	)

static

set the value of a matrix cell to true

Parameters

me	Matrix to update
row	Row coordinate
col	Column coordinate

Definition at line 72 of file mincross.c.

References adjmatrix_t::data, free(), gv_alloc(), matrix_get(), adjmatrix_t::ncols, adjmatrix_t::nrows, NULL, row, and zmax().

Referenced by flat_search().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ medians()

static bool medians	(	graph_t *	g,
		int	r0,
		int	r1
	)

static

Definition at line 1608 of file mincross.c.

References aghead, agtail, ED_head_port, ED_tail_port, ED_xpenalty, flat_mval(), GD_rank, ND_in, ND_mval, ND_out, ordercmpf(), rm(), TI_list, and VAL.

Referenced by mincross_step().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ merge2()

static void merge2 ( graph_t * g )

static

Definition at line 803 of file mincross.c.

References agnameof(), GD_maxrank, GD_minrank, GD_rank, merge_components(), ND_order, NULL, and Verbose.

Referenced by dot_mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ merge_components()

static void merge_components ( graph_t * g )

static

Definition at line 780 of file mincross.c.

References GD_comp, GD_maxrank, GD_minrank, GD_nlist, GlobalMaxRank, GlobalMinRank, ND_next, ND_prev, and NULL.

Referenced by merge2().

Here is the caller graph for this function:

◆ mincross()

static int64_t mincross	(	graph_t *	g,
		int	startpass
	)

static

Returns: minimum crossings on success, negative value on failure

Definition at line 688 of file mincross.c.

References build_ranks(), Convergence, dot_root(), flat_breakcycles(), flat_reorder(), MaxIter, MIN, mincross_step(), MinQuit, ncross(), restore_best(), save_best(), transpose(), and Verbose.

Referenced by dot_mincross(), and mincross_clust().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mincross_clust()

static int64_t mincross_clust ( graph_t * g )

static

Returns: minimum crossings on success, negative value on failure

Definition at line 533 of file mincross.c.

References expand_cluster(), flat_breakcycles(), flat_reorder(), GD_clust, GD_n_cluster, mincross(), mincross_clust(), ordered_edges(), and save_vlist().

Referenced by dot_mincross(), and mincross_clust().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mincross_options()

static void mincross_options ( graph_t * g )

static

Definition at line 1744 of file mincross.c.

References agget(), MAX, MaxIter, MinQuit, and scale_clamp().

Referenced by init_mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mincross_step()

static void mincross_step	(	graph_t *	g,
		int	pass
	)

static

Definition at line 1449 of file mincross.c.

References GD_maxrank, GD_minrank, last, medians(), reorder(), Root, and transpose().

Referenced by mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ncross()

static int64_t ncross ( void )

static

Definition at line 1539 of file mincross.c.

References GD_maxrank, GD_minrank, GD_rank, rcross(), and Root.

Referenced by build_ranks(), and mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ neighbor()

static node_t * neighbor	(	node_t *	v,
		int	dir
	)

static

Definition at line 867 of file mincross.c.

References GD_rank, ND_order, ND_rank, NULL, and Root.

◆ new_matrix()

static adjmatrix_t * new_matrix	(	size_t	initial_rows,
		size_t	initial_columns
	)

static

create an adjacency matrix

These matrices dynamically expand on demand. So the initial dimensions provided can be later safely exceeded at runtime.

Parameters

initial_rows	How many rows to allocate now
initial_columns	How many columns to allocate now

Returns: A constructed matrix

Definition at line 401 of file mincross.c.

References gv_alloc(), and adjmatrix_t::nrows.

Referenced by flat_breakcycles().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nodeposcmpf()

static int nodeposcmpf	(	const void *	x,
		const void *	y
	)

static

Definition at line 1666 of file mincross.c.

References ND_order.

Referenced by restore_best().

Here is the caller graph for this function:

◆ ordercmpf()

static int ordercmpf	(	const void *	x,
		const void *	y
	)

static

Definition at line 1556 of file mincross.c.

Referenced by fixLabelOrder(), and medians().

Here is the caller graph for this function:

◆ ordered_edges()

static void ordered_edges ( graph_t * g )

static

Definition at line 508 of file mincross.c.

References agerrorf(), agfstsubg(), agnxtsubg(), do_ordering(), do_ordering_for_nodes(), G_ordering, is_a_cluster(), late_string(), N_ordering, NULL, ordered_edges(), and streq().

Referenced by init_mincross(), mincross_clust(), and ordered_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ out_cross()

static int out_cross	(	node_t *	v,
		node_t *	w
	)

static

Definition at line 602 of file mincross.c.

References aghead, cnt(), cross(), ED_head_port, ED_xpenalty, ND_order, and ND_out.

Referenced by transpose_step().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ postorder()

static void postorder	(	graph_t *	g,
		node_t *	v,
		nodes_t *	list,
		int	r
	)

static

Definition at line 1306 of file mincross.c.

References aghead, constraining_flat_edge(), LIST_APPEND, MARK, ND_flat_out, ND_rank, and postorder().

Referenced by flat_reorder(), and postorder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rcross()

static int64_t rcross	(	graph_t *	g,
		int	r
	)

static

Definition at line 1500 of file mincross.c.

References aghead, cross(), ED_xpenalty, free(), GD_rank, gv_calloc(), local_cross(), ND_has_port, ND_in, ND_order, ND_out, Root, and top().

Referenced by ncross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ realFillRanks()

static Agraph_t * realFillRanks	(	Agraph_t *	g,
		bitarray_t *	ranks,
		Agraph_t *	sg
	)

static

Definition at line 962 of file mincross.c.

References agbindrec(), agfstnode(), agfstout(), aghead, agnode(), agnxtnode(), agnxtout(), agsubg(), agsubnode(), alloc_elist, bitarray_clear(), bitarray_get(), bitarray_set(), dot_root(), GD_clust, GD_maxrank, GD_minrank, GD_n_cluster, ND_ht, ND_in, ND_lw, ND_out, ND_rank, ND_rw, ND_UF_size, NULL, and realFillRanks().

Referenced by fillRanks(), and realFillRanks().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rec_reset_vlists()

void rec_reset_vlists ( graph_t * g )

Definition at line 926 of file mincross.c.

References dot_root(), furthestnode(), GD_clust, GD_maxrank, GD_minrank, GD_n_cluster, GD_rank, GD_rankleader, ND_order, NULL, and rec_reset_vlists().

Referenced by cleanup2(), flat_edges(), and rec_reset_vlists().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rec_save_vlists()

void rec_save_vlists ( graph_t * g )

Definition at line 918 of file mincross.c.

References GD_clust, GD_n_cluster, rec_save_vlists(), and save_vlist().

Referenced by flat_edges(), and rec_save_vlists().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reorder()

static void reorder	(	graph_t *	g,
		int	r,
		bool	reverse,
		bool	hasfixed
	)

static

Definition at line 1398 of file mincross.c.

References exchange(), GD_rank, left2right(), ND_clust, ND_mval, and Root.

Referenced by mincross_step().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ restore_best()

static void restore_best ( graph_t * g )

static

Definition at line 751 of file mincross.c.

References GD_maxrank, GD_minrank, GD_rank, ND_order, nodeposcmpf(), Root, and saveorder.

Referenced by mincross().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ save_best()

static void save_best ( graph_t * g )

static

Definition at line 768 of file mincross.c.

References GD_maxrank, GD_minrank, GD_rank, ND_order, and saveorder.

Referenced by mincross().

Here is the caller graph for this function:

◆ save_vlist()

void save_vlist ( graph_t * g )

Definition at line 909 of file mincross.c.

References GD_maxrank, GD_minrank, GD_rank, and GD_rankleader.

Referenced by mincross_clust(), and rec_save_vlists().

Here is the caller graph for this function:

◆ transpose()

static void transpose	(	graph_t *	g,
		bool	reverse
	)

static

Definition at line 672 of file mincross.c.

References delta, GD_maxrank, GD_minrank, GD_rank, and transpose_step().

Referenced by build_ranks(), mincross(), and mincross_step().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ transpose_step()

static int64_t transpose_step	(	graph_t *	g,
		int	r,
		bool	reverse
	)

static

Definition at line 631 of file mincross.c.

References exchange(), GD_maxrank, GD_minrank, GD_rank, in_cross(), left2right(), ND_order, out_cross(), and Root.

Referenced by transpose().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ virtual_weight()

void virtual_weight ( edge_t * e )

Definition at line 1714 of file mincross.c.

References agerrorf(), aghead, agtail, ED_weight, endpoint_class(), graphviz_exit(), and table.

Referenced by make_chain().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ Convergence

const double Convergence = .995

static

Definition at line 160 of file mincross.c.

Referenced by mincross().

◆ GlobalMaxRank

int GlobalMaxRank

static

Definition at line 163 of file mincross.c.

Referenced by init_mincross(), and merge_components().

◆ GlobalMinRank

int GlobalMinRank

static

Definition at line 163 of file mincross.c.

Referenced by init_mincross(), and merge_components().

◆ MinQuit

int MinQuit

static

Definition at line 159 of file mincross.c.

Referenced by mincross(), and mincross_options().

◆ ReMincross

bool ReMincross

static

Definition at line 166 of file mincross.c.

Referenced by dot_mincross(), init_mincross(), and left2right().

◆ Root

graph_t* Root

static

Definition at line 162 of file mincross.c.

Referenced by build_ranks(), exchange(), flat_reorder(), init_mincross(), install_in_rank(), mincross_step(), ncross(), neighbor(), rcross(), reorder(), restore_best(), and transpose_step().

◆ table

const int table[NTYPES][NTYPES]

static

Initial value:

= {
     {C_EE, C_EE, C_EE},
     {C_EE, C_SS, C_VS},
     {C_EE, C_VS, C_VV}}

Definition at line 1701 of file mincross.c.

Referenced by set_cell_heights(), set_cell_widths(), and virtual_weight().

◆ TE_list

edge_t** TE_list

static

Definition at line 164 of file mincross.c.

Referenced by cleanup2(), do_ordering_node(), and init_mincross().

◆ TI_list

int* TI_list

static

Definition at line 165 of file mincross.c.

Referenced by cleanup2(), init_mincross(), and medians().

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ C_EE

◆ C_SS

◆ C_VS

◆ C_VV

◆ flatindex

◆ isBackedge

◆ MARK

◆ ND_hi

◆ ND_idx

◆ ND_lo

◆ ND_np

◆ ND_x

◆ NTYPES

◆ ORDINARY

◆ saveorder

◆ SINGLETON

◆ VAL

◆ VIRTUALNODE

Function Documentation

◆ allocate_ranks()

◆ betweenclust()

◆ build_ranks()

◆ checkLabelOrder()

◆ cleanup2()

◆ constraining_flat_edge()

◆ do_ordering()

◆ do_ordering_for_nodes()

◆ do_ordering_node()

◆ dot_mincross()

◆ edgeidcmpf()

◆ emptyComp()

◆ endpoint_class()

◆ enqueue_neighbors()

◆ exchange()

◆ fillRanks()

◆ findSource()

◆ fixLabelOrder()

◆ flat_breakcycles()

◆ flat_mval()

◆ flat_reorder()

◆ flat_rev()

◆ flat_search()

◆ free_matrix()

◆ furthestnode()

◆ getComp()

◆ in_cross()

◆ init_mccomp()

◆ init_mincross()

◆ inside_cluster()

◆ install_in_rank()

◆ is_a_normal_node_of()

◆ is_a_vnode_of_an_edge_of()

◆ left2right()

◆ LIST()

◆ local_cross()

◆ matrix_get()

◆ matrix_set()

◆ medians()

◆ merge2()

◆ merge_components()

◆ mincross()

◆ mincross_clust()

◆ mincross_options()

◆ mincross_step()

◆ ncross()

◆ neighbor()

◆ new_matrix()

◆ nodeposcmpf()

◆ ordercmpf()

◆ ordered_edges()

◆ out_cross()

◆ postorder()

◆ rcross()

◆ realFillRanks()

◆ rec_reset_vlists()