1/* vim:set shiftwidth=4 ts=4: */
2
3#include <stdlib.h>
4#include <assert.h>
5
6#include "spinehdr.h"
7#include "quad.h"
8#include "subset.h"
9
10static int cmpdeg(const void *v0, const void *v1)
11{
12 Agnode_t *n0 = *(Agnode_t **) v0;
13 Agnode_t *n1 = *(Agnode_t **) v1;
14
15 if (ND_deg(n0) > ND_deg(n1))
16 return -1;
17 else if (ND_deg(n0) < ND_deg(n1))
18 return 1;
19 else
20 return 0;
21}
22
23void genQuads(Agraph_t * g, quadfn_t action, void *state)
24{
25 int nnodes = agnnodes(g);
26 Agnode_t **arr = N_NEW(nnodes, Agnode_t *);
27 Agraph_t *cloneg = agsubg(g, "clone", 1);
28 Dt_t **subs = N_NEW(nnodes, Dt_t *);
29 Agnode_t *n;
30 Agnode_t *v;
31 Agnode_t *u;
32 Agnode_t *w;
33 Agedge_t *e;
34 Agedge_t *f;
35
36 /* make clone graph */
37 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
38 agsubnode(cloneg, n, 1);
39 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
40 agsubedge(cloneg, e, 1);
41 }
42 }
43
44 /* sort the vertices by non-increasing degrees */
45 int j, i = 0;
46 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
47 arr[i++] = n;
48 ND_deg(n) = agdegree(cloneg, n, 1, 1);
49 }
50 qsort(arr, nnodes, sizeof(Agnode_t *), cmpdeg);
51
52 /* create index and set for each node */
53 for (i = 0; i < nnodes; i++) {
54 if (i < nnodes - 1)
55 assert(ND_deg(arr[i]) >= ND_deg(arr[i + 1]));
56 ND_id(arr[i]) = i;
57 subs[i] = mkSubset();
58 }
59
60 for (i = 0; i < nnodes; i++) {
61 v = arr[i];
62 /* for each adjacent node u of v */
63 for (e = agfstedge(cloneg, v); e; e = agnxtedge(cloneg, e, v)) {
64 if (agtail(e) == aghead(e))
65 continue;
66 if (agtail(e) == v)
67 u = aghead(e);
68 else
69 u = agtail(e);
70 /* for each adjacent node w != v of u */
71 for (f = agfstedge(cloneg, u); f; f = agnxtedge(cloneg, f, u)) {
72 if (agtail(f) == aghead(f))
73 continue;
74 if (agtail(f) == u)
75 w = aghead(f);
76 else
77 w = agtail(f);
78 addSubset(subs[ND_id(w)], u);
79 }
80 }
81 for (j = i + 1; j < nnodes; j++) {
82 if (sizeSubset(subs[j]) >= 2)
83 /* generate quadrilaterals */
84 action(v, arr[j], subs[j], state);
85 }
86 for (j = i + 1; j < nnodes; j++) {
87 if (sizeSubset(subs[j]) >= 1)
88 clearSubset(subs[j]);
89 }
90 agdelnode(cloneg, v);
91 closeSubset(subs[i]);
92 }
93
94 agclose(cloneg);
95 free(arr);
96 free(subs);
97}
98
99#ifdef TEST
100static int walker(Agnode_t * n, int *isFirst)
101{
102 if (*isFirst) {
103 *isFirst = 0;
104 printf("%s", agnameof(n));
105 } else
106 printf(",%s", agnameof(n));
107 return 0;
108}
109
110static void
111findQuads(Agnode_t * v, Agnode_t * w, Dt_t * subset, void *state)
112{
113 int first = 1;
114 printf("%s %s {", agnameof(v), agnameof(w));
115 walkSubset(subset, (walkfn) walker, &first);
116 printf("}\n");
117}
118
119int main()
120{
121 Agraph_t *g = agread(stdin, 0);
122 genQuads(g, findQuads, 0);
123 return 0;
124}
125#endif
126