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