summaryrefslogtreecommitdiff
path: root/nauty/gutil1.c
diff options
context:
space:
mode:
Diffstat (limited to 'nauty/gutil1.c')
-rw-r--r--nauty/gutil1.c1222
1 files changed, 1222 insertions, 0 deletions
diff --git a/nauty/gutil1.c b/nauty/gutil1.c
new file mode 100644
index 0000000..28df5d2
--- /dev/null
+++ b/nauty/gutil1.c
@@ -0,0 +1,1222 @@
+/* gutil1.c: Some graph utilities. */
+
+#include "gtools.h"
+#include "gutils.h"
+
+/**************************************************************************/
+
+void
+degstats(graph *g, int m, int n, unsigned long *edges, int *mindeg,
+ int *mincount, int *maxdeg, int *maxcount, boolean *eulerian)
+/* Compute degree-related graph properties.
+ *edges = number of edges
+ *mindeg, *mincount = minimum degree and how many there are
+ *maxdeg, *maxcount = maximum degree and how many there are
+ *eulerian = whether the graph has only even degrees
+*/
+{
+ setword *pg;
+ int i,j,d,dor;
+ int mind,mindc,maxd,maxdc;
+ unsigned long ned;
+
+ mind = n;
+ mindc = 0;
+ maxd = 0;
+ maxdc = 0;
+ ned = 0;
+ dor = 0;
+
+ pg = (setword*)g;
+ for (i = 0; i < n; ++i)
+ {
+ d = 0;
+ for (j = 0; j < m; ++j, ++pg)
+ if (*pg) d += POPCOUNT(*pg);
+
+ if (d == mind)
+ ++mindc;
+ else if (d < mind)
+ {
+ mind = d;
+ mindc = 1;
+ }
+
+ if (d == maxd)
+ ++maxdc;
+ else if (d > maxd)
+ {
+ maxd = d;
+ maxdc = 1;
+ }
+
+ dor |= d;
+ ned += d;
+ }
+
+ *mindeg = mind;
+ *mincount = mindc;
+ *maxdeg = maxd;
+ *maxcount = maxdc;
+ *edges = ned / 2;
+ *eulerian = (dor & 1) == 0;
+}
+
+/**************************************************************************/
+
+void
+degstats3(graph *g, int m, int n, unsigned long *edges, int *mindeg,
+ int *mincount, int *maxdeg, int *maxcount, int *odddeg)
+/* Compute degree-related graph properties.
+ *edges = number of edges
+ *mindeg, *mincount = minimum degree and how many there are
+ *maxdeg, *maxcount = maximum degree and how many there are
+ *odddeg = number of vertices of odd degree
+*/
+{
+ setword *pg;
+ int i,j,d,dodd;
+ int mind,mindc,maxd,maxdc;
+ unsigned long ned;
+
+ mind = n;
+ mindc = 0;
+ maxd = 0;
+ maxdc = 0;
+ ned = 0;
+ dodd = 0;
+
+ pg = (setword*)g;
+ for (i = 0; i < n; ++i)
+ {
+ d = 0;
+ for (j = 0; j < m; ++j, ++pg)
+ if (*pg) d += POPCOUNT(*pg);
+
+ if (d == mind)
+ ++mindc;
+ else if (d < mind)
+ {
+ mind = d;
+ mindc = 1;
+ }
+
+ if (d == maxd)
+ ++maxdc;
+ else if (d > maxd)
+ {
+ maxd = d;
+ maxdc = 1;
+ }
+
+ dodd += d % 2;
+ ned += d;
+ }
+
+ *mindeg = mind;
+ *mincount = mindc;
+ *maxdeg = maxd;
+ *maxcount = maxdc;
+ *edges = ned / 2;
+ *odddeg = dodd;
+}
+
+/**************************************************************************/
+
+void
+degstats2(graph *g, boolean digraph, int m, int n,
+ unsigned long *edges, int *loops,
+ int *minindeg, int *minincount, int *maxindeg, int *maxincount,
+ int *minoutdeg, int *minoutcount, int *maxoutdeg, int *maxoutcount,
+ boolean *eulerian)
+/* Compute degree-related graph properties.
+ *edges = number of edges (including loops), directed edges for digraphs
+ *loops = number of loops
+ *minindeg, *minincount = minimum in-degree and how many there are
+ *maxindeg, *maxincount = maximum in-degree and how many there are
+ *minoutdeg,*minoutcount,*maxoutdeg,*maxoutcount = similarly for out-degree
+ *eulerian = whether the undirected graph has only even degrees,
+ or the directed graph has indegree=outdegree at each vertex.
+ A loop contributes 2 to the degrees of an undirected graph and
+ 1 to each degree for a directed graph.
+*/
+{
+ setword *pg;
+ int i,j,d,dor;
+ int mind,mindc,maxd,maxdc;
+ unsigned long ned;
+ int nloops;
+#if MAXN
+ int indeg[MAXN];
+ int outdeg[MAXN];
+#else
+ DYNALLSTAT(int,indeg,indeg_sz);
+ DYNALLSTAT(int,outdeg,outdeg_sz);
+#endif
+
+ if (n == 0)
+ {
+ *edges = *loops = 0;
+ *minindeg = *minincount = *maxindeg = *maxincount = 0;
+ *minoutdeg = *minoutcount = *maxoutdeg = *maxoutcount = 0;
+ *eulerian = TRUE;
+ return;
+ }
+
+#if !MAXN
+ if (digraph)
+ {
+ DYNALLOC1(int,indeg,indeg_sz,n,"degstats2");
+ DYNALLOC1(int,outdeg,outdeg_sz,n,"degstats2");
+ }
+#endif
+
+ if (!digraph)
+ {
+ mind = n+2;
+ mindc = 0;
+ maxd = 0;
+ maxdc = 0;
+ ned = 0;
+ dor = 0;
+ nloops = 0;
+
+ pg = (setword*)g;
+ for (i = 0; i < n; ++i)
+ {
+ d = 0;
+ if (ISELEMENT(pg,i))
+ {
+ ++d;
+ ++nloops;
+ }
+ for (j = 0; j < m; ++j, ++pg)
+ if (*pg) d += POPCOUNT(*pg);
+
+ if (d == mind)
+ ++mindc;
+ else if (d < mind)
+ {
+ mind = d;
+ mindc = 1;
+ }
+
+ if (d == maxd)
+ ++maxdc;
+ else if (d > maxd)
+ {
+ maxd = d;
+ maxdc = 1;
+ }
+
+ dor |= d;
+ ned += d;
+ }
+
+ *minindeg = *minoutdeg = mind;
+ *minincount = *minoutcount = mindc;
+ *maxindeg = *maxoutdeg = maxd;
+ *maxincount = *maxoutcount = maxdc;
+ *edges = ned / 2;
+ *eulerian = (dor & 1) == 0;
+ *loops = nloops;
+ }
+ else
+ {
+ for (i = 0; i < n; ++i) indeg[i] = outdeg[i] = 0;
+
+ nloops = 0;
+ ned = 0;
+ for (i = 0, pg = (setword*)g; i < n; ++i, pg += m)
+ {
+ if (ISELEMENT(pg,i)) ++nloops;
+ for (j = -1; (j = nextelement(pg,m,j)) >= 0;)
+ {
+ ++outdeg[i];
+ ++indeg[j];
+ }
+ ned += outdeg[i];
+ }
+ *edges = ned;
+ *loops = nloops;
+
+ mind = maxd = indeg[0];
+ mindc = maxdc = 1;
+
+ for (i = 1; i < n; ++i)
+ {
+ d = indeg[i];
+
+ if (d == mind)
+ ++mindc;
+ else if (d < mind)
+ {
+ mind = d;
+ mindc = 1;
+ }
+
+ if (d == maxd)
+ ++maxdc;
+ else if (d > maxd)
+ {
+ maxd = d;
+ maxdc = 1;
+ }
+ }
+ *minindeg = mind;
+ *minincount = mindc;
+ *maxindeg = maxd;
+ *maxincount = maxdc;
+
+ mind = maxd = outdeg[0];
+ mindc = maxdc = 1;
+
+ for (i = 1; i < n; ++i)
+ {
+ d = outdeg[i];
+
+ if (d == mind)
+ ++mindc;
+ else if (d < mind)
+ {
+ mind = d;
+ mindc = 1;
+ }
+
+ if (d == maxd)
+ ++maxdc;
+ else if (d > maxd)
+ {
+ maxd = d;
+ maxdc = 1;
+ }
+ }
+ *minoutdeg = mind;
+ *minoutcount = mindc;
+ *maxoutdeg = maxd;
+ *maxoutcount = maxdc;
+
+ for (i = 0; i < n; ++i)
+ if (indeg[i] != outdeg[i]) break;
+ *eulerian = (i == n);
+ }
+}
+
+/*********************************************************************/
+
+void
+sources_sinks(graph *g, int m, int n, int *sources, int *sinks)
+/* Count the sources and sinks. For an undirected graph, these
+ are just the isolated vertices. For a directed graph, they have
+ their usual meanings. A vertex with a loop is neither a source
+ nor a sink.
+*/
+{
+ setword rowor,wk;
+ int i,j,nsource,nsink;
+ set *gi;
+#if MAXM
+ setword work[MAXM+1];
+#else
+ DYNALLSTAT(setword,work,work_sz);
+ DYNALLOC1(setword,work,work_sz,m,"sources_sinks");
+#endif
+
+ if (n == 0) { *sources = *sinks = 0; return; }
+
+ if (m == 1)
+ {
+ nsink = 0;
+ wk = 0;
+ for (i = 0; i < n; ++i)
+ {
+ if (g[i] == 0) ++nsink;
+ wk |= g[i];
+ }
+ *sinks = nsink;
+ *sources = n - POPCOUNT(wk);
+ return;
+ }
+
+ for (i = 0; i < m; ++i) work[i] = 0;
+ nsink = 0;
+ for (i = 0, gi = g; i < n; ++i, gi += m)
+ {
+ rowor = 0;
+ for (j = 0; j < m; ++j)
+ {
+ rowor |= gi[j];
+ work[j] |= gi[j];
+ }
+ if (rowor == 0) ++nsink;
+ }
+ *sinks = nsink;
+ nsource = n;
+ for (j = 0; j < m; ++j)
+ nsource -= POPCOUNT(work[j]);
+ *sources = nsource;
+}
+
+/*********************************************************************/
+
+boolean
+isconnected1(graph *g, int n)
+/* test if g is connected (m=1) */
+{
+ setword seen,expanded,toexpand;
+ int i;
+
+ if (n == 0) return FALSE;
+
+ seen = bit[0];
+ expanded = 0;
+
+ while ((toexpand = (seen & ~expanded)) != 0)
+ {
+ i = FIRSTBITNZ(toexpand);
+ expanded |= bit[i];
+ seen |= g[i];
+ }
+
+ return POPCOUNT(seen) == n;
+}
+
+/**************************************************************************/
+
+boolean
+isconnected(graph *g, int m, int n)
+/* Test if g is connected */
+{
+ int i,head,tail,w;
+ set *gw;
+#if MAXN
+ int queue[MAXN],visited[MAXN];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+ DYNALLSTAT(int,visited,visited_sz);
+#endif
+
+ if (n == 0) return FALSE;
+ if (m == 1) return isconnected1(g,n);
+
+#if !MAXN
+ DYNALLOC1(int,queue,queue_sz,n,"isconnected");
+ DYNALLOC1(int,visited,visited_sz,n,"isconnected");
+#endif
+
+ for (i = 0; i < n; ++i) visited[i] = 0;
+
+ queue[0] = 0;
+ visited[0] = 1;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ gw = GRAPHROW(g,w,m);
+ for (i = -1; (i = nextelement(gw,m,i)) >= 0;)
+ {
+ if (!visited[i])
+ {
+ visited[i] = 1;
+ queue[tail++] = i;
+ }
+ }
+ }
+
+ return tail == n;
+}
+
+/**************************************************************************/
+
+boolean
+issubconnected(graph *g, set *sub, int m, int n)
+/* Test if the subset of g induced by sub is connected. Empty is connected. */
+/* Note that the value for empty subgraphs disagrees with isconnected() */
+{
+ int i,head,tail,w,subsize;
+ set *gw;
+#if MAXN
+ int queue[MAXN],visited[MAXN];
+ setword subw[MAXM];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+ DYNALLSTAT(int,visited,visited_sz);
+ DYNALLSTAT(set,subw,subw_sz);
+
+ DYNALLOC1(int,queue,queue_sz,n,"issubconnected");
+ DYNALLOC1(int,visited,visited_sz,n,"issubconnected");
+ DYNALLOC1(set,subw,subw_sz,m,"issubconnected");
+#endif
+
+ subsize = 0;
+ for (i = 0; i < m; ++i) subsize += (sub[i] ? POPCOUNT(sub[i]) : 0);
+
+ if (subsize <= 1) return TRUE;
+
+ for (i = 0; i < n; ++i) visited[i] = 0;
+
+ i = nextelement(sub,m,-1);
+ queue[0] = i;
+ visited[i] = 1;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ gw = GRAPHROW(g,w,m);
+ for (i = 0; i < m; ++i) subw[i] = gw[i] & sub[i];
+
+ for (i = -1; (i = nextelement(subw,m,i)) >= 0;)
+ {
+ if (!visited[i])
+ {
+ visited[i] = 1;
+ queue[tail++] = i;
+ }
+ }
+ }
+
+ return tail == subsize;
+}
+
+/**********************************************************************/
+
+boolean
+isbiconnected1(graph *g, int n)
+/* Test if g is biconnected; version for m=1. */
+{
+ int sp,v,w;
+ setword sw;
+ int numvis;
+ setword visited;
+ int num[WORDSIZE],lp[WORDSIZE],stack[WORDSIZE];
+
+ if (n <= 2) return FALSE;
+
+ visited = bit[0];
+ stack[0] = 0;
+ num[0] = 0;
+ lp[0] = 0;
+ numvis = 1;
+ sp = 0;
+ v = 0;
+
+ for (;;)
+ {
+ if ((sw = g[v] & ~visited)) /* not "==" */
+ {
+ w = v;
+ v = FIRSTBITNZ(sw); /* visit next child */
+ stack[++sp] = v;
+ visited |= bit[v];
+ lp[v] = num[v] = numvis++;
+ sw = g[v] & visited & ~bit[w];
+ while (sw)
+ {
+ w = FIRSTBITNZ(sw);
+ sw &= ~bit[w];
+ if (num[w] < lp[v]) lp[v] = num[w];
+ }
+ }
+ else
+ {
+ w = v; /* back up to parent */
+ if (sp <= 1) return numvis == n;
+ v = stack[--sp];
+ if (lp[w] >= num[v]) return FALSE;
+ if (lp[w] < lp[v]) lp[v] = lp[w];
+ }
+ }
+}
+
+/**********************************************************************/
+
+boolean
+isbiconnected(graph *g, int m, int n)
+/* test if g is biconnected */
+{
+ int sp,v,vc;
+ int numvis;
+ set *gv;
+#if MAXN
+ int num[MAXN],lp[MAXN],stack[MAXN];
+#else
+ DYNALLSTAT(int,num,num_sz);
+ DYNALLSTAT(int,lp,lp_sz);
+ DYNALLSTAT(int,stack,stack_sz);
+#endif
+
+ if (n <= 2) return FALSE;
+ if (m == 1) return isbiconnected1(g,n);
+
+#if !MAXN
+ DYNALLOC1(int,num,num_sz,n,"isbiconnected");
+ DYNALLOC1(int,lp,lp_sz,n,"isbiconnected");
+ DYNALLOC1(int,stack,stack_sz,n,"isbiconnected");
+#endif
+
+ num[0] = 0;
+ for (v = 1; v < n; ++v) num[v] = -1;
+ lp[0] = 0;
+ numvis = 1;
+ sp = 0;
+ v = 0;
+ vc = -1;
+ gv = (set*)g;
+
+ for (;;)
+ {
+ vc = nextelement(gv,m,vc);
+ if (vc < 0)
+ {
+ if (sp <= 1) return numvis == n;
+ vc = v;
+ v = stack[--sp];
+ gv = GRAPHROW(g,v,m);
+ if (lp[vc] >= num[v]) return FALSE;
+ if (lp[vc] < lp[v]) lp[v] = lp[vc];
+ }
+ else if (num[vc] < 0)
+ {
+ stack[++sp] = vc;
+ v = vc;
+ gv = GRAPHROW(g,v,m);
+ vc = -1;
+ lp[v] = num[v] = numvis++;
+ }
+ else if (vc != v)
+ {
+ if (num[vc] < lp[v]) lp[v] = num[vc];
+ }
+ }
+}
+
+/**************************************************************************/
+
+boolean
+twocolouring(graph *g, int *colour, int m, int n)
+/* If g is bipartite, set colour[*] to 0 or 1 to indicate an example
+ of 2-colouring and return TRUE. Otherwise return FALSE.
+ Colour 0 is assigned to the first vertex of each component. */
+{
+ int i,head,tail,v,w,need;
+ set *gw;
+ setword xg;
+#if MAXN
+ int queue[MAXN];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+#endif
+
+#if !MAXN
+ DYNALLOC1(int,queue,queue_sz,n,"twocolouring");
+#endif
+
+ if (n == 0) return TRUE;
+ for (i = 0; i < n; ++i) colour[i] = -1;
+
+ if (m == 1)
+ {
+ for (v = 0; v < n; ++v)
+ if (colour[v] < 0)
+ {
+ queue[0] = v;
+ colour[v] = 0;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ need = 1 - colour[w];
+ xg = g[w];
+ while (xg)
+ {
+ TAKEBIT(i,xg);
+ if (colour[i] < 0)
+ {
+ colour[i] = need;
+ queue[tail++] = i;
+ }
+ else if (colour[i] != need)
+ return FALSE;
+ }
+ }
+ }
+ }
+ else
+ {
+ for (v = 0; v < n; ++v)
+ if (colour[v] < 0)
+ {
+ queue[0] = v;
+ colour[v] = 0;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ need = 1 - colour[w];
+ gw = GRAPHROW(g,w,m);
+ for (i = -1; (i = nextelement(gw,m,i)) >= 0;)
+ {
+ if (colour[i] < 0)
+ {
+ colour[i] = need;
+ queue[tail++] = i;
+ }
+ else if (colour[i] != need)
+ return FALSE;
+ }
+ }
+ }
+ }
+
+ return TRUE;
+}
+
+/**************************************************************************/
+
+boolean
+isbipartite(graph *g, int m, int n)
+/* Test if g is bipartite */
+{
+#if MAXN
+ int colour[MAXN];
+#else
+ DYNALLSTAT(int,colour,colour_sz);
+
+ DYNALLOC1(int,colour,colour_sz,n,"isbipartite");
+#endif
+
+ return twocolouring(g,colour,m,n);
+}
+
+/**************************************************************************/
+
+int
+bipartiteside(graph *g, int m, int n)
+/* If g is not bipartite, return 0.
+ Otherwise return the size of the smallest of the two parts
+ of a 2-coluring for which this value is smallest. */
+{
+ int i,head,tail,v,w,need;
+ set *gw;
+ setword xg;
+ int ans,col[2];
+#if MAXN
+ int queue[MAXN];
+ int colour[MAXN];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+ DYNALLSTAT(int,colour,colour_sz);
+#endif
+
+#if !MAXN
+ DYNALLOC1(int,queue,queue_sz,n,"twocolouring");
+ DYNALLOC1(int,colour,colour_sz,n,"isbipartite");
+#endif
+
+ if (n == 0) return 0;
+ for (i = 0; i < n; ++i) colour[i] = -1;
+ ans = 0;
+
+ if (m == 1)
+ {
+ for (v = 0; v < n; ++v)
+ {
+ if (colour[v] < 0)
+ {
+ queue[0] = v;
+ colour[v] = 0;
+ col[0] = 1; col[1] = 0;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ need = 1 - colour[w];
+ xg = g[w];
+ while (xg)
+ {
+ TAKEBIT(i,xg);
+ if (colour[i] < 0)
+ {
+ colour[i] = need;
+ ++col[need];
+ queue[tail++] = i;
+ }
+ else if (colour[i] != need)
+ return 0;
+ }
+ }
+ if (col[0] <= col[1]) ans += col[0];
+ else ans += col[1];
+ }
+ }
+ }
+ else
+ {
+ for (v = 0; v < n; ++v)
+ {
+ if (colour[v] < 0)
+ {
+ queue[0] = v;
+ colour[v] = 0;
+ col[0] = 1; col[1] = 0;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ need = 1 - colour[w];
+ gw = GRAPHROW(g,w,m);
+ for (i = -1; (i = nextelement(gw,m,i)) >= 0;)
+ {
+ if (colour[i] < 0)
+ {
+ colour[i] = need;
+ ++col[need];
+ queue[tail++] = i;
+ }
+ else if (colour[i] != need)
+ return 0;
+ }
+ }
+ if (col[0] <= col[1]) ans += col[0];
+ else ans += col[1];
+ }
+ }
+ }
+
+ return ans;
+}
+
+/**************************************************************************/
+
+int
+girth(graph *g, int m, int n)
+/* Find the girth of graph g. 0 means acyclic. */
+{
+ int i,head,tail,v,w;
+ int best,c,dw1;
+ set *gw;
+#if MAXN
+ int dist[MAXN],queue[MAXN];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+ DYNALLSTAT(int,dist,dist_sz);
+
+ DYNALLOC1(int,queue,queue_sz,n,"girth");
+ DYNALLOC1(int,dist,dist_sz,n,"girth");
+#endif
+
+ if (n == 0) return 0;
+ best = n+3;
+
+ for (v = 0; v < n; ++v)
+ {
+ for (i = 0; i < n; ++i) dist[i] = -1;
+
+ queue[0] = v;
+ dist[v] = 0;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ gw = GRAPHROW(g,w,m);
+ dw1 = dist[w] + 1;
+ for (i = -1; (i = nextelement(gw,m,i)) >= 0;)
+ {
+ if (dist[i] < 0)
+ {
+ dist[i] = dw1;
+ queue[tail++] = i;
+ }
+ else if (dist[i] >= dist[w])
+ {
+ c = dw1 + dist[i];
+ if (c < best) best = c;
+ if ((c & 1) != 0 || c > best) break;
+ }
+ }
+ if (i >= 0) break;
+ }
+ if (best == 3) return 3;
+ }
+
+ return (best > n ? 0 : best);
+}
+
+/**************************************************************************/
+
+void
+find_dist(graph *g, int m, int n, int v, int *dist)
+/* Put in dist[0..n-1] the distance of each vertex from v.
+ Vertices in a different component are given the distance n. */
+{
+ int i,head,tail,w;
+ set *gw;
+#if MAXN
+ int queue[MAXN];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+#endif
+
+#if !MAXN
+ DYNALLOC1(int,queue,queue_sz,n,"isconnected");
+#endif
+
+ if (n == 0) return;
+ for (i = 0; i < n; ++i) dist[i] = n;
+
+ queue[0] = v;
+ dist[v] = 0;
+
+ head = 0;
+ tail = 1;
+ while (tail < n && head < tail)
+ {
+ w = queue[head++];
+ gw = GRAPHROW(g,w,m);
+ for (i = -1; (i = nextelement(gw,m,i)) >= 0;)
+ {
+ if (dist[i] == n)
+ {
+ dist[i] = dist[w] + 1;
+ queue[tail++] = i;
+ }
+ }
+ }
+}
+
+/**************************************************************************/
+
+void
+find_dist2(graph *g, int m, int n, int v, int w, int *dist)
+/* Put in dist[0..n-1] the distance of each vertex from {v,w}.
+ Vertices in a different component are given the distance n. */
+{
+ int i,head,tail,x;
+ set *gx;
+#if MAXN
+ int queue[MAXN];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+#endif
+
+#if !MAXN
+ DYNALLOC1(int,queue,queue_sz,n,"isconnected");
+#endif
+
+ if (n == 0) return;
+ for (i = 0; i < n; ++i) dist[i] = n;
+
+ queue[0] = v;
+ queue[1] = w;
+ dist[v] = dist[w] = 0;
+
+ head = 0;
+ tail = 2;
+ while (tail < n && head < tail)
+ {
+ x = queue[head++];
+ gx = GRAPHROW(g,x,m);
+ for (i = -1; (i = nextelement(gx,m,i)) >= 0;)
+ {
+ if (dist[i] == n)
+ {
+ dist[i] = dist[x] + 1;
+ queue[tail++] = i;
+ }
+ }
+ }
+}
+
+/**************************************************************************/
+
+int
+numcomponents1(graph *g, int n)
+/* Find number of components of undirected graph; case m=1 */
+{
+ setword notvisited,queue;
+ int nc,i;
+
+ nc = 0;
+ notvisited = ALLMASK(n);
+
+ while (notvisited)
+ {
+ ++nc;
+ queue = SWHIBIT(notvisited);
+ notvisited &= ~queue;
+ while (queue)
+ {
+ TAKEBIT(i,queue);
+ notvisited &= ~bit[i];
+ queue |= g[i] & notvisited;
+ }
+ }
+
+ return nc;
+}
+
+int
+numcomponents(graph *g, int m, int n)
+/* Find number of components of undirected graph */
+{
+ int i,nc,head,tail,v,w;
+ set *gw;
+#if MAXN
+ int queue[MAXN];
+ set notvisited[MAXM+1]; /* +1 to satisfy gcc12 on ARM */
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+ DYNALLSTAT(set,notvisited,notvisited_sz);
+#endif
+
+ if (n == 0) return 0;
+ if (m == 1) return numcomponents1(g,n);
+
+#if !MAXN
+ DYNALLOC1(int,queue,queue_sz,n,"numcomponents");
+ DYNALLOC1(set,notvisited,notvisited_sz,m,"numcomponents");
+#endif
+
+ EMPTYSET(notvisited,m);
+ for (i = 0; i < n; ++i) ADDELEMENT(notvisited,i);
+
+ nc = 0;
+
+ for (v = -1; (v = nextelement(notvisited,m,v)) >= 0;)
+ {
+ ++nc;
+ queue[0] = v;
+
+ head = 0;
+ tail = 1;
+ while (head < tail)
+ {
+ w = queue[head++];
+ gw = GRAPHROW(g,w,m);
+ for (i = -1; (i = nextelement(gw,m,i)) >= 0;)
+ {
+ if (ISELEMENT(notvisited,i))
+ {
+ DELELEMENT(notvisited,i);
+ queue[tail++] = i;
+ }
+ }
+ }
+ }
+
+ return nc;
+}
+
+/**************************************************************************/
+
+void
+diamstats(graph *g, int m, int n, int *radius, int *diameter)
+/* Find the radius and diameter. Both -1 if g is disconnected.
+ We use an O(mn) algorithm, which is pretty disgraceful. */
+{
+ int v,i,head,tail,w;
+ int ecc,diam,rad;
+ set *gw;
+#if MAXN
+ int queue[MAXN],dist[MAXN];
+#else
+ DYNALLSTAT(int,queue,queue_sz);
+ DYNALLSTAT(int,dist,dist_sz);
+#endif
+
+ /* if (m == 1) {diamstats1(g,n,radius,diameter); return; } */
+
+#if !MAXN
+ DYNALLOC1(int,queue,queue_sz,n,"isconnected");
+ DYNALLOC1(int,dist,dist_sz,n,"isconnected");
+#endif
+
+ if (n == 0)
+ {
+ *radius = *diameter = 0;
+ return;
+ }
+
+ diam = -1;
+ rad = n;
+
+ for (v = 0; v < n; ++v)
+ {
+ for (i = 0; i < n; ++i) dist[i] = -1;
+
+ queue[0] = v;
+ dist[v] = 0;
+
+ head = 0;
+ tail = 1;
+ while (tail < n && head < tail)
+ {
+ w = queue[head++];
+ gw = GRAPHROW(g,w,m);
+ for (i = -1; (i = nextelement(gw,m,i)) >= 0;)
+ {
+ if (dist[i] < 0)
+ {
+ dist[i] = dist[w] + 1;
+ queue[tail++] = i;
+ }
+ }
+ }
+
+ if (tail < n)
+ {
+ *diameter = *radius = -1;
+ return;
+ }
+
+ ecc = dist[queue[n-1]];
+
+ if (ecc > diam) diam = ecc;
+ if (ecc < rad) rad = ecc;
+ }
+
+ *diameter = diam;
+ *radius = rad;
+}
+
+/**************************************************************************/
+
+static long
+maxclnode1(graph *g, setword cliq, setword cov, int maxv)
+/* Internal search node. cov has all the vertices outside cliq that
+ * cover all of cliq. maxv is the last vertex of cliq.
+ */
+{
+ long ans;
+ int i;
+ setword w;
+
+ if (cov == 0) return 1;
+
+ ans = 0;
+ w = cov & BITMASK(maxv);
+ while (w)
+ {
+ TAKEBIT(i,w);
+ ans += maxclnode1(g,cliq|bit[i],cov&g[i]&~bit[i],i);
+ }
+ return ans;
+}
+
+long
+maxcliques(graph *g, int m, int n)
+/* Find the number of maximal cliques */
+{
+ int i;
+ long ans;
+
+ if (n == 0) return 0;
+
+ if (m == 1)
+ {
+ ans = 0;
+ for (i = 0; i < n; ++i)
+ ans += maxclnode1(g,bit[i],g[i],i);
+ }
+ else
+ {
+ fprintf(stderr,">E maxcliques() is only implemented for m=1\n");
+ exit(1);
+ }
+
+ return ans;
+}
+
+/**************************************************************************/
+
+static void
+maxcsnode1(int *best, graph *g, setword cliq, setword cov, int maxv)
+/* Internal search node. cov has all the vertices outside cliq that
+ * cover all of cliq. maxv is the last vertex of cliq.
+ * *best is the largest clique known so far.
+ */
+{
+ int i,s;
+ setword w;
+
+ if (cov == 0) return;
+
+ w = cov & BITMASK(maxv);
+
+ s = POPCOUNT(cliq);
+ if (s + POPCOUNT(w) <= *best) return;
+ if (w)
+ {
+ if (s + 1 > *best) *best = s + 1;
+ while (w)
+ {
+ TAKEBIT(i,w);
+ maxcsnode1(best,g,cliq|bit[i],cov&g[i]&~bit[i],i);
+ }
+ }
+}
+
+int
+maxcliquesize(graph *g, int m, int n)
+/* Find the largest clique size */
+{
+ int i,best;
+
+ if (n == 0) return 0;
+
+ if (m == 1)
+ {
+ best = 1;
+ for (i = 0; i < n; ++i)
+ maxcsnode1(&best,g,bit[i],g[i],i);
+ }
+ else
+ {
+ fprintf(stderr,">E maxcliquesize() is only implemented for m=1\n");
+ exit(1);
+ }
+
+ return best;
+}
+
+int
+maxindsetsize(graph *g, int m, int n)
+/* Find the largest independent set size */
+{
+ int i,best;
+ graph gc[WORDSIZE];
+ setword all;
+
+ if (n == 0) return 0;
+
+ if (m == 1)
+ {
+ all = ALLMASK(n);
+ for (i = 0; i < n; ++i) gc[i] = g[i] ^ all ^ bit[i];
+
+ best = 1;
+ for (i = 0; i < n; ++i)
+ maxcsnode1(&best,gc,bit[i],gc[i],i);
+ }
+ else
+ {
+ fprintf(stderr,">E maxindsetsize() is only implemented for m=1\n");
+ exit(1);
+ }
+
+ return best;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 07:35:50 +0000