Graphviz: lib/dotgen/mincross.c File Reference

Searching...

No Matches

#include <assert.h>
#include <cgraph/cgraph.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)

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)

static int	topsort (Agraph_t g, Agraph_t sg, Agnode_t **arr)

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)

typedef	LIST (node_t *)

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 int	table [NTYPES][NTYPES]

Macro Definition Documentation

◆ C_EE

#define C_EE 1

Definition at line 1818 of file mincross.c.

◆ C_SS

#define C_SS 2

Definition at line 1820 of file mincross.c.

◆ C_VS

#define C_VS 2

Definition at line 1819 of file mincross.c.

◆ C_VV

#define C_VV 4

Definition at line 1821 of file mincross.c.

◆ flatindex

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

Definition at line 112 of file mincross.c.

◆ isBackedge

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

Definition at line 269 of file mincross.c.

◆ MARK

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

Definition at line 110 of file mincross.c.

◆ ND_hi

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

Definition at line 253 of file mincross.c.

◆ ND_idx

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

Definition at line 255 of file mincross.c.

◆ ND_lo

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

Definition at line 252 of file mincross.c.

◆ ND_np

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

Definition at line 254 of file mincross.c.

◆ ND_x

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

Definition at line 251 of file mincross.c.

◆ NTYPES

#define NTYPES 3

Definition at line 1816 of file mincross.c.

◆ ORDINARY

#define ORDINARY 0

Definition at line 1813 of file mincross.c.

◆ saveorder

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

Definition at line 111 of file mincross.c.

◆ SINGLETON

#define SINGLETON 1

Definition at line 1814 of file mincross.c.

◆ VAL

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

Definition at line 1708 of file mincross.c.

◆ VIRTUALNODE

#define VIRTUALNODE 2

Definition at line 1815 of file mincross.c.

Function Documentation

◆ allocate_ranks()

void allocate_ranks ( graph_t * g )

Definition at line 1223 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 511 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 1299 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 378 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
	)

static

Definition at line 922 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 1397 of file mincross.c.

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

Referenced by flat_reorder(), and LIST().

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 558 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 567 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 518 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 417 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 1790 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 258 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 1829 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 1375 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 706 of file mincross.c.

References GD_rank, ND_order, ND_rank, and Root.

◆ fillRanks()

static void fillRanks ( Agraph_t * g )

static

Definition at line 1101 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 272 of file mincross.c.

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

Referenced by topsort().

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 324 of file mincross.c.

References agdegree(), agedge(), agfstnode(), agnnodes(), agnxtnode(), agsubg(), cnt(), emptyComp(), free(), getComp(), gv_calloc(), ND_hi, ND_lo, ND_order, ND_x, NULL, ordercmpf(), topsort(), 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 1192 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 1678 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 1428 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, 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 1133 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 1160 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 491 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 994 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 301 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 668 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 499 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 1109 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 990 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 1251 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 974 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 978 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 644 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 1407 of file mincross.c.

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

Here is the call graph for this function:

◆ local_cross()

static int local_cross	(	elist	l,
		int	dir
	)

static

Definition at line 1579 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 48 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 70 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 1710 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 895 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 871 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 777 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 618 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 1896 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 1551 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 1640 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 961 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 482 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 1768 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 1657 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 591 of file mincross.c.

References agerrorf(), agfstsubg(), agnxtsubg(), do_ordering(), do_ordering_for_nodes(), G_ordering, is_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 687 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:

◆ rcross()

static int64_t rcross	(	graph_t *	g,
		int	r
	)

static

Definition at line 1601 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 1063 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 1026 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 1016 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 1499 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 840 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 858 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 1006 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:

◆ topsort()

static int topsort	(	Agraph_t *	g,
		Agraph_t *	sg,
		Agnode_t **	arr
	)

static

Definition at line 282 of file mincross.c.

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

Referenced by fixLabelOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ transpose()

static void transpose	(	graph_t *	g,
		bool	reverse
	)

static

Definition at line 760 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 719 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 1838 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 157 of file mincross.c.

Referenced by mincross().

◆ GlobalMaxRank

int GlobalMaxRank

static

Definition at line 160 of file mincross.c.

Referenced by init_mincross(), and merge_components().

◆ GlobalMinRank

int GlobalMinRank

static

Definition at line 160 of file mincross.c.

Referenced by init_mincross(), and merge_components().

◆ MinQuit

int MinQuit

static

Definition at line 156 of file mincross.c.

Referenced by mincross(), and mincross_options().

◆ ReMincross

bool ReMincross

static

Definition at line 163 of file mincross.c.

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

◆ Root

graph_t* Root

static

Definition at line 159 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

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 1823 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 161 of file mincross.c.

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

◆ TI_list

int* TI_list

static

Definition at line 162 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()

◆ rcross()

◆ realFillRanks()

◆ rec_reset_vlists()

◆ rec_save_vlists()