Graphviz 13.0.0~dev.20250607.1528
|
#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 | ELT(M, i, j) (M->data[((i)*M->ncols)+(j)]) |
#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 | 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) |
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 1776 of file mincross.c.
#define C_SS 2 |
Definition at line 1778 of file mincross.c.
#define C_VS 2 |
Definition at line 1777 of file mincross.c.
#define C_VV 4 |
Definition at line 1779 of file mincross.c.
#define flatindex | ( | v | ) | ((size_t)ND_low(v)) |
Definition at line 44 of file mincross.c.
Definition at line 197 of file mincross.c.
#define MARK | ( | v | ) | (ND_mark(v)) |
Definition at line 42 of file mincross.c.
Definition at line 181 of file mincross.c.
Definition at line 183 of file mincross.c.
Definition at line 180 of file mincross.c.
Definition at line 182 of file mincross.c.
Definition at line 179 of file mincross.c.
#define NTYPES 3 |
Definition at line 1774 of file mincross.c.
#define ORDINARY 0 |
Definition at line 1771 of file mincross.c.
#define saveorder | ( | v | ) | (ND_coord(v)).x |
Definition at line 43 of file mincross.c.
#define SINGLETON 1 |
Definition at line 1772 of file mincross.c.
Definition at line 1666 of file mincross.c.
#define VIRTUALNODE 2 |
Definition at line 1773 of file mincross.c.
void allocate_ranks | ( | graph_t * | g | ) |
Definition at line 1173 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 450 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 1249 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 309 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 864 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 1347 of file mincross.c.
References aghead, agtail, ED_weight, and inside_cluster().
Referenced by flat_reorder(), and postorder().
|
static |
Definition at line 497 of file mincross.c.
References agfstnode(), agnxtnode(), and do_ordering_node().
Referenced by ordered_edges().
|
static |
Definition at line 506 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 457 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 349 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 1748 of file mincross.c.
References AGSEQ.
Referenced by do_ordering_node().
|
static |
Definition at line 186 of file mincross.c.
References agdelnode(), agfstnode(), and agnxtnode().
Referenced by fixLabelOrder().
|
static |
Definition at line 1787 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 1325 of file mincross.c.
References aghead, agtail, MARK, ND_in, and ND_out.
Referenced by build_ranks(), and install_cluster().
|
static |
Definition at line 1046 of file mincross.c.
References free(), GD_maxrank, gv_calloc(), NULL, and realFillRanks().
Referenced by init_mincross().
Definition at line 200 of file mincross.c.
References agdegree(), agfstnode(), agnxtnode(), and NULL.
Referenced by topsort().
Definition at line 254 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 1141 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 1636 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 1378 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 1078 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 1105 of file mincross.c.
References agcontains(), aghead, agtail, delete_flat_edge(), dot_root(), ED_edge_type, ED_weight, ELT, flat_rev(), flat_search(), flatindex, FLATORDER, GD_n_cluster, GD_rank, M, ND_flat_out, ND_mark, ND_onstack, and ND_rank.
Referenced by flat_breakcycles(), and flat_search().
|
static |
Definition at line 428 of file mincross.c.
References adjmatrix_t::data, and free().
Referenced by cleanup2().
Definition at line 936 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 229 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 610 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 438 of file mincross.c.
References GD_comp, GD_maxrank, GD_minrank, GD_nlist, and GD_rank.
Referenced by dot_mincross().
|
static |
Definition at line 1054 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 932 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 1201 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 916 of file mincross.c.
References agcontains(), ND_node_type, and NORMAL.
Referenced by furthestnode(), and inside_cluster().
Definition at line 920 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 584 of file mincross.c.
References CLUSTER, ELT, flatindex, GD_flip, GD_rank, M, ND_clust, ND_node_type, ND_rank, ND_ranktype, NULL, ReMincross, SWAP, and VIRTUAL.
Referenced by reorder(), and transpose_step().
|
static |
Definition at line 1529 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 |
Definition at line 1668 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 837 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 813 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 719 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 558 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 1854 of file mincross.c.
References agget(), MAX, MaxIter, MinQuit, and scale_clamp().
Referenced by init_mincross().
|
static |
Definition at line 1501 of file mincross.c.
References GD_maxrank, GD_minrank, last, medians(), reorder(), Root, and transpose().
Referenced by mincross().
|
static |
Definition at line 1596 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 420 of file mincross.c.
References adjmatrix_t::data, gv_alloc(), gv_calloc(), adjmatrix_t::ncols, and adjmatrix_t::nrows.
Referenced by flat_breakcycles().
|
static |
Definition at line 1726 of file mincross.c.
References ND_order.
Referenced by restore_best().
|
static |
Definition at line 1614 of file mincross.c.
Referenced by fixLabelOrder(), and medians().
|
static |
Definition at line 531 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 629 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 1362 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 1551 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 1007 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 968 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 958 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 1449 of file mincross.c.
References exchange, GD_rank, left2right(), ND_clust, ND_mval, and Root.
Referenced by mincross_step().
|
static |
Definition at line 782 of file mincross.c.
References GD_maxrank, GD_minrank, GD_rank, ND_order, nodeposcmpf(), Root, and saveorder.
Referenced by mincross().
|
static |
Definition at line 800 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 948 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 210 of file mincross.c.
References agdeledge(), agdelnode(), agfstout(), agnxtout(), cnt(), findSource(), and ND_np.
Referenced by fixLabelOrder().
|
static |
Definition at line 702 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 661 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 1796 of file mincross.c.
References agerrorf(), aghead, agtail, ED_weight, endpoint_class(), graphviz_exit(), and table.
Referenced by make_chain().
|
static |
Definition at line 85 of file mincross.c.
Referenced by mincross().
|
static |
Definition at line 88 of file mincross.c.
Referenced by init_mincross(), and merge_components().
|
static |
Definition at line 88 of file mincross.c.
Referenced by init_mincross(), and merge_components().
|
static |
Definition at line 84 of file mincross.c.
Referenced by mincross(), and mincross_options().
|
static |
Definition at line 91 of file mincross.c.
Referenced by dot_mincross(), init_mincross(), and left2right().
|
static |
Definition at line 87 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 1781 of file mincross.c.
Referenced by set_cell_heights(), set_cell_widths(), and virtual_weight().
|
static |
Definition at line 89 of file mincross.c.
Referenced by cleanup2(), do_ordering_node(), and init_mincross().
|
static |
Definition at line 90 of file mincross.c.
Referenced by cleanup2(), init_mincross(), and medians().