Graphviz 13.1.3~dev.20250829.0113
|
#include <dotgen/dot.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdint.h>
#include <util/alloc.h>
#include <util/list.h>
#include <util/gv_math.h>
Go to the source code of this file.
Macros | |
#define | BACKWARD_PENALTY 1000 |
#define | STRONG_CLUSTER_WEIGHT 1000 |
#define | NORANK 6 |
#define | ROOT "\177root" |
#define | TOPNODE "\177top" |
#define | BOTNODE "\177bot" |
#define | ND_comp(n) ND_hops(n) |
Functions | |
static void | dot1_rank (graph_t *g) |
static void | dot2_rank (graph_t *g) |
typedef | LIST (edge_t *) |
static int | edge_ptr_cmp (const void *x, const void *y) |
static void | cleanup1 (graph_t *g) |
static void | edgelabel_ranks (graph_t *g) |
static void | collapse_rankset (graph_t *g, graph_t *subg, int kind) |
static int | rank_set_class (graph_t *g) |
static int | make_new_cluster (graph_t *g, graph_t *subg) |
static void | node_induce (graph_t *par, graph_t *g) |
void | dot_scan_ranks (graph_t *g) |
static void | cluster_leader (graph_t *clust) |
static void | collapse_cluster (graph_t *g, graph_t *subg) |
static void | collapse_sets (graph_t *rg, graph_t *g) |
static void | find_clusters (graph_t *g) |
static void | set_minmax (graph_t *g) |
static point | minmax_edges (graph_t *g) |
static int | minmax_edges2 (graph_t *g, point slen) |
void | rank1 (graph_t *g) |
static void | expand_ranksets (graph_t *g) |
void | dot_rank (graph_t *g) |
bool | is_cluster (graph_t *g) |
static void | set_parent (graph_t *g, graph_t *p) |
static bool | is_empty (graph_t *g) |
static bool | is_a_strong_cluster (graph_t *g) |
static int | rankset_kind (graph_t *g) |
static bool | is_nonconstraint (edge_t *e) |
static node_t * | find (node_t *n) |
static node_t * | union_one (node_t *leader, node_t *n) |
static node_t * | union_all (graph_t *g) |
static void | compile_samerank (graph_t *ug, graph_t *parent_clust) |
static graph_t * | dot_lca (graph_t *c0, graph_t *c1) |
static bool | is_internal_to_cluster (edge_t *e) |
static node_t * | makeXnode (graph_t *G, char *name) |
static void | compile_nodes (graph_t *g, graph_t *Xg) |
static void | merge (edge_t *e, int minlen, int weight) |
static void | strong (graph_t *g, node_t *t, node_t *h, edge_t *orig) |
static void | weak (graph_t *g, node_t *t, node_t *h, edge_t *orig) |
static void | compile_edges (graph_t *ug, graph_t *Xg) |
static void | compile_clusters (graph_t *g, graph_t *Xg, node_t *top, node_t *bot) |
static void | reverse_edge2 (graph_t *g, edge_t *e) |
static void | dfs (graph_t *g, node_t *v) |
static void | break_cycles (graph_t *g) |
static void | setMinMax (graph_t *g, int doRoot) |
static void | readout_levels (graph_t *g, graph_t *Xg, int ncc) |
static void | dfscc (graph_t *g, node_t *n, int cc) |
static int | connect_components (graph_t *g) |
static void | add_fast_edges (graph_t *g) |
static void | my_init_graph (Agraph_t *g, Agobj_t *graph, void *arg) |
static void | my_init_node (Agraph_t *g, Agobj_t *node, void *arg) |
static void | my_init_edge (Agraph_t *g, Agobj_t *edge, void *arg) |
Variables | |
static node_t * | Last_node |
static Agcbdisc_t | mydisc = { {my_init_graph,0,0}, {my_init_node,0,0}, {my_init_edge,0,0} } |
int | infosizes [] |
|
static |
Definition at line 1047 of file rank.c.
References agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), elist_append, ND_in, and ND_out.
Referenced by dot2_rank().
|
static |
Definition at line 907 of file rank.c.
References agfstnode(), agnxtnode(), dfs(), ND_mark, and ND_onstack.
Referenced by dot2_rank().
|
static |
Definition at line 78 of file rank.c.
References agfstnode(), agfstout(), agnxtnode(), agnxtout(), Agedge_s::base, Agobj_s::data, ED_to_orig, ED_to_virt, edge_ptr_cmp(), free(), free_list, GD_comp, GD_nlist, LIST_APPEND, LIST_FREE, LIST_GET, LIST_SIZE, LIST_SORT, ND_in, ND_mark, ND_next, ND_node_type, ND_out, ND_prev, NULL, prev, and SLACKNODE.
Referenced by conjugate_gradient_f(), and dot1_rank().
|
static |
Definition at line 294 of file rank.c.
References agfstnode(), agnxtnode(), CLUSTER, GD_leader, GD_nlist, ND_next, ND_node_type, ND_rank, ND_ranktype, ND_UF_size, NORMAL, NULL, and UF_union().
Referenced by collapse_cluster().
Definition at line 325 of file rank.c.
References agfstnode(), CL_type, cluster_leader(), dot1_rank(), dot_scan_ranks(), GD_parent, LOCAL, make_new_cluster(), node_induce(), and NULL.
Referenced by collapse_sets(), and find_clusters().
Definition at line 177 of file rank.c.
References agfstnode(), agnxtnode(), GD_maxset, GD_minset, MAXRANK, MINRANK, ND_ranktype, NULL, SINKRANK, SOURCERANK, and UF_union().
Referenced by collapse_sets().
Definition at line 344 of file rank.c.
References agfstsubg(), agnxtsubg(), CL_type, CLUSTER, collapse_cluster(), collapse_rankset(), collapse_sets(), LOCAL, and rank_set_class().
Referenced by collapse_sets(), and dot1_rank().
Definition at line 845 of file rank.c.
References agedge(), agfstin(), agfstnode(), agfstout(), agfstsubg(), agnxtnode(), agnxtsubg(), BOTNODE, compile_clusters(), find(), is_a_cluster(), is_a_strong_cluster(), makeXnode(), merge(), ND_rep, STRONG_CLUSTER_WEIGHT, sub, top(), and TOPNODE.
Referenced by compile_clusters(), and dot2_rank().
Definition at line 806 of file rank.c.
References agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), agtail, find(), GD_maxrep, GD_minrep, is_a_strong_cluster(), is_internal_to_cluster(), is_nonconstraint(), ND_clust, ND_rep, NULL, strong(), SWAP, and weak().
Referenced by dot2_rank().
Definition at line 747 of file rank.c.
References agfstnode(), agnameof(), agnxtnode(), find(), Last_node, makeXnode(), ND_rep, and NULL.
Referenced by dot2_rank().
Definition at line 632 of file rank.c.
References agfstnode(), agfstsubg(), agget(), agnameof(), agnxtnode(), agnxtsubg(), agwarningf(), compile_samerank(), GD_level, GD_maxrep, GD_minrep, is_a_cluster(), is_empty(), MAXRANK, MINRANK, ND_clust, NORANK, NULL, rankset_kind(), SAMERANK, set_parent(), SINKRANK, SOURCERANK, union_all(), and union_one().
Referenced by compile_samerank(), and dot2_rank().
|
static |
Definition at line 1024 of file rank.c.
References agedge(), agfstnode(), agnxtnode(), dfscc(), makeXnode(), ND_comp, and ROOT.
Referenced by dot2_rank().
Definition at line 885 of file rank.c.
References agfstout(), aghead, agnxtout(), dfs(), ND_mark, ND_onstack, and reverse_edge2().
Referenced by break_cycles(), and dfs().
Definition at line 1012 of file rank.c.
References agfstin(), agfstout(), aghead, agnxtin(), agnxtout(), agtail, dfscc(), and ND_comp.
Referenced by connect_components(), and dfscc().
|
static |
Definition at line 500 of file rank.c.
References acyclic(), class1(), cleanup1(), collapse_sets(), decompose(), edgelabel_ranks(), expand_ranksets(), minmax_edges(), minmax_edges2(), and rank1().
Referenced by collapse_cluster(), and dot_rank().
|
static |
Definition at line 1073 of file rank.c.
References add_fast_edges(), agbindrec(), agclose(), agget(), agnedges(), agnnodes(), agopen(), agpushdisc(), Agstrictdirected, break_cycles(), compile_clusters(), compile_edges(), compile_nodes(), compile_samerank(), connect_components(), edgelabel_ranks(), infosizes, Last_node, mydisc, NULL, rank2(), readout_levels(), and scale_clamp().
Referenced by dot_rank().
Definition at line 704 of file rank.c.
References GD_level, and GD_parent.
Referenced by is_internal_to_cluster().
void dot_rank | ( | graph_t * | g | ) |
Definition at line 519 of file rank.c.
References agget(), dot1_rank(), dot2_rank(), GD_flags, GD_maxrank, GD_minrank, mapbool(), NEW_RANK, and Verbose.
Referenced by dotLayout(), and make_flat_adj_edges().
void dot_scan_ranks | ( | graph_t * | g | ) |
Definition at line 273 of file rank.c.
References agfstnode(), agnxtnode(), GD_leader, GD_maxrank, GD_minrank, ND_rank, and NULL.
Referenced by collapse_cluster(), and rebuild_vlists().
|
static |
compare two edge pointers
This function assumes the two edge pointers may have differing provenance, and thus cannot be directly compared. It also assumes the caller is primarily comparing in order to put equal elements next to each other in a sorting operation. Relying on, e.g. an earlier allocated edge pointer to compare as less than a later allocated edge pointer is not a good idea.
a | One edge |
b | Another edge |
Definition at line 63 of file rank.c.
Referenced by cleanup1().
|
static |
Definition at line 162 of file rank.c.
References agfstnode(), agfstout(), agnxtnode(), agnxtout(), ED_minlen, EDGE_LABEL, GD_has_labels, and GD_ranksep.
Referenced by dot1_rank(), and dot2_rank().
|
static |
Definition at line 463 of file rank.c.
References agfstnode(), agnxtnode(), CL_type, dot_root(), find_clusters(), GD_clust, GD_maxrank, GD_minrank, GD_n_cluster, LEAFSET, LOCAL, ND_rank, ND_ranktype, set_minmax(), UF_find(), and UF_singleton().
Referenced by dot1_rank().
Definition at line 600 of file rank.c.
References find(), and ND_set.
Referenced by compile_clusters(), compile_edges(), compile_nodes(), find(), readout_levels(), union_all(), and union_one().
|
static |
Definition at line 363 of file rank.c.
References agfstsubg(), agnxtsubg(), CLUSTER, collapse_cluster(), dot_root(), and GD_set_type.
Referenced by expand_ranksets().
|
static |
Definition at line 564 of file rank.c.
References agget(), mapbool(), and str.
Referenced by compile_clusters(), and compile_edges().
bool is_cluster | ( | graph_t * | g | ) |
Definition at line 530 of file rank.c.
References is_a_cluster().
Referenced by ordered_edges(), and rank_set_class().
|
static |
Definition at line 560 of file rank.c.
References agfstnode().
Referenced by compile_samerank().
|
static |
|
static |
typedef LIST | ( | edge_t * | ) |
Definition at line 231 of file rank.c.
References do_graph_label(), GD_clust, GD_n_cluster, and gv_recalloc().
Referenced by collapse_cluster(), and set_parent().
Definition at line 729 of file rank.c.
References agnode(), alloc_elist, G, GD_nlist, Last_node, ND_in, ND_next, ND_out, ND_prev, and NULL.
Referenced by compile_clusters(), compile_nodes(), connect_components(), and weak().
|
static |
Definition at line 763 of file rank.c.
References ED_minlen, ED_weight, and MAX.
Referenced by beginpath(), compile_clusters(), endpath(), reverse_edge2(), and strong().
Definition at line 387 of file rank.c.
References aghead, agtail, GD_maxset, GD_minset, ND_in, ND_out, ND_ranktype, NULL, reverse_edge(), SINKRANK, SOURCERANK, UF_find(), point::x, and point::y.
Referenced by dot1_rank().
Definition at line 419 of file rank.c.
References agfstnode(), agnxtnode(), ED_minlen, ED_weight, GD_maxset, GD_minset, ND_in, ND_out, NULL, UF_find(), virtual_edge(), point::x, and point::y.
Referenced by dot1_rank().
Definition at line 1063 of file rank.c.
References agbindrec(), and edge.
Definition at line 1059 of file rank.c.
References agbindrec(), and graph().
Definition at line 1061 of file rank.c.
References agbindrec().
Definition at line 243 of file rank.c.
References agcontains(), agdelete(), agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), agsubedge(), dot_root(), GD_clust, GD_n_cluster, ND_clust, ND_ranktype, and NULL.
Referenced by collapse_cluster(), and set_parent().
void rank1 | ( | graph_t * | g | ) |
Definition at line 444 of file rank.c.
References agget(), agnnodes(), GD_comp, GD_n_cluster, GD_nlist, rank(), and scale_clamp().
Referenced by dot1_rank().
|
static |
Definition at line 216 of file rank.c.
References agget(), CLUSTER, GD_set_type, is_cluster(), maptoken(), MAXRANK, MINRANK, NULL, SAMERANK, SINKRANK, and SOURCERANK.
Referenced by collapse_sets().
|
static |
Definition at line 956 of file rank.c.
References agfstnode(), agnxtnode(), delta, find(), free(), free_list, GD_maxrank, GD_minrank, gv_calloc(), MIN, ND_alg, ND_comp, ND_in, ND_out, ND_rank, ND_rep, NULL, and setMinMax().
Referenced by dot2_rank().
|
static |
Definition at line 373 of file rank.c.
References GD_clust, GD_leader, GD_maxrank, GD_minrank, GD_n_cluster, ND_rank, and set_minmax().
Referenced by expand_ranksets(), and set_minmax().
Definition at line 553 of file rank.c.
References GD_parent, make_new_cluster(), and node_induce().
Referenced by compile_samerank().
|
static |
Definition at line 923 of file rank.c.
References agfstnode(), agnxtnode(), GD_clust, GD_leader, GD_maxrank, GD_minrank, GD_n_cluster, GD_parent, ND_rank, NULL, and setMinMax().
Referenced by readout_levels(), and setMinMax().
Definition at line 769 of file rank.c.
References agedge(), agerrorf(), agfindedge, agnameof(), ED_minlen, ED_weight, and merge().
Referenced by compile_edges().
Definition at line 619 of file rank.c.
References agfstnode(), agnxtnode(), find(), and union_one().
Referenced by compile_samerank().
Definition at line 611 of file rank.c.
References find(), and ND_set.
Referenced by compile_samerank(), and union_all().
Definition at line 780 of file rank.c.
References agedge(), agfstin(), agfstout(), aghead, agnxtin(), agtail, BACKWARD_PENALTY, ED_minlen, ED_weight, id, makeXnode(), and MAX.
Referenced by compile_edges().
int infosizes[] |
Definition at line 1067 of file rank.c.
Referenced by dot2_rank().
|
static |
Definition at line 728 of file rank.c.
Referenced by compile_nodes(), dot2_rank(), and makeXnode().
|
static |
Definition at line 1065 of file rank.c.
Referenced by dot2_rank(), and myiddisc_open().