From caf65438ea717abb0fed3463ec21a0a25680f784 Mon Sep 17 00:00:00 2001 From: "Emden R. Gansner" Date: Sun, 2 Oct 2016 17:49:01 -0400 Subject: [PATCH] Add library for computing Simmelian backbones of graphs. --- configure.ac | 1 + lib/Makefile.am | 2 +- lib/spine/Makefile.am | 19 ++ lib/spine/quad.c | 124 +++++++++++++ lib/spine/quad.h | 10 + lib/spine/spine.c | 407 +++++++++++++++++++++++++++++++++++++++++ lib/spine/spine.h | 8 + lib/spine/spinehdr.h | 38 ++++ lib/spine/subset.c | 95 ++++++++++ lib/spine/subset.h | 18 ++ lib/spine/union_find.c | 63 +++++++ lib/spine/union_find.h | 12 ++ 12 files changed, 796 insertions(+), 1 deletion(-) create mode 100644 lib/spine/Makefile.am create mode 100644 lib/spine/quad.c create mode 100644 lib/spine/quad.h create mode 100644 lib/spine/spine.c create mode 100644 lib/spine/spine.h create mode 100644 lib/spine/spinehdr.h create mode 100644 lib/spine/subset.c create mode 100644 lib/spine/subset.h create mode 100644 lib/spine/union_find.c create mode 100644 lib/spine/union_find.h diff --git a/configure.ac b/configure.ac index 53a8bd11a..fc3a246bb 100644 --- a/configure.ac +++ b/configure.ac @@ -3145,6 +3145,7 @@ AC_CONFIG_FILES(Makefile lib/ast/Makefile lib/sfio/Makefile lib/sfio/Sfio_f/Makefile + lib/spine/Makefile lib/vmalloc/Makefile lib/dotgen/Makefile lib/neatogen/Makefile diff --git a/lib/Makefile.am b/lib/Makefile.am index e80bc38b6..e6d97445d 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -4,6 +4,6 @@ SUBDIRS = cdt cgraph pathplan sfio vmalloc ast \ vpsc rbtree ortho sparse patchwork expr common \ pack xdot label gvc ingraphs topfish glcomp mingle edgepaint \ - circogen dotgen fdpgen neatogen twopigen sfdpgen osage gvpr + circogen dotgen fdpgen neatogen twopigen sfdpgen osage gvpr spine EXTRA_DIST = gvc.vcxproj* gvc.def diff --git a/lib/spine/Makefile.am b/lib/spine/Makefile.am new file mode 100644 index 000000000..13cc866bd --- /dev/null +++ b/lib/spine/Makefile.am @@ -0,0 +1,19 @@ +# $Id$ $Revision$ +## Process this file with automake to produce Makefile.in + +#pdfdir = $(pkgdatadir)/doc/pdf +#pkgconfigdir = $(libdir)/pkgconfig + +AM_CPPFLAGS = -I$(top_srcdir) \ + -I$(top_srcdir)/lib/cgraph \ + -I$(top_srcdir)/lib/cdt + +noinst_HEADERS = quad.h spine.h subset.h union_find.h +noinst_LTLIBRARIES = libspine_C.la + +libspine_C_la_SOURCES = quad.c spine.c subset.c union_find.c + +EXTRA_DIST = $(man_MANS) $(pdf_DATA) + +DISTCLEANFILES = $(pdf_DATA) + diff --git a/lib/spine/quad.c b/lib/spine/quad.c new file mode 100644 index 000000000..07970eb74 --- /dev/null +++ b/lib/spine/quad.c @@ -0,0 +1,124 @@ +/* vim:set shiftwidth=4 ts=4: */ + +#include +#include +#include +#include +#include + +static int cmpdeg(const void *v0, const void *v1) +{ + Agnode_t *n0 = *(Agnode_t **) v0; + Agnode_t *n1 = *(Agnode_t **) v1; + + if (ND_deg(n0) > ND_deg(n1)) + return -1; + else if (ND_deg(n0) < ND_deg(n1)) + return 1; + else + return 0; +} + +void genQuads(Agraph_t * g, quadfn_t action, void *state) +{ + int nnodes = agnnodes(g); + Agnode_t **arr = N_NEW(nnodes, Agnode_t *); + Agraph_t *cloneg = agsubg(g, "clone", 1); + Dt_t **subs = N_NEW(nnodes, Dt_t *); + Agnode_t *n; + Agnode_t *v; + Agnode_t *u; + Agnode_t *w; + Agedge_t *e; + Agedge_t *f; + + /* make clone graph */ + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + agsubnode(cloneg, n, 1); + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + agsubedge(cloneg, e, 1); + } + } + + /* sort the vertices by non-increasing degrees */ + int j, i = 0; + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + arr[i++] = n; + ND_deg(n) = agdegree(cloneg, n, 1, 1); + } + qsort(arr, nnodes, sizeof(Agnode_t *), cmpdeg); + + /* create index and set for each node */ + for (i = 0; i < nnodes; i++) { + if (i < nnodes - 1) + assert(ND_deg(arr[i]) >= ND_deg(arr[i + 1])); + ND_id(arr[i]) = i; + subs[i] = mkSubset(); + } + + for (i = 0; i < nnodes; i++) { + v = arr[i]; + /* for each adjacent node u of v */ + for (e = agfstedge(cloneg, v); e; e = agnxtedge(cloneg, e, v)) { + if (agtail(e) == aghead(e)) + continue; + if (agtail(e) == v) + u = aghead(e); + else + u = agtail(e); + /* for each adjacent node w != v of u */ + for (f = agfstedge(cloneg, u); f; f = agnxtedge(cloneg, f, u)) { + if (agtail(f) == aghead(f)) + continue; + if (agtail(f) == u) + w = aghead(f); + else + w = agtail(f); + addSubset(subs[ND_id(w)], u); + } + } + for (j = i + 1; j < nnodes; j++) { + if (sizeSubset(subs[j]) >= 2) + /* generate quadrilaterals */ + action(v, arr[j], subs[j], state); + } + for (j = i + 1; j < nnodes; j++) { + if (sizeSubset(subs[j]) >= 1) + clearSubset(subs[j]); + } + agdelnode(cloneg, v); + closeSubset(subs[i]); + } + + agclose(cloneg); + free(arr); + free(subs); +} + +#ifdef TEST +static int walker(Agnode_t * n, int *isFirst) +{ + if (*isFirst) { + *isFirst = 0; + printf("%s", agnameof(n)); + } else + printf(",%s", agnameof(n)); + return 0; +} + +static void +findQuads(Agnode_t * v, Agnode_t * w, Dt_t * subset, void *state) +{ + int first = 1; + printf("%s %s {", agnameof(v), agnameof(w)); + walkSubset(subset, (walkfn) walker, &first); + printf("}\n"); +} + +int main() +{ + Agraph_t *g = agread(stdin, 0); + genQuads(g, findQuads, 0); + return 0; +} +#endif diff --git a/lib/spine/quad.h b/lib/spine/quad.h new file mode 100644 index 000000000..c40c27049 --- /dev/null +++ b/lib/spine/quad.h @@ -0,0 +1,10 @@ +#ifndef QUAD_H +#define QUAD_H + +#include + +typedef void (*quadfn_t)(Agnode_t*, Agnode_t*, Dt_t*, void*); + +extern void genQuads (Agraph_t*, quadfn_t action, void*); + +#endif diff --git a/lib/spine/spine.c b/lib/spine/spine.c new file mode 100644 index 000000000..5fd0214a6 --- /dev/null +++ b/lib/spine/spine.c @@ -0,0 +1,407 @@ +/* vim:set shiftwidth=4 ts=4: */ + +#include +#include +#include +#include "union_find.h" +#include "assert.h" +#include +#include +#include +#ifdef MAIN +#include +#include "ingraphs.h" + +typedef struct { + FILE *outfp; + char **Files; + float sparse_ratio; + int verbose; +} opts_t; +#endif + +#if 0 +static float ewt(Agedge_t * e) +{ + return ED_wt(e); +} +#endif + +static void doEdge(Agraph_t * g, Agnode_t * v, Agnode_t * w, int *quadcnt) +{ + Agedge_t *e = agedge(g, v, w, 0, 0); + if (!e) + e = agedge(g, w, v, 0, 0); + if (!e) { + fprintf(stderr, "Could not find edge %s--%s\n", agnameof(v), + agnameof(w)); + exit(1); + } + quadcnt[ED_id(e)] += 1; +} + +static void +recordQuads(Agnode_t * v, Agnode_t * w, Dt_t * subset, void *state) +{ + Dtlink_t *link0; + Dtlink_t *link1; + Agnode_t *u0; + Agnode_t *u1; + int *quadcnt = (int *) state; + Agraph_t *g = agroot(v); + + for (link0 = dtflatten(subset); link0; link0 = dtlink(subset, link0)) { + u0 = (Agnode_t *) (((ptritem *) dtobj(subset, link0))->v); + for (link1 = dtlink(subset, link0); link1; + link1 = dtlink(subset, link1)) { + u1 = (Agnode_t *) (((ptritem *) dtobj(subset, link1))->v); + doEdge(g, v, u0, quadcnt); + doEdge(g, w, u0, quadcnt); + doEdge(g, v, u1, quadcnt); + doEdge(g, w, u1, quadcnt); + } + } +} + +static void setEdgeWeights(Agraph_t * g) +{ + int *quadcnt = N_NEW(agnedges(g), int); + int *que = N_NEW(agnnodes(g), int); + Agnode_t *n; + /* Agnode_t *v; */ + Agedge_t *e; + int wt; + + genQuads(g, recordQuads, quadcnt); + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + wt = 0; + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + if (aghead(e) == n) + continue; + wt += quadcnt[ED_id(e)]; + } + for (e = agfstin(g, n); e; e = agnxtin(g, e)) { + if (agtail(e) == n) + continue; + wt += quadcnt[ED_id(e)]; + } + que[ND_id(n)] = wt; +#if 0 + fprintf(stderr, " %s quad %d\n", agnameof(n), que[ND_id(n)]); +#endif + } + + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + int quadv = quadcnt[ED_id(e)]; + if (quadv) + ED_wt(e) = + quadv / + sqrt((double) (que[ND_id(n)] * que[ND_id(aghead(e))])); + else + ED_wt(e) = 0; +#if 0 + fprintf(stderr, " %s--%s quadcnt %d wt %f\n", + agnameof(n), agnameof(aghead(e)), quadcnt[ED_id(e)], + ED_wt(e)); +#endif + } + } + + free(quadcnt); + free(que); +} + +/* Return number in range [0,nedges] */ +static int computeIndex(int nedges, float s) +{ + int r = ceilf(nedges * (1 - s)); + return r; +} + +static int doBucket(Agedge_t ** edgelist, int idx, Dt_t * M) +{ + Agedge_t *e; + float weight = ED_wt(edgelist[idx]); + + while ((e = edgelist[idx]) && (ED_wt(e) == weight)) { + idx++; + if (UF_find(agtail(e)) != UF_find(aghead(e))) + addSubset(M, e); + } + + return idx; +} + +static int walker(Agedge_t * e, Agraph_t * sg) +{ + UF_union(agtail(e), aghead(e)); + agsubedge(sg, e, 1); + return 0; +} + +static Agraph_t *findUMST(Agraph_t * g, Agedge_t ** edgelist, int nedges) +{ + Agraph_t *sg = agsubg(g, "UMST", 1); + Dt_t *M = mkSubset(); + + int i = 0; + while (i < nedges) { + i = doBucket(edgelist, i, M); + /* for each edge in M, add to sg, and union nodes */ + walkSubset(M, (walkfn) walker, sg); + if (i < nedges) + clearSubset(M); + } + closeSubset(M); + return sg; +} + +static int cmpe(const void *v0, const void *v1) +{ + Agedge_t *e0 = *(Agedge_t **) v0; + Agedge_t *e1 = *(Agedge_t **) v1; + + if (ED_wt(e0) > ED_wt(e1)) + return -1; + else if (ED_wt(e0) < ED_wt(e1)) + return 1; + else + return 0; +} + + +void genSpine(Agraph_t * g, float sparse_ratio, int verbose) +{ + Agraph_t *sg_union; + Agnode_t *n; + Agedge_t *e; + Agedge_t **edgelist; + int i, index; + int nedges = agnedges(g); + float threshhold; + + if (verbose) + fprintf(stderr, "Graph %s %d nodes %d edges:\n", agnameof(g), + agnnodes(g), agnedges(g)); + aginit(g, AGNODE, "nodeinfo", sizeof(nodeinfo_t), 1); + aginit(g, AGEDGE, "edgeinfo", sizeof(edgeinfo_t), 1); + + int eidx = 0; + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + ED_id(e) = eidx++; + } + } + if (verbose) + fprintf(stderr, "setEdgeWeights\n"); + setEdgeWeights(g); + + /* sort edges by non-increasing weight */ + if (verbose) + fprintf(stderr, "sorting\n"); + edgelist = N_NEW(nedges + 1, Agedge_t *); /* NULL at end */ + i = 0; + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { + edgelist[i++] = e; + } + } + qsort(edgelist, nedges, sizeof(Agedge_t *), cmpe); +#if 0 + float curwt = -1; + int cnt = 0; + for (i = 0; i <= nedges; i++) { + e = edgelist[i]; + if (e && (ED_wt(e) == curwt)) + cnt++; + else { + if (cnt) + fprintf(stderr, "%f %d\n", curwt, cnt); + if (e) { + cnt = 1; + curwt = ED_wt(e); + } + } + } +#endif + if (verbose) + fprintf(stderr, "heaviest wt %f least wt %f\n", ED_wt(edgelist[0]), + ED_wt(edgelist[nedges - 1])); + + /* compute UMST */ + sg_union = findUMST(g, edgelist, nedges); + int umst_size = agnedges(sg_union); + if (verbose) + fprintf(stderr, " union of maximum spanning trees: %d edges\n", + umst_size); + + /* Find index of the |E|(1-sparse_ratio)th edge */ + index = computeIndex(nedges, sparse_ratio); + if (verbose) + fprintf(stderr, " index %d out of %d\n", index, nedges); + + /* set of edges with weights above threshhold */ + /* Add all edges with wt >= wt(edgelist[index]) */ + /* As edgelist is sorted, first index edges */ + int extra_edges = 0; + for (i = 1; i <= index; i++) { + e = edgelist[i - 1]; + if (verbose) { + if (agsubedge(sg_union, e, 0) == NULL) + extra_edges++; + } + agsubedge(sg_union, e, 1); + } + + /* Add any additional edges with same weight as e */ + if (index) { + threshhold = ED_wt(e); + for (; i <= nedges; i++) { + e = edgelist[i - 1]; + if (ED_wt(e) >= threshhold) { + if (verbose) { + if (agsubedge(sg_union, e, 0) == NULL) + extra_edges++; + } + agsubedge(sg_union, e, 1); + } else + break; + } + } + if (verbose) + fprintf(stderr, + "number of extra edges not in UMST %d total edges %d\n", + extra_edges, agnedges(sg_union)); + + /* layout graph sg_union */ + Agsym_t *sym = agattr(g, AGEDGE, "weight", "0"); + int ncnt = 0; + int ecnt = 0; + for (n = agfstnode(sg_union); n; n = agnxtnode(sg_union, n)) { + ncnt++; + for (e = agfstout(sg_union, n); e; e = agnxtout(sg_union, e)) { + ecnt++; + agxset(e, sym, "1"); + } + } + fprintf(stderr, "ncnt %d ecnt %d\n", ncnt, ecnt); +} + +#ifdef MAIN + +static FILE *openFile(char *cmd, char *name, char *mode) +{ + FILE *fp; + char *modestr; + + fp = fopen(name, mode); + if (!fp) { + if (*mode == 'r') + modestr = "reading"; + else + modestr = "writing"; + fprintf(stderr, "%s: could not open file %s for %s\n", + cmd, name, modestr); + exit(1); + } + return fp; +} + +static int setFloat(char *s, float *v) +{ + char *endp; + float f = strtof(s, &endp); + if (s == endp) { + fprintf(stderr, "Option value \"%s\" must be a float\n", s); + return 1; + } + if ((f < 0) || (f > 1)) { + fprintf(stderr, "Option value \"%s\" must be in the range [0,1]\n", + s); + return 1; + } + *v = f; + return 0; + +} + +static char *Usage = "Usage: %s [-?] [options]\n\ + -r : sparsification ratio [0,1] (0.5) \n\ + -o : put output in (stdout)\n\ + -v : verbose mode \n\ + -? : print usage\n"; + +static void usage(char *cmd, int v) +{ + fprintf(v ? stderr : stdout, Usage, cmd); + exit(v); +} + +static void doOpts(int argc, char *argv[], opts_t * op) +{ + int c; + char *cmd = argv[0]; + + op->outfp = NULL; + op->Files = NULL; + op->verbose = 0; + op->sparse_ratio = 0.5; + + opterr = 0; + while ((c = getopt(argc, argv, "o:r:v")) != -1) { + switch (c) { + case 'o': + op->outfp = openFile(cmd, optarg, "w"); + break; + case 'v': + op->verbose = 1; + break; + case 'r': + if (setFloat(optarg, &(op->sparse_ratio))) { + fprintf(stderr, "%s: bad value for flag -%c - ignored\n", + cmd, c); + } + break; + case '?': + if (optopt == '?') + usage(cmd, 0); + else + fprintf(stderr, "%s: option -%c unrecognized - ignored\n", + cmd, optopt); + break; + } + } + argv += optind; + argc -= optind; + + if (argc) + op->Files = argv; + if (op->outfp == NULL) + op->outfp = stdout; + if (op->verbose) + fprintf(stderr, "sparse ratio = %f\n", op->sparse_ratio); +} + +static Agraph_t *gread(FILE * fp) +{ + return agread(fp, (Agdisc_t *) 0); +} + +int main(int argc, char *argv[]) +{ + opts_t opts; + ingraph_state ig; + Agraph_t *g; + + doOpts(argc, argv, &opts); + newIngraph(&ig, opts.Files, gread); + while ((g = nextGraph(&ig)) != 0) { + genSpine(g, ops.sparse_ratio, ops.verbose); + agwrite(g, ops.outfp); + agclose(g); + } + + return 0; +} +#endif diff --git a/lib/spine/spine.h b/lib/spine/spine.h new file mode 100644 index 000000000..d98fa0bf2 --- /dev/null +++ b/lib/spine/spine.h @@ -0,0 +1,8 @@ +#ifndef SPINE_T +#define SPINE_T + +#include + +void genSpine (Agraph_t * g, float sparse_ratio, int verbose); + +#endif diff --git a/lib/spine/spinehdr.h b/lib/spine/spinehdr.h new file mode 100644 index 000000000..a31232004 --- /dev/null +++ b/lib/spine/spinehdr.h @@ -0,0 +1,38 @@ +#ifndef SPINEHDR_T +#define SPINEHDR_T + +/* +#include +#include +#include +#include +*/ +#include + +#define N_NEW(n,t) (t*)calloc((n),sizeof(t)) +#define NEW(t) (t*)calloc((1),sizeof(t)) + +#define NOTUSED(var) (void) var + +typedef struct { + Agrec_t h; + int id; + int deg; + int UF_size; + Agnode_t *UF_parent; +} nodeinfo_t; + +typedef struct { + Agrec_t h; + float weight; + int id; +} edgeinfo_t; + +#define ED_wt(e) (((edgeinfo_t*)AGDATA(e))->weight) +#define ED_id(e) (((edgeinfo_t*)AGDATA(e))->id) +#define ND_id(n) (((nodeinfo_t*)AGDATA(n))->id) +#define ND_deg(n) (((nodeinfo_t*)AGDATA(n))->deg) +#define ND_UF_parent(n) (((nodeinfo_t*)AGDATA(n))->UF_parent) +#define ND_UF_size(n) (((nodeinfo_t*)AGDATA(n))->UF_size) + +#endif diff --git a/lib/spine/subset.c b/lib/spine/subset.c new file mode 100644 index 000000000..f3e111f5b --- /dev/null +++ b/lib/spine/subset.c @@ -0,0 +1,95 @@ +/* vim:set shiftwidth=4 ts=4: */ + +#include +#include +#include + +static Void_t *mkPtrItem(Dt_t * d, ptritem * obj, Dtdisc_t * disc) +{ + NOTUSED(d); + NOTUSED(disc); + ptritem *np = NEW(ptritem); + np->v = obj->v; + return (Void_t *) np; +} + +static void freePtrItem(Dt_t * d, ptritem * obj, Dtdisc_t * disc) +{ + NOTUSED(d); + NOTUSED(disc); + free(obj); +} + +static int cmpptr(Dt_t * d, void **key1, void **key2, Dtdisc_t * disc) +{ + NOTUSED(d); + NOTUSED(disc); + if (*key1 > *key2) + return 1; + else if (*key1 < *key2) + return -1; + else + return 0; +} + +static Dtdisc_t ptrdisc = { + offsetof(ptritem, v), + sizeof(void *), + offsetof(ptritem, link), + (Dtmake_f) mkPtrItem, + (Dtfree_f) freePtrItem, + (Dtcompar_f) cmpptr, + 0, + 0, + 0 +}; + +Dt_t *mkSubset() +{ + Dt_t *s = dtopen(&ptrdisc, Dtoset); + return s; +} + +void addSubset(Dt_t * s, void *n) +{ + ptritem dummy; + + dummy.v = n; + dtinsert(s, &dummy); +} + +int sizeSubset(Dt_t * s) +{ + return dtsize(s); +} + +void clearSubset(Dt_t * s) +{ + dtclear(s); +} + +void closeSubset(Dt_t * s) +{ + dtclose(s); +} + +typedef struct { + walkfn wf; + void *state; +} auxstate; + +static int auxfn(Dt_t * s, void *data, void *state) +{ + NOTUSED(s); + return ((auxstate *) state)->wf(((ptritem *) data)->v, + ((auxstate *) state)->state); +} + +void walkSubset(Dt_t * s, walkfn wf, void *state) +{ + auxstate xstate; + + xstate.wf = wf; + xstate.state = state; + dtwalk(s, auxfn, &xstate); +} diff --git a/lib/spine/subset.h b/lib/spine/subset.h new file mode 100644 index 000000000..4eab7c7fd --- /dev/null +++ b/lib/spine/subset.h @@ -0,0 +1,18 @@ +#ifndef SUBSET_H +#define SUBSET_H + +typedef struct { + Dtlink_t link; + void* v; +} ptritem; + +typedef int (*walkfn)(void*, void*); + +extern Dt_t* mkSubset(void); +extern void addSubset(Dt_t*, void*); +extern void walkSubset(Dt_t*, walkfn, void*); +extern int sizeSubset(Dt_t*); +extern void clearSubset(Dt_t*); +extern void closeSubset(Dt_t*); + +#endif diff --git a/lib/spine/union_find.c b/lib/spine/union_find.c new file mode 100644 index 000000000..662b0add3 --- /dev/null +++ b/lib/spine/union_find.c @@ -0,0 +1,63 @@ +/* vim:set shiftwidth=4 ts=4: */ + +#include +#include +#include + +typedef Agnode_t node_t; + +/* union-find */ +node_t *UF_find(node_t * n) +{ + while (ND_UF_parent(n) && (ND_UF_parent(n) != n)) { + if (ND_UF_parent(ND_UF_parent(n))) + ND_UF_parent(n) = ND_UF_parent(ND_UF_parent(n)); + n = ND_UF_parent(n); + } + return n; +} + +node_t *UF_union(node_t * u, node_t * v) +{ + if (u == v) + return u; + if (ND_UF_parent(u) == NULL) { + ND_UF_parent(u) = u; + ND_UF_size(u) = 1; + } else + u = UF_find(u); + if (ND_UF_parent(v) == NULL) { + ND_UF_parent(v) = v; + ND_UF_size(v) = 1; + } else + v = UF_find(v); + if (ND_id(u) > ND_id(v)) { + ND_UF_parent(u) = v; + ND_UF_size(v) += ND_UF_size(u); + } else { + ND_UF_parent(v) = u; + ND_UF_size(u) += ND_UF_size(v); + v = u; + } + return v; +} + +void UF_remove(node_t * u, node_t * v) +{ + assert(ND_UF_size(u) == 1); + ND_UF_parent(u) = u; + ND_UF_size(v) -= ND_UF_size(u); +} + +void UF_singleton(node_t * u) +{ + ND_UF_size(u) = 1; + ND_UF_parent(u) = NULL; +} + +void UF_setname(node_t * u, node_t * v) +{ + assert(u == UF_find(u)); + ND_UF_parent(u) = v; + ND_UF_size(v) += ND_UF_size(u); +} diff --git a/lib/spine/union_find.h b/lib/spine/union_find.h new file mode 100644 index 000000000..102f5b415 --- /dev/null +++ b/lib/spine/union_find.h @@ -0,0 +1,12 @@ +#ifndef UNION_FIND_H +#define UNION_FIND_H + +#include + + extern Agnode_t *UF_find(Agnode_t *); + extern Agnode_t *UF_union(Agnode_t *, Agnode_t *); + extern void UF_remove(Agnode_t *, Agnode_t *); + extern void UF_singleton(Agnode_t *); + extern void UF_setname(Agnode_t *, Agnode_t *); + +#endif -- 2.40.0