test/planarity_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 11 Jan 2012 14:12:36 +0100
changeset 974 b1744d7bdb47
parent 797 30cb42e3e43a
child 1181 1e5da3fc4fbc
permissions -rw-r--r--
Merge LP interface updates
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 
    21 #include <lemon/planarity.h>
    22 
    23 #include <lemon/smart_graph.h>
    24 #include <lemon/lgf_reader.h>
    25 #include <lemon/connectivity.h>
    26 #include <lemon/dim2.h>
    27 
    28 #include "test_tools.h"
    29 
    30 using namespace lemon;
    31 using namespace lemon::dim2;
    32 
    33 const int lgfn = 4;
    34 const std::string lgf[lgfn] = {
    35   "@nodes\n"
    36   "label\n"
    37   "0\n"
    38   "1\n"
    39   "2\n"
    40   "3\n"
    41   "4\n"
    42   "@edges\n"
    43   "     label\n"
    44   "0 1  0\n"
    45   "0 2  0\n"
    46   "0 3  0\n"
    47   "0 4  0\n"
    48   "1 2  0\n"
    49   "1 3  0\n"
    50   "1 4  0\n"
    51   "2 3  0\n"
    52   "2 4  0\n"
    53   "3 4  0\n",
    54 
    55   "@nodes\n"
    56   "label\n"
    57   "0\n"
    58   "1\n"
    59   "2\n"
    60   "3\n"
    61   "4\n"
    62   "@edges\n"
    63   "     label\n"
    64   "0 1  0\n"
    65   "0 2  0\n"
    66   "0 3  0\n"
    67   "0 4  0\n"
    68   "1 2  0\n"
    69   "1 3  0\n"
    70   "2 3  0\n"
    71   "2 4  0\n"
    72   "3 4  0\n",
    73 
    74   "@nodes\n"
    75   "label\n"
    76   "0\n"
    77   "1\n"
    78   "2\n"
    79   "3\n"
    80   "4\n"
    81   "5\n"
    82   "@edges\n"
    83   "     label\n"
    84   "0 3  0\n"
    85   "0 4  0\n"
    86   "0 5  0\n"
    87   "1 3  0\n"
    88   "1 4  0\n"
    89   "1 5  0\n"
    90   "2 3  0\n"
    91   "2 4  0\n"
    92   "2 5  0\n",
    93 
    94   "@nodes\n"
    95   "label\n"
    96   "0\n"
    97   "1\n"
    98   "2\n"
    99   "3\n"
   100   "4\n"
   101   "5\n"
   102   "@edges\n"
   103   "     label\n"
   104   "0 3  0\n"
   105   "0 4  0\n"
   106   "0 5  0\n"
   107   "1 3  0\n"
   108   "1 4  0\n"
   109   "1 5  0\n"
   110   "2 3  0\n"
   111   "2 5  0\n"
   112 };
   113 
   114 
   115 
   116 typedef SmartGraph Graph;
   117 GRAPH_TYPEDEFS(Graph);
   118 
   119 typedef PlanarEmbedding<SmartGraph> PE;
   120 typedef PlanarDrawing<SmartGraph> PD;
   121 typedef PlanarColoring<SmartGraph> PC;
   122 
   123 void checkEmbedding(const Graph& graph, PE& pe) {
   124   int face_num = 0;
   125 
   126   Graph::ArcMap<int> face(graph, -1);
   127 
   128   for (ArcIt a(graph); a != INVALID; ++a) {
   129     if (face[a] == -1) {
   130       Arc b = a;
   131       while (face[b] == -1) {
   132         face[b] = face_num;
   133         b = pe.next(graph.oppositeArc(b));
   134       }
   135       check(face[b] == face_num, "Wrong face");
   136       ++face_num;
   137     }
   138   }
   139   check(face_num + countNodes(graph) - countConnectedComponents(graph) ==
   140         countEdges(graph) + 1, "Euler test does not passed");
   141 }
   142 
   143 void checkKuratowski(const Graph& graph, PE& pe) {
   144   std::map<int, int> degs;
   145   for (NodeIt n(graph); n != INVALID; ++n) {
   146     int deg = 0;
   147     for (IncEdgeIt e(graph, n); e != INVALID; ++e) {
   148       if (pe.kuratowski(e)) {
   149         ++deg;
   150       }
   151     }
   152     ++degs[deg];
   153   }
   154   for (std::map<int, int>::iterator it = degs.begin(); it != degs.end(); ++it) {
   155     check(it->first == 0 || it->first == 2 ||
   156           (it->first == 3 && it->second == 6) ||
   157           (it->first == 4 && it->second == 5),
   158           "Wrong degree in Kuratowski graph");
   159   }
   160 
   161   // Not full test
   162   check((degs[3] == 0) != (degs[4] == 0), "Wrong Kuratowski graph");
   163 }
   164 
   165 bool intersect(Point<int> e1, Point<int> e2, Point<int> f1, Point<int> f2) {
   166   int l, r;
   167   if (std::min(e1.x, e2.x) > std::max(f1.x, f2.x)) return false;
   168   if (std::max(e1.x, e2.x) < std::min(f1.x, f2.x)) return false;
   169   if (std::min(e1.y, e2.y) > std::max(f1.y, f2.y)) return false;
   170   if (std::max(e1.y, e2.y) < std::min(f1.y, f2.y)) return false;
   171 
   172   l = (e2.x - e1.x) * (f1.y - e1.y) - (e2.y - e1.y) * (f1.x - e1.x);
   173   r = (e2.x - e1.x) * (f2.y - e1.y) - (e2.y - e1.y) * (f2.x - e1.x);
   174   if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false;
   175   l = (f2.x - f1.x) * (e1.y - f1.y) - (f2.y - f1.y) * (e1.x - f1.x);
   176   r = (f2.x - f1.x) * (e2.y - f1.y) - (f2.y - f1.y) * (e2.x - f1.x);
   177   if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false;
   178   return true;
   179 }
   180 
   181 bool collinear(Point<int> p, Point<int> q, Point<int> r) {
   182   int v;
   183   v = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
   184   if (v != 0) return false;
   185   v = (q.x - p.x) * (r.x - p.x) + (q.y - p.y) * (r.y - p.y);
   186   if (v < 0) return false;
   187   return true;
   188 }
   189 
   190 void checkDrawing(const Graph& graph, PD& pd) {
   191   for (Graph::NodeIt n(graph); n != INVALID; ++n) {
   192     Graph::NodeIt m(n);
   193     for (++m; m != INVALID; ++m) {
   194       check(pd[m] != pd[n], "Two nodes with identical coordinates");
   195     }
   196   }
   197 
   198   for (Graph::EdgeIt e(graph); e != INVALID; ++e) {
   199     for (Graph::EdgeIt f(e); f != e; ++f) {
   200       Point<int> e1 = pd[graph.u(e)];
   201       Point<int> e2 = pd[graph.v(e)];
   202       Point<int> f1 = pd[graph.u(f)];
   203       Point<int> f2 = pd[graph.v(f)];
   204 
   205       if (graph.u(e) == graph.u(f)) {
   206         check(!collinear(e1, e2, f2), "Wrong drawing");
   207       } else if (graph.u(e) == graph.v(f)) {
   208         check(!collinear(e1, e2, f1), "Wrong drawing");
   209       } else if (graph.v(e) == graph.u(f)) {
   210         check(!collinear(e2, e1, f2), "Wrong drawing");
   211       } else if (graph.v(e) == graph.v(f)) {
   212         check(!collinear(e2, e1, f1), "Wrong drawing");
   213       } else {
   214         check(!intersect(e1, e2, f1, f2), "Wrong drawing");
   215       }
   216     }
   217   }
   218 }
   219 
   220 void checkColoring(const Graph& graph, PC& pc, int num) {
   221   for (NodeIt n(graph); n != INVALID; ++n) {
   222     check(pc.colorIndex(n) >= 0 && pc.colorIndex(n) < num,
   223           "Wrong coloring");
   224   }
   225   for (EdgeIt e(graph); e != INVALID; ++e) {
   226     check(pc.colorIndex(graph.u(e)) != pc.colorIndex(graph.v(e)),
   227           "Wrong coloring");
   228   }
   229 }
   230 
   231 int main() {
   232 
   233   for (int i = 0; i < lgfn; ++i) {
   234     std::istringstream lgfs(lgf[i]);
   235 
   236     SmartGraph graph;
   237     graphReader(graph, lgfs).run();
   238 
   239     check(simpleGraph(graph), "Test graphs must be simple");
   240 
   241     PE pe(graph);
   242     bool planar = pe.run();
   243     check(checkPlanarity(graph) == planar, "Planarity checking failed");
   244 
   245     if (planar) {
   246       checkEmbedding(graph, pe);
   247 
   248       PlanarDrawing<Graph> pd(graph);
   249       pd.run(pe.embeddingMap());
   250       checkDrawing(graph, pd);
   251 
   252       PlanarColoring<Graph> pc(graph);
   253       pc.runFiveColoring(pe.embeddingMap());
   254       checkColoring(graph, pc, 5);
   255 
   256     } else {
   257       checkKuratowski(graph, pe);
   258     }
   259   }
   260 
   261   return 0;
   262 }