1 /** \file
2 * \brief Implementation of the class UpwardPlanarity.
3 *
4 * \author Robert Zeranski
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 #include <ogdf/upward/UpwardPlanarity.h>
33
34 #include <ogdf/upward/internal/UpwardPlanarityEmbeddedDigraph.h>
35 #include <ogdf/upward/internal/UpwardPlanaritySingleSource.h>
36 #include <ogdf/upward/internal/UpSAT.h>
37
38 namespace ogdf {
39
40 //
41 // General digraphs
42 //
43
isUpwardPlanar(Graph & G)44 bool UpwardPlanarity::isUpwardPlanar(Graph &G) {
45 UpSAT tester(G);
46 return tester.testUpwardPlanarity();
47 }
48
embedUpwardPlanar(Graph & G,adjEntry & externalToItsRight)49 bool UpwardPlanarity::embedUpwardPlanar(Graph &G, adjEntry& externalToItsRight) {
50 UpSAT embedder(G);
51 return embedder.embedUpwardPlanar(externalToItsRight);
52 }
53
54 #if 0
55 int UpwardPlanarity::maximalFeasibleUpwardPlanarSubgraph(const Graph &G, GraphCopy &GC) {
56 MaximalFUPS m(G,0);
57 return m.computeMFUPS(GC);
58 }
59 #endif
60
61
62 //
63 // Biconnected digraphs
64 //
65
isUpwardPlanar_embedded(const Graph & G)66 bool UpwardPlanarity::isUpwardPlanar_embedded(const Graph &G)
67 {
68 if (isBiconnected(G) && G.representsCombEmbedding() && isAcyclic(G)) {
69 UpwardPlanarityEmbeddedDigraph p(G);
70 return p.isUpwardPlanarEmbedded();
71 }
72 return false;
73 }
74
75
isUpwardPlanar_embedded(const Graph & G,List<adjEntry> & possibleExternalFaces)76 bool UpwardPlanarity::isUpwardPlanar_embedded(const Graph &G, List<adjEntry> &possibleExternalFaces)
77 {
78 if (isBiconnected(G) && G.representsCombEmbedding() && isAcyclic(G)) {
79 UpwardPlanarityEmbeddedDigraph p(G);
80 return p.isUpwardPlanarEmbedded(possibleExternalFaces);
81 }
82 return false;
83 }
84
85 //
86 // Triconnected digraphs
87 //
88
89
isUpwardPlanar_triconnected(const Graph & G)90 bool UpwardPlanarity::isUpwardPlanar_triconnected(const Graph &G)
91 {
92 if (isTriconnected(G) && isAcyclic(G)) {
93 Graph H(G);
94 BoyerMyrvold p;
95 if (!p.planarEmbed(H)) return false;
96 return isUpwardPlanar_embedded(H);
97 }
98 return false;
99 }
100
101
upwardPlanarEmbed_triconnected(Graph & G)102 bool UpwardPlanarity::upwardPlanarEmbed_triconnected(Graph &G)
103 {
104 if (isTriconnected(G) && isAcyclic(G)) {
105 BoyerMyrvold p;
106 if (!p.planarEmbed(G)) return false;
107 return isUpwardPlanar_embedded(G);
108 }
109 return false;
110 }
111
112 //
113 // Single-source digraphs
114 //
115
isUpwardPlanar_singleSource(const Graph & G)116 bool UpwardPlanarity::isUpwardPlanar_singleSource(const Graph &G)
117 {
118 NodeArray<SListPure<adjEntry> > adjacentEdges;
119 return UpwardPlanaritySingleSource::testAndFindEmbedding(G, false, adjacentEdges);
120 }
121
122
upwardPlanarEmbed_singleSource(Graph & G)123 bool UpwardPlanarity::upwardPlanarEmbed_singleSource(Graph &G)
124 {
125 NodeArray<SListPure<adjEntry> > adjacentEdges(G);
126 if(!UpwardPlanaritySingleSource::testAndFindEmbedding(G, true, adjacentEdges))
127 return false;
128
129 node superSink;
130 SList<edge> augmentedEdges;
131 UpwardPlanaritySingleSource::embedAndAugment(G, adjacentEdges, false, superSink, augmentedEdges);
132
133 return true;
134 }
135
136
upwardPlanarAugment_singleSource(Graph & G)137 bool UpwardPlanarity::upwardPlanarAugment_singleSource(Graph &G)
138 {
139 node superSink;
140 SList<edge> augmentedEdges;
141
142 return upwardPlanarAugment_singleSource(G, superSink, augmentedEdges);
143 }
144
145
upwardPlanarAugment_singleSource(Graph & G,node & superSink,SList<edge> & augmentedEdges)146 bool UpwardPlanarity::upwardPlanarAugment_singleSource(
147 Graph &G,
148 node &superSink,
149 SList<edge> &augmentedEdges)
150 {
151 NodeArray<SListPure<adjEntry> > adjacentEdges(G);
152 if(!UpwardPlanaritySingleSource::testAndFindEmbedding(G, true, adjacentEdges))
153 return false;
154
155 UpwardPlanaritySingleSource::embedAndAugment(G, adjacentEdges, true, superSink, augmentedEdges);
156 return true;
157 }
158
159
isUpwardPlanar_singleSource_embedded(const ConstCombinatorialEmbedding & E,SList<face> & externalFaces)160 bool UpwardPlanarity::isUpwardPlanar_singleSource_embedded(
161 const ConstCombinatorialEmbedding &E,
162 SList<face> &externalFaces)
163 {
164 const Graph &G = E;
165 OGDF_ASSERT(G.representsCombEmbedding());
166
167 externalFaces.clear();
168
169 // trivial cases
170 if(G.empty())
171 return true;
172
173 if(!isAcyclic(G))
174 return false;
175
176 // determine the single source in G
177 node s;
178 if(!hasSingleSource(G,s))
179 return false;
180
181 // construct face-sink graph anf find possible external faces
182 FaceSinkGraph F(E,s);
183 F.possibleExternalFaces(externalFaces);
184
185 return !externalFaces.empty();
186 }
187
188
upwardPlanarAugment_singleSource_embedded(Graph & G,node & superSink,SList<edge> & augmentedEdges)189 bool UpwardPlanarity::upwardPlanarAugment_singleSource_embedded(
190 Graph &G,
191 node &superSink,
192 SList<edge> &augmentedEdges)
193 {
194 OGDF_ASSERT(G.representsCombEmbedding());
195
196 // trivial cases
197 if(G.empty())
198 return true;
199
200 if(!isAcyclic(G))
201 return false;
202
203 // determine the single source in G
204 node s;
205 if(!hasSingleSource(G,s))
206 return false;
207
208 // construct embedding represented by G and face-sink graph
209 ConstCombinatorialEmbedding E(G);
210 FaceSinkGraph F(E,s);
211
212 // find possible external faces
213 SList<face> externalFaces;
214 F.possibleExternalFaces(externalFaces);
215
216 if (externalFaces.empty())
217 return false;
218
219 else {
220 F.stAugmentation(F.faceNodeOf(externalFaces.front()), G, superSink, augmentedEdges);
221 return true;
222 }
223 }
224
225 }
226