r798:58c330ad0b5c
Sun, 04 Oct 2009 10:15:32
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -137,16 +137,6 @@ |
| 137 | 137 |
typename Graph::Arc prev, next; |
| 138 | 138 |
}; |
| 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> |
| 151 | 141 |
class PlanarityChecking {
|
| 152 | 142 |
private: |
| ... | ... |
@@ -179,16 +169,8 @@ |
| 179 | 169 |
|
| 180 | 170 |
public: |
| 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() {
|
| 193 | 175 |
typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; |
| 194 | 176 |
|
| ... | ... |
@@ -239,7 +221,8 @@ |
| 239 | 221 |
} |
| 240 | 222 |
|
| 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; |
| 244 | 227 |
walkDown(rn, i, node_data, order_list, child_lists, |
| 245 | 228 |
ancestor_map, low_map, embed_arc, merge_roots); |
| ... | ... |
@@ -449,7 +432,8 @@ |
| 449 | 432 |
Node ynode = order_list[yn]; |
| 450 | 433 |
|
| 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; |
| 454 | 438 |
} else if (!external(ynode, rorder, child_lists, |
| 455 | 439 |
ancestor_map, low_map)) {
|
| ... | ... |
@@ -527,6 +511,22 @@ |
| 527 | 511 |
|
| 528 | 512 |
}; |
| 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 |
| 531 | 531 |
/// |
| 532 | 532 |
/// \brief Planar embedding of an undirected simple graph |
| ... | ... |
@@ -712,7 +712,7 @@ |
| 712 | 712 |
/// |
| 713 | 713 |
/// The returned map contains the successor of each arc in the |
| 714 | 714 |
/// graph. |
| 715 |
const EmbeddingMap& |
|
| 715 |
const EmbeddingMap& embeddingMap() const {
|
|
| 716 | 716 |
return _embedding; |
| 717 | 717 |
} |
| 718 | 718 |
| ... | ... |
@@ -239,15 +239,18 @@ |
| 239 | 239 |
check(simpleGraph(graph), "Test graphs must be simple"); |
| 240 | 240 |
|
| 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); |
| 244 | 247 |
|
| 245 | 248 |
PlanarDrawing<Graph> pd(graph); |
| 246 |
pd.run(pe. |
|
| 249 |
pd.run(pe.embeddingMap()); |
|
| 247 | 250 |
checkDrawing(graph, pd); |
| 248 | 251 |
|
| 249 | 252 |
PlanarColoring<Graph> pc(graph); |
| 250 |
pc.runFiveColoring(pe. |
|
| 253 |
pc.runFiveColoring(pe.embeddingMap()); |
|
| 251 | 254 |
checkColoring(graph, pc, 5); |
| 252 | 255 |
|
| 253 | 256 |
} else {
|
0 comments (0 inline)