r798:58c330ad0b5c
Sun, 04 Oct 2009 10:15:32
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -139,12 +139,2 @@ |
| 139 | 139 |
|
| 140 |
} |
|
| 141 |
|
|
| 142 |
/// \ingroup planar |
|
| 143 |
/// |
|
| 144 |
/// \brief Planarity checking of an undirected simple graph |
|
| 145 |
/// |
|
| 146 |
/// This class implements the Boyer-Myrvold algorithm for planarity |
|
| 147 |
/// checking of an undirected graph. This class is a simplified |
|
| 148 |
/// version of the PlanarEmbedding algorithm class because neither |
|
| 149 |
/// the embedding nor the kuratowski subdivisons are not computed. |
|
| 150 | 140 |
template <typename Graph> |
| ... | ... |
@@ -181,12 +171,4 @@ |
| 181 | 171 |
|
| 182 |
/// \brief Constructor |
|
| 183 |
/// |
|
| 184 |
/// \note The graph should be simple, i.e. parallel and loop arc |
|
| 185 |
/// free. |
|
| 186 | 172 |
PlanarityChecking(const Graph& graph) : _graph(graph) {}
|
| 187 | 173 |
|
| 188 |
/// \brief Runs the algorithm. |
|
| 189 |
/// |
|
| 190 |
/// Runs the algorithm. |
|
| 191 |
/// \return %True when the graph is planar. |
|
| 192 | 174 |
bool run() {
|
| ... | ... |
@@ -241,3 +223,4 @@ |
| 241 | 223 |
for (typename MergeRoots::Value::iterator it = |
| 242 |
merge_roots[node].begin(); |
|
| 224 |
merge_roots[node].begin(); |
|
| 225 |
it != merge_roots[node].end(); ++it) {
|
|
| 243 | 226 |
int rn = *it; |
| ... | ... |
@@ -451,3 +434,4 @@ |
| 451 | 434 |
bool rd; |
| 452 |
if (!external(xnode, rorder, child_lists, |
|
| 435 |
if (!external(xnode, rorder, child_lists, |
|
| 436 |
ancestor_map, low_map)) {
|
|
| 453 | 437 |
rd = true; |
| ... | ... |
@@ -529,2 +513,18 @@ |
| 529 | 513 |
|
| 514 |
} |
|
| 515 |
|
|
| 516 |
/// \ingroup planar |
|
| 517 |
/// |
|
| 518 |
/// \brief Planarity checking of an undirected simple graph |
|
| 519 |
/// |
|
| 520 |
/// This function implements the Boyer-Myrvold algorithm for |
|
| 521 |
/// planarity checking of an undirected graph. It is a simplified |
|
| 522 |
/// version of the PlanarEmbedding algorithm class because neither |
|
| 523 |
/// the embedding nor the kuratowski subdivisons are not computed. |
|
| 524 |
template <typename GR> |
|
| 525 |
bool checkPlanarity(const GR& graph) {
|
|
| 526 |
_planarity_bits::PlanarityChecking<GR> pc(graph); |
|
| 527 |
return pc.run(); |
|
| 528 |
} |
|
| 529 |
|
|
| 530 | 530 |
/// \ingroup planar |
| ... | ... |
@@ -714,3 +714,3 @@ |
| 714 | 714 |
/// graph. |
| 715 |
const EmbeddingMap& |
|
| 715 |
const EmbeddingMap& embeddingMap() const {
|
|
| 716 | 716 |
return _embedding; |
| ... | ... |
@@ -241,3 +241,6 @@ |
| 241 | 241 |
PE pe(graph); |
| 242 |
|
|
| 242 |
bool planar = pe.run(); |
|
| 243 |
check(checkPlanarity(graph) == planar, "Planarity checking failed"); |
|
| 244 |
|
|
| 245 |
if (planar) {
|
|
| 243 | 246 |
checkEmbedding(graph, pe); |
| ... | ... |
@@ -245,3 +248,3 @@ |
| 245 | 248 |
PlanarDrawing<Graph> pd(graph); |
| 246 |
pd.run(pe. |
|
| 249 |
pd.run(pe.embeddingMap()); |
|
| 247 | 250 |
checkDrawing(graph, pd); |
| ... | ... |
@@ -249,3 +252,3 @@ |
| 249 | 252 |
PlanarColoring<Graph> pc(graph); |
| 250 |
pc.runFiveColoring(pe. |
|
| 253 |
pc.runFiveColoring(pe.embeddingMap()); |
|
| 251 | 254 |
checkColoring(graph, pc, 5); |
0 comments (0 inline)