1 /** \file
2 * \brief Implements graph generator for hierarchical graphs.
3 *
4 * \author Carsten Gutwenger, Christoph Buchheim
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32
33 #include <ogdf/basic/SList.h>
34 #include <ogdf/basic/graph_generators/deterministic.h>
35 #include <ogdf/basic/graph_generators/randomHierarchy.h>
36
37 using std::minstd_rand;
38 using std::uniform_int_distribution;
39 using std::uniform_real_distribution;
40
41
42 namespace ogdf {
43
44
45 class BEdge {
46 public:
47 int head, tail, id, pos;
48 BEdge *next;
BEdge(int t,int h,int c)49 BEdge(int t,int h,int c) : head(h), tail(t), id(c), pos(-1), next(nullptr) { }
50 OGDF_NEW_DELETE
51 };
52
53 using bEdge = BEdge*;
54
55
56 OGDF_DECLARE_COMPARER(CmpTail, bEdge, int, x->tail);
57 OGDF_DECLARE_COMPARER(CmpHead, bEdge, int, x->head);
58
59
randomHierarchy(Graph & G,int numberOfNodes,int numberOfEdges,bool planar,bool singleSource,bool longEdges)60 void randomHierarchy(
61 Graph &G,
62 int numberOfNodes,
63 int numberOfEdges,
64 bool planar,
65 bool singleSource,
66 bool longEdges)
67 {
68 Array<node> nnr (3*numberOfNodes);
69 Array<int> vrt (3*numberOfNodes);
70 Array<int> fst (numberOfNodes+1);
71
72 /** Place nodes **/
73
74 emptyGraph(G, numberOfNodes);
75
76 minstd_rand rng(randomSeed());
77 uniform_real_distribution<> dist_0_1(0.0,1.0);
78
79 int numberOfLayers = 0, totNumber = 0, realCount = 0;
80 fst[0] = 0;
81 for(node v : G.nodes) {
82 if(longEdges && numberOfLayers) vrt[totNumber++] = 1;
83
84 nnr[totNumber] = v;
85 vrt[totNumber++] = 0;
86 realCount++;
87 double r = dist_0_1(rng);
88 if((totNumber == 1 && singleSource) || realCount == numberOfNodes || r*r*numberOfNodes < 1)
89 {
90 if(longEdges && numberOfLayers)
91 vrt[totNumber++] = 1;
92 fst[++numberOfLayers] = totNumber;
93 }
94 }
95
96 /** Determine allowed neighbours **/
97
98 Array<int> leftN (totNumber);
99 Array<int> rightN(totNumber);
100 for(int layer = 1; layer < numberOfLayers; layer++)
101 {
102 if(planar) {
103 int n1 = fst[layer-1];
104 int n2 = fst[layer];
105 leftN[n2] = n1;
106 while(n1 < fst[layer] && n2 < fst[layer+1]) {
107 double r = dist_0_1(rng);
108 if(n1 != fst[layer]-1 &&
109 (n2 == fst[layer+1]-1 ||
110 r < (double)(fst[layer]-fst[layer-1])/(double)(fst[layer+1]-fst[layer-1])))
111 n1++;
112 else {
113 rightN[n2] = n1;
114 if(++n2 < fst[layer+1])
115 leftN[n2] = n1;
116 }
117 }
118 }
119 else
120 for(int n2 = fst[layer]; n2 < fst[layer+1]; n2++) {
121 leftN [n2] = fst[layer-1];
122 rightN[n2] = fst[layer]-1;
123 }
124 }
125
126 /** Insert edges **/
127
128 List<bEdge> startEdges;
129 Array<SList<bEdge>> edgeIn (totNumber);
130 Array<SList<bEdge>> edgeOut(totNumber);
131
132 if (numberOfLayers) {
133 double x1 = numberOfEdges;
134 double x2 = 0;
135 for (int n2 = fst[1]; n2 < totNumber; n2++) {
136 if (!vrt[n2])
137 x2 += rightN[n2] - leftN[n2] + 1;
138 }
139
140 int idc = 0;
141 for (int n2 = fst[1]; n2 < totNumber; n2++) {
142 if (!vrt[n2]) {
143 bool connected = !singleSource;
144 for (int n1 = leftN[n2]; n1 <= rightN[n2] || !connected; n1++) {
145 double r = dist_0_1(rng);
146 if (r < x1 / x2 || n1 > rightN[n2]) {
147 int next = (n1 <= rightN[n2] ? n1 : uniform_int_distribution<>(leftN[n2], rightN[n2])(rng));
148 int act = n2;
149 bEdge nextEdge = new BEdge(next, act, idc++);
150 while (vrt[next]) {
151 act = next;
152 next = uniform_int_distribution<>(leftN[act], rightN[act])(rng);
153 edgeOut[act].pushBack(nextEdge);
154 nextEdge = new BEdge(next, act, idc++);
155 edgeIn[act].pushBack(nextEdge);
156 }
157 startEdges.pushBack(nextEdge);
158 connected = true;
159 x1 -= 1;
160 }
161 if (n1 <= rightN[n2])
162 x2 -= 1;
163 }
164 }
165 }
166 }
167
168 if(planar)
169 for(int act = 0; act < totNumber; act++) {
170 CmpTail cmpTail;
171 edgeIn[act].quicksort(cmpTail);
172 CmpHead cmpHead;
173 edgeOut[act].quicksort(cmpHead);
174 }
175
176 for(int act = 0; act < totNumber; act++) {
177 for(bEdge nextEdge : edgeIn[act]) {
178 nextEdge->next = edgeOut[act].popFrontRet();
179 }
180 }
181
182 for(bEdge actEdge : startEdges) {
183 bEdge nextEdge = actEdge;
184 while(vrt[nextEdge->head])
185 nextEdge = nextEdge->next;
186 G.newEdge(nnr[actEdge->tail], nnr[nextEdge->head]);
187 }
188
189 /** Clean up **/
190 for(bEdge nextEdge : startEdges) {
191 bEdge toDelete = nextEdge;
192 while(vrt[nextEdge->head]) {
193 nextEdge = nextEdge->next;
194 delete toDelete;
195 toDelete = nextEdge;
196 }
197 delete toDelete;
198 }
199 }
200
201
202 }
203