Planar drawing algorithm now works for less than 3 nodes (#611)
authorBalazs Dezso <deba@google.com>
Wed, 17 Oct 2018 17:52:11 +0200
changeset 11826b79d93e812f
parent 1181 1e5da3fc4fbc
child 1184 3c00344f49c9
Planar drawing algorithm now works for less than 3 nodes (#611)
lemon/planarity.h
test/planarity_test.cc
     1.1 --- a/lemon/planarity.h	Tue May 15 14:16:35 2018 +0200
     1.2 +++ b/lemon/planarity.h	Wed Oct 17 17:52:11 2018 +0200
     1.3 @@ -2398,6 +2398,15 @@
     1.4      void run(const EmbeddingMap& embedding) {
     1.5        typedef SmartEdgeSet<Graph> AuxGraph;
     1.6  
     1.7 +      if (countNodes(_graph) < 3) {
     1.8 +        int y = 0;
     1.9 +        for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
    1.10 +          _point_map[n].x = 0;
    1.11 +          _point_map[n].y = y++;
    1.12 +        }
    1.13 +        return;
    1.14 +      }
    1.15 +
    1.16        if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {
    1.17          drawing(_graph, embedding, _point_map);
    1.18          return;
     2.1 --- a/test/planarity_test.cc	Tue May 15 14:16:35 2018 +0200
     2.2 +++ b/test/planarity_test.cc	Wed Oct 17 17:52:11 2018 +0200
     2.3 @@ -30,10 +30,40 @@
     2.4  using namespace lemon;
     2.5  using namespace lemon::dim2;
     2.6  
     2.7 -const int lgfn = 4;
     2.8 +const int lgfn = 8;
     2.9  const std::string lgf[lgfn] = {
    2.10    "@nodes\n"
    2.11    "label\n"
    2.12 +  "@edges\n"
    2.13 +  "     label\n",
    2.14 +
    2.15 +  "@nodes\n"
    2.16 +  "label\n"
    2.17 +  "0\n"
    2.18 +  "@edges\n"
    2.19 +  "     label\n",
    2.20 +
    2.21 +  "@nodes\n"
    2.22 +  "label\n"
    2.23 +  "0\n"
    2.24 +  "1\n"
    2.25 +  "@edges\n"
    2.26 +  "     label\n"
    2.27 +  "0 1  0\n",
    2.28 +
    2.29 +  "@nodes\n"
    2.30 +  "label\n"
    2.31 +  "0\n"
    2.32 +  "1\n"
    2.33 +  "2\n"
    2.34 +  "@edges\n"
    2.35 +  "     label\n"
    2.36 +  "0 1  0\n"
    2.37 +  "1 2  1\n"
    2.38 +  "2 0  2\n",
    2.39 +
    2.40 +  "@nodes\n"
    2.41 +  "label\n"
    2.42    "0\n"
    2.43    "1\n"
    2.44    "2\n"
    2.45 @@ -136,8 +166,11 @@
    2.46        ++face_num;
    2.47      }
    2.48    }
    2.49 -  check(face_num + countNodes(graph) - countConnectedComponents(graph) ==
    2.50 -        countEdges(graph) + 1, "Euler test does not passed");
    2.51 +
    2.52 +  if (face_num != 0) {
    2.53 +    check(face_num + countNodes(graph) - countConnectedComponents(graph) ==
    2.54 +          countEdges(graph) + 1, "Euler test does not passed");
    2.55 +  }
    2.56  }
    2.57  
    2.58  void checkKuratowski(const Graph& graph, PE& pe) {