Graphviz 13.1.1~dev.20250718.1235
|
#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/exit.h>
#include <util/gv_math.h>
#include <util/itos.h>
#include <util/list.h>
#include <util/streq.h>
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 i, size_t j) |
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, int rnks[], int rnks_sz, 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 int | table [NTYPES][NTYPES] |
#define C_EE 1 |
Definition at line 1786 of file mincross.c.
#define C_SS 2 |
Definition at line 1788 of file mincross.c.
#define C_VS 2 |
Definition at line 1787 of file mincross.c.
#define C_VV 4 |
Definition at line 1789 of file mincross.c.
#define flatindex | ( | v | ) | ((size_t)ND_low(v)) |
Definition at line 86 of file mincross.c.
Definition at line 233 of file mincross.c.
#define MARK | ( | v | ) | (ND_mark(v)) |
Definition at line 84 of file mincross.c.
Definition at line 217 of file mincross.c.
Definition at line 219 of file mincross.c.
Definition at line 216 of file mincross.c.
Definition at line 218 of file mincross.c.
Definition at line 215 of file mincross.c.
#define NTYPES 3 |
Definition at line 1784 of file mincross.c.
#define ORDINARY 0 |
Definition at line 1781 of file mincross.c.
#define saveorder | ( | v | ) | (ND_coord(v)).x |
Definition at line 85 of file mincross.c.
#define SINGLETON 1 |
Definition at line 1782 of file mincross.c.
Definition at line 1676 of file mincross.c.
#define VIRTUALNODE 2 |
Definition at line 1783 of file mincross.c.
void allocate_ranks | ( | graph_t * | g | ) |
Definition at line 1191 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().
|
static |
Definition at line 473 of file mincross.c.
References aghead, agtail, ED_to_orig, and ND_clust.
Referenced by do_ordering_node().
int build_ranks | ( | Agraph_t * | g, |
int | pass | ||
) |
Definition at line 1267 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(), MARK, ncross(), ND_in, ND_next, ND_out, ND_prev, ND_ranktype, NULL, Root, and transpose().
Referenced by expand_cluster(), and mincross().
void checkLabelOrder | ( | graph_t * | g | ) |
Definition at line 342 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().
|
static |
Definition at line 884 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().
Definition at line 1365 of file mincross.c.
References aghead, agtail, ED_weight, and inside_cluster().
Referenced by flat_reorder(), and postorder().
|
static |
Definition at line 520 of file mincross.c.
References agfstnode(), agnxtnode(), and do_ordering_node().
Referenced by ordered_edges().
|
static |
Definition at line 529 of file mincross.c.
References agerrorf(), agfstnode(), agnameof(), agnxtnode(), do_ordering_node(), late_string(), N_ordering, NULL, and streq().
Referenced by ordered_edges().
Definition at line 480 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().
int dot_mincross | ( | Agraph_t * | g | ) |
Definition at line 381 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().
|
static |
Definition at line 1758 of file mincross.c.
References AGSEQ.
Referenced by do_ordering_node().
|
static |
Definition at line 222 of file mincross.c.
References agdelnode(), agfstnode(), and agnxtnode().
Referenced by fixLabelOrder().
|
static |
Definition at line 1797 of file mincross.c.
References ND_node_type, ND_weight_class, ORDINARY, SINGLETON, VIRTUAL, and VIRTUALNODE.
Referenced by virtual_weight().
void enqueue_neighbors | ( | node_queue_t * | q, |
node_t * | n0, | ||
int | pass | ||
) |
Definition at line 1343 of file mincross.c.
References aghead, agtail, MARK, ND_in, and ND_out.
Referenced by build_ranks(), and install_cluster().
|
static |
Definition at line 1065 of file mincross.c.
References free(), GD_maxrank, gv_calloc(), NULL, and realFillRanks().
Referenced by init_mincross().
Definition at line 236 of file mincross.c.
References agdegree(), agfstnode(), agnxtnode(), and NULL.
Referenced by topsort().
Definition at line 288 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().
|
static |
Definition at line 1160 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().
|
static |
Definition at line 1646 of file mincross.c.
References aghead, agtail, ND_flat_in, ND_flat_out, ND_mval, and ND_order.
Referenced by medians().
|
static |
Definition at line 1396 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, MARK, ND_flat_in, ND_flat_out, ND_order, postorder(), and Root.
Referenced by mincross(), and mincross_clust().
Definition at line 1097 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().
Definition at line 1124 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().
|
static |
Definition at line 453 of file mincross.c.
References adjmatrix_t::data, and free().
Referenced by cleanup2().
Definition at line 956 of file mincross.c.
References is_a_normal_node_of(), is_a_vnode_of_an_edge_of(), and neighbor.
Referenced by rec_reset_vlists().
Definition at line 265 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().
Definition at line 630 of file mincross.c.
References agtail, cnt(), cross(), ED_tail_port, ED_xpenalty, ND_in, and ND_order.
Referenced by transpose_step().
|
static |
Definition at line 461 of file mincross.c.
References GD_comp, GD_maxrank, GD_minrank, GD_nlist, and GD_rank.
Referenced by dot_mincross().
|
static |
Definition at line 1073 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().
Definition at line 952 of file mincross.c.
References is_a_normal_node_of(), and is_a_vnode_of_an_edge_of().
Referenced by constraining_flat_edge().
Definition at line 1219 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().
Definition at line 936 of file mincross.c.
References agcontains(), ND_node_type, and NORMAL.
Referenced by furthestnode(), and inside_cluster().
Definition at line 940 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().
Definition at line 606 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().
|
static |
Definition at line 1547 of file mincross.c.
References aghead, agtail, cross(), ED_head_port, ED_tail_port, ED_xpenalty, elist::list, and ND_order.
Referenced by rcross().
|
static |
get the value of a matrix cell
me | Matrix to inspect |
row | Row coordinate |
col | Column coordinate |
Definition at line 48 of file mincross.c.
References adjmatrix_t::allocated, adjmatrix_t::data, adjmatrix_t::ncols, NULL, and row.
Referenced by left2right().
|
static |
set the value of a matrix cell to true
me | Matrix to update |
row | Row coordinate |
col | Column coordinate |
Definition at line 67 of file mincross.c.
References adjmatrix_t::allocated, adjmatrix_t::data, gv_recalloc(), adjmatrix_t::ncols, NULL, and row.
Referenced by flat_search().
|
static |
Definition at line 1678 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().
|
static |
Definition at line 857 of file mincross.c.
References agnameof(), GD_maxrank, GD_minrank, GD_rank, merge_components(), ND_order, NULL, and Verbose.
Referenced by dot_mincross().
|
static |
Definition at line 833 of file mincross.c.
References GD_comp, GD_maxrank, GD_minrank, GD_nlist, GlobalMaxRank, GlobalMinRank, ND_next, ND_prev, and NULL.
Referenced by merge2().
|
static |
Definition at line 739 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().
|
static |
Definition at line 580 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().
|
static |
Definition at line 1864 of file mincross.c.
References agget(), MAX, MaxIter, MinQuit, and scale_clamp().
Referenced by init_mincross().
|
static |
Definition at line 1519 of file mincross.c.
References GD_maxrank, GD_minrank, last, medians(), reorder(), Root, and transpose().
Referenced by mincross().
|
static |
Definition at line 1608 of file mincross.c.
References GD_maxrank, GD_minrank, GD_rank, rcross(), and Root.
Referenced by build_ranks(), and mincross().
|
static |
Definition at line 446 of file mincross.c.
References gv_alloc(), adjmatrix_t::ncols, and adjmatrix_t::nrows.
Referenced by flat_breakcycles().
|
static |
Definition at line 1736 of file mincross.c.
References ND_order.
Referenced by restore_best().
|
static |
Definition at line 1625 of file mincross.c.
Referenced by fixLabelOrder(), and medians().
|
static |
Definition at line 553 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().
Definition at line 649 of file mincross.c.
References aghead, cnt(), cross(), ED_head_port, ED_xpenalty, ND_order, and ND_out.
Referenced by transpose_step().
Definition at line 1380 of file mincross.c.
References aghead, constraining_flat_edge(), MARK, ND_flat_out, ND_rank, and postorder().
Referenced by flat_reorder(), and postorder().
|
static |
Definition at line 1569 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().
Definition at line 1026 of file mincross.c.
References agbindrec(), agfstnode(), agfstout(), aghead, agnode(), agnxtnode(), agnxtout(), agsubg(), agsubnode(), alloc_elist, 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().
void rec_reset_vlists | ( | graph_t * | g | ) |
Definition at line 988 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().
void rec_save_vlists | ( | graph_t * | g | ) |
Definition at line 978 of file mincross.c.
References GD_clust, GD_n_cluster, rec_save_vlists(), and save_vlist().
Referenced by flat_edges(), and rec_save_vlists().
|
static |
Definition at line 1467 of file mincross.c.
References exchange, GD_rank, left2right(), ND_clust, ND_mval, and Root.
Referenced by mincross_step().
|
static |
Definition at line 802 of file mincross.c.
References GD_maxrank, GD_minrank, GD_rank, ND_order, nodeposcmpf(), Root, and saveorder.
Referenced by mincross().
|
static |
Definition at line 820 of file mincross.c.
References GD_maxrank, GD_minrank, GD_rank, ND_order, and saveorder.
Referenced by mincross().
void save_vlist | ( | graph_t * | g | ) |
Definition at line 968 of file mincross.c.
References GD_maxrank, GD_minrank, GD_rank, and GD_rankleader.
Referenced by mincross_clust(), and rec_save_vlists().
Definition at line 246 of file mincross.c.
References agdeledge(), agdelnode(), agfstout(), agnxtout(), cnt(), findSource(), and ND_np.
Referenced by fixLabelOrder().
|
static |
Definition at line 722 of file mincross.c.
References delta, GD_maxrank, GD_minrank, GD_rank, and transpose_step().
Referenced by build_ranks(), mincross(), and mincross_step().
|
static |
Definition at line 681 of file mincross.c.
References exchange, GD_maxrank, GD_minrank, GD_rank, in_cross(), left2right(), ND_order, out_cross(), and Root.
Referenced by transpose().
void virtual_weight | ( | edge_t * | e | ) |
Definition at line 1806 of file mincross.c.
References agerrorf(), aghead, agtail, ED_weight, endpoint_class(), graphviz_exit(), and table.
Referenced by make_chain().
|
static |
Definition at line 121 of file mincross.c.
Referenced by mincross().
|
static |
Definition at line 124 of file mincross.c.
Referenced by init_mincross(), and merge_components().
|
static |
Definition at line 124 of file mincross.c.
Referenced by init_mincross(), and merge_components().
|
static |
Definition at line 120 of file mincross.c.
Referenced by mincross(), and mincross_options().
|
static |
Definition at line 127 of file mincross.c.
Referenced by dot_mincross(), init_mincross(), and left2right().
|
static |
Definition at line 123 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().
Definition at line 1791 of file mincross.c.
Referenced by set_cell_heights(), set_cell_widths(), and virtual_weight().
|
static |
Definition at line 125 of file mincross.c.
Referenced by cleanup2(), do_ordering_node(), and init_mincross().
|
static |
Definition at line 126 of file mincross.c.
Referenced by cleanup2(), init_mincross(), and medians().