Graphviz 16.1.3~dev.20261121.1645
Loading...
Searching...
No Matches
rank.c File Reference
#include "config.h"
#include <common/utils.h>
#include <dotgen/dot.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <util/list.h>
#include <util/streq.h>
Include dependency graph for rank.c:

Go to the source code of this file.

Macros

#define ROOT   "\177root"
 
#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, char kind)
 
static char rankset_kind (graph_t *g)
 
static char 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)
 
static void set_parent (graph_t *g, graph_t *p)
 
static bool is_empty (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 compile_edges (graph_t *ug, graph_t *Xg)
 
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
 
int infosizes []
 

Macro Definition Documentation

◆ ND_comp

#define ND_comp (   n)    ND_hops(n)

Definition at line 515 of file rank.c.

◆ ROOT

#define ROOT   "\177root"

Definition at line 510 of file rank.c.

Function Documentation

◆ add_fast_edges()

static void add_fast_edges ( graph_t *  g)
static

Definition at line 915 of file rank.c.

References agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), elist_append, ND_in, and ND_out.

Referenced by dot2_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ break_cycles()

static void break_cycles ( graph_t *  g)
static

Definition at line 781 of file rank.c.

References agfstnode(), agnxtnode(), dfs(), ND_mark, and ND_onstack.

Referenced by dot2_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ cleanup1()

static void cleanup1 ( graph_t *  g)
static

Definition at line 80 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_d(), and dot1_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ cluster_leader()

static void cluster_leader ( graph_t *  clust)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ collapse_cluster()

static void collapse_cluster ( graph_t *  g,
graph_t *  subg 
)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ collapse_rankset()

static void collapse_rankset ( graph_t *  g,
graph_t *  subg,
char  kind 
)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ collapse_sets()

static void collapse_sets ( graph_t *  rg,
graph_t *  g 
)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ compile_edges()

static void compile_edges ( graph_t *  ug,
graph_t *  Xg 
)
static

Definition at line 721 of file rank.c.

References agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), agtail, find(), GD_maxrep, GD_minrep, is_internal_to_cluster(), is_nonconstraint(), ND_clust, ND_rep, NULL, strong(), and SWAP.

Referenced by dot2_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ compile_nodes()

static void compile_nodes ( graph_t *  g,
graph_t *  Xg 
)
static

Definition at line 690 of file rank.c.

References agfstnode(), agnameof(), agnxtnode(), find(), Last_node, makeXnode(), ND_rep, and NULL.

Referenced by dot2_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ compile_samerank()

static void compile_samerank ( graph_t *  ug,
graph_t *  parent_clust 
)
static

Definition at line 582 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, NOCMD, NULL, rankset_kind(), SAMERANK, set_parent(), SINKRANK, SOURCERANK, union_all(), and union_one().

Referenced by compile_samerank(), and dot2_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ connect_components()

static int connect_components ( graph_t *  g)
static

Definition at line 893 of file rank.c.

References agedge(), agfstnode(), agnxtnode(), dfscc(), makeXnode(), ND_comp, and ROOT.

Referenced by dot2_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfs()

static void dfs ( graph_t *  g,
node_t *  v 
)
static

Definition at line 760 of file rank.c.

References agfstout(), aghead, agnxtout(), dfs(), ND_mark, ND_onstack, and reverse_edge2().

Referenced by break_cycles(), and dfs().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfscc()

static void dfscc ( graph_t *  g,
node_t *  n,
int  cc 
)
static

Definition at line 882 of file rank.c.

References agfstin(), agfstout(), aghead, agnxtin(), agnxtout(), agtail, dfscc(), and ND_comp.

Referenced by connect_components(), and dfscc().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dot1_rank()

static void dot1_rank ( graph_t *  g)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dot2_rank()

void dot2_rank ( graph_t *  g)
static

Definition at line 947 of file rank.c.

References add_fast_edges(), agbindrec(), agclose(), agget(), agnedges(), agnnodes(), agopen(), agpushdisc(), Agstrictdirected, break_cycles(), 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().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dot_lca()

static graph_t * dot_lca ( graph_t *  c0,
graph_t *  c1 
)
static

Definition at line 650 of file rank.c.

References GD_level, and GD_parent.

Referenced by is_internal_to_cluster().

Here is the caller graph for this function:

◆ dot_rank()

void dot_rank ( graph_t *  g)

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dot_scan_ranks()

void dot_scan_ranks ( graph_t *  g)

Definition at line 266 of file rank.c.

References agfstnode(), agnxtnode(), GD_leader, GD_maxrank, GD_minrank, ND_rank, and NULL.

Referenced by collapse_cluster(), and rebuild_vlists().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ edge_ptr_cmp()

static int edge_ptr_cmp ( const void *  x,
const void *  y 
)
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.

Parameters
aOne edge
bAnother edge
Returns
A comparator value suitable for sorting algorithms

Definition at line 66 of file rank.c.

Referenced by cleanup1().

Here is the caller graph for this function:

◆ edgelabel_ranks()

static void edgelabel_ranks ( graph_t *  g)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ expand_ranksets()

static void expand_ranksets ( graph_t *  g)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ find()

static node_t * find ( node_t *  n)
static

Definition at line 553 of file rank.c.

References find(), and ND_set.

Referenced by compile_edges(), compile_nodes(), find(), readout_levels(), union_all(), and union_one().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ find_clusters()

static void find_clusters ( graph_t *  g)
static

Definition at line 346 of file rank.c.

References agfstsubg(), agnxtsubg(), CLUSTER, collapse_cluster(), dot_root(), and GD_set_type.

Referenced by expand_ranksets().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ is_empty()

static bool is_empty ( graph_t *  g)
static

Definition at line 523 of file rank.c.

References agfstnode().

Referenced by compile_samerank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ is_internal_to_cluster()

static bool is_internal_to_cluster ( edge_t *  e)
static

Definition at line 660 of file rank.c.

References aghead, agtail, dot_lca(), and ND_clust.

Referenced by compile_edges().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ is_nonconstraint()

static bool is_nonconstraint ( edge_t *  e)
static

Definition at line 543 of file rank.c.

References agxget(), constr, E_constr, and mapbool().

Referenced by compile_edges().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ LIST()

typedef LIST ( edge_t *  )

Definition at line 41 of file rank.c.

References L, LIST_APPEND, NULL, and SIZE_MAX.

◆ make_new_cluster()

static int make_new_cluster ( graph_t *  g,
graph_t *  subg 
)
static

Definition at line 228 of file rank.c.

References do_graph_label(), GD_clust, GD_n_cluster, and gv_recalloc().

Referenced by collapse_cluster(), and set_parent().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ makeXnode()

static node_t * makeXnode ( graph_t *  G,
char *  name 
)
static

Definition at line 673 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_nodes(), and connect_components().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ merge()

static void merge ( edge_t *  e,
int  minlen,
int  weight 
)
static

Definition at line 705 of file rank.c.

References ED_minlen, ED_weight, and MAX.

Referenced by beginpath(), endpath(), reverse_edge2(), and strong().

Here is the caller graph for this function:

◆ minmax_edges()

static point minmax_edges ( graph_t *  g)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minmax_edges2()

static int minmax_edges2 ( graph_t *  g,
point  slen 
)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ my_init_edge()

static void my_init_edge ( Agraph_t *  g,
Agobj_t *  edge,
void *  arg 
)
static

Definition at line 936 of file rank.c.

References agbindrec(), and edge.

Here is the call graph for this function:

◆ my_init_graph()

static void my_init_graph ( Agraph_t *  g,
Agobj_t *  graph,
void *  arg 
)
static

Definition at line 926 of file rank.c.

References agbindrec(), and graph().

Here is the call graph for this function:

◆ my_init_node()

static void my_init_node ( Agraph_t *  g,
Agobj_t *  node,
void *  arg 
)
static

Definition at line 931 of file rank.c.

References agbindrec().

Here is the call graph for this function:

◆ node_induce()

static void node_induce ( graph_t *  par,
graph_t *  g 
)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ rank1()

void rank1 ( graph_t *  g)

Definition at line 420 of file rank.c.

References agget(), agnnodes(), GD_comp, GD_n_cluster, GD_nlist, rank(), and scale_clamp().

Referenced by dot1_rank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ rank_set_class()

static char rank_set_class ( graph_t *  g)
static

Definition at line 219 of file rank.c.

References CLUSTER, GD_set_type, is_a_cluster(), and rankset_kind().

Referenced by collapse_sets().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ rankset_kind()

static char rankset_kind ( graph_t *  g)
static

Definition at line 525 of file rank.c.

References agget(), MAXRANK, MINRANK, NOCMD, SAMERANK, SINKRANK, SOURCERANK, str, and streq().

Referenced by compile_samerank(), and rank_set_class().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ readout_levels()

static void readout_levels ( graph_t *  g,
graph_t *  Xg,
int  ncc 
)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ reverse_edge2()

static void reverse_edge2 ( graph_t *  g,
edge_t *  e 
)
static

Definition at line 750 of file rank.c.

References agdelete(), agedge(), agfindedge, aghead, agtail, ED_minlen, ED_weight, and merge().

Referenced by dfs().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ set_minmax()

static void set_minmax ( graph_t *  g)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ set_parent()

static void set_parent ( graph_t *  g,
graph_t *  p 
)
static

Definition at line 517 of file rank.c.

References GD_parent, make_new_cluster(), and node_induce().

Referenced by compile_samerank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ setMinMax()

static void setMinMax ( graph_t *  g,
int  doRoot 
)
static

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ strong()

static void strong ( graph_t *  g,
node_t *  t,
node_t *  h,
edge_t *  orig 
)
static

Definition at line 710 of file rank.c.

References agedge(), agerrorf(), agfindedge, agnameof(), ED_minlen, ED_weight, and merge().

Referenced by compile_edges().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ union_all()

static node_t * union_all ( graph_t *  g)
static

Definition at line 570 of file rank.c.

References agfstnode(), agnxtnode(), find(), and union_one().

Referenced by compile_samerank().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ union_one()

static node_t * union_one ( node_t *  leader,
node_t *  n 
)
static

Definition at line 563 of file rank.c.

References find(), and ND_set.

Referenced by compile_samerank(), and union_all().

Here is the call graph for this function:
Here is the caller graph for this function:

Variable Documentation

◆ infosizes

int infosizes[]
Initial value:

Definition at line 944 of file rank.c.

Referenced by dot2_rank().

◆ Last_node

node_t* Last_node
static

Definition at line 672 of file rank.c.

Referenced by compile_nodes(), dot2_rank(), and makeXnode().

◆ mydisc

Agcbdisc_t mydisc
static
Initial value:
= {
{my_init_graph, 0, 0}, {my_init_node, 0, 0}, {my_init_edge, 0, 0}}
static void my_init_graph(Agraph_t *g, Agobj_t *graph, void *arg)
Definition rank.c:926
static void my_init_node(Agraph_t *g, Agobj_t *node, void *arg)
Definition rank.c:931
static void my_init_edge(Agraph_t *g, Agobj_t *edge, void *arg)
Definition rank.c:936

Definition at line 941 of file rank.c.

Referenced by dot2_rank(), and myiddisc_open().