Graphviz 13.1.0~dev.20250626.0830
|
#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, ints_t *scratch) |
static int64_t | mincross (graph_t *g, int startpass, ints_t *scratch) |
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 (ints_t *scratch) |
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, ints_t *scratch) |
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, ints_t *Count) |
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 1799 of file mincross.c.
#define C_SS 2 |
Definition at line 1801 of file mincross.c.
#define C_VS 2 |
Definition at line 1800 of file mincross.c.
#define C_VV 4 |
Definition at line 1802 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 1797 of file mincross.c.
#define ORDINARY 0 |
Definition at line 1794 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 1795 of file mincross.c.
Definition at line 1689 of file mincross.c.
#define VIRTUALNODE 2 |
Definition at line 1796 of file mincross.c.
void allocate_ranks | ( | graph_t * | g | ) |
Definition at line 1197 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 479 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, | ||
ints_t * | scratch | ||
) |
Definition at line 1273 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 890 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 1371 of file mincross.c.
References aghead, agtail, ED_weight, and inside_cluster().
Referenced by flat_reorder(), and postorder().
|
static |
Definition at line 526 of file mincross.c.
References agfstnode(), agnxtnode(), and do_ordering_node().
Referenced by ordered_edges().
|
static |
Definition at line 535 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 486 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 1771 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 1810 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 1349 of file mincross.c.
References aghead, agtail, MARK, ND_in, and ND_out.
Referenced by build_ranks(), and install_cluster().
|
static |
Definition at line 1071 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 1166 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 1659 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 1402 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 1103 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 1130 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 459 of file mincross.c.
References adjmatrix_t::data, and free().
Referenced by cleanup2().
Definition at line 962 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 636 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 467 of file mincross.c.
References GD_comp, GD_maxrank, GD_minrank, GD_nlist, and GD_rank.
Referenced by dot_mincross().
|
static |
Definition at line 1079 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 958 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 1225 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 942 of file mincross.c.
References agcontains(), ND_node_type, and NORMAL.
Referenced by furthestnode(), and inside_cluster().
Definition at line 946 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 612 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 1553 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 1691 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 863 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 839 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 745 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 586 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 1877 of file mincross.c.
References agget(), MAX, MaxIter, MinQuit, and scale_clamp().
Referenced by init_mincross().
|
static |
Definition at line 1525 of file mincross.c.
References GD_maxrank, GD_minrank, last, medians(), reorder(), Root, and transpose().
Referenced by mincross().
|
static |
Definition at line 1620 of file mincross.c.
References GD_maxrank, GD_minrank, GD_rank, NULL, rcross(), and Root.
Referenced by build_ranks(), and mincross().
|
static |
Definition at line 452 of file mincross.c.
References gv_alloc(), adjmatrix_t::ncols, and adjmatrix_t::nrows.
Referenced by flat_breakcycles().
|
static |
Definition at line 1749 of file mincross.c.
References ND_order.
Referenced by restore_best().
|
static |
Definition at line 1638 of file mincross.c.
Referenced by fixLabelOrder(), and medians().
|
static |
Definition at line 559 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 655 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 1386 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 1575 of file mincross.c.
References aghead, cross(), ED_xpenalty, GD_rank, local_cross(), ND_has_port, ND_in, ND_order, ND_out, and top().
Referenced by ncross().
Definition at line 1032 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 994 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 984 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 1473 of file mincross.c.
References exchange, GD_rank, left2right(), ND_clust, ND_mval, and Root.
Referenced by mincross_step().
|
static |
Definition at line 808 of file mincross.c.
References GD_maxrank, GD_minrank, GD_rank, ND_order, nodeposcmpf(), Root, and saveorder.
Referenced by mincross().
|
static |
Definition at line 826 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 974 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 728 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 687 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 1819 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(), reorder(), restore_best(), and transpose_step().
Definition at line 1804 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().