Implementing a planar graph type

[gyorokp]

My goal is to implement classes for planar graphs. The PlanarGraph class maintains a topology of nodes, edges and faces and provides algorithms that are characteristic to planar graphs. PlaneGraph extends this functionality with geometric properties, such as node coordinates and arc shapes.

[Alpar Juttner]

Nice proposal. I'll try to have a deeper look at it soon. Do you have an example code that actually uses these tool?

[gyorokp]

No real applications yet, only a few tests to show that the features are working. More complex examples may come up later during the project.

[gyorokp]

Basic tests of features

[Alpar Juttner]

Unfortunately, trac will not send an email notification if you just add a new attachment to a ticket.

Thus please always add a short (but separate) comment whenever you upload an attachment so that it won't remain hidden.

[gyorokp]

Please disregard all the previous patches except this new one. The project is now complete and this patch contains all of it.

[Peter Kovacs]

I had a short look at these proposal. It seems to be a remarkable result of a hard work. It is also well documented and well tested. Well done! I would prefer to incude these tools in the release 1.3.

Several small suggestions and questions:

• graph_to_eps.h
  • inner_run() should be renamed to innerRun() or start() or execute() etc. I would prefer start() similarly to algorithms.
  • inner_run() and edgeToEps() should be private or protected, not public.
  • It seems to be strange (and maybe "dangerous" in a sense) to overload the run() function based on int vs. bool distinction, because in C++, an int can be reagarded as a bool value and vice versa. What do these parameters mean in case of standard and planar graphs?
  • GraphToEps could check if the underlying graph is planar or not. Would it be better to make the above distinction according to this? Do we want to support the standard drawing of a planar graph and/or the special drawing of a non-planar graph type (which could store a planar graph)?

• planar_graph.h
  • I like the solution of introducing Face as a new item type in graphs (just like Node, Arc and Edge) and implementing FaceIt, FaceMap and the other iterator classes.
  • We could introduce a concept class for planar graphs (concepts::PlanarGraph), but I don't know whether it is worth to do or not. However, I suggest introducing PlanarGraphTag to indicate whether a graph type is palanar or not.
  • If this is the final version, we don't need an "UNDER CONSTRUCTION" warning in the Doxygen doc. :) And the REMOVE_BEFORE_RELEASE parts should also be removed.
  • link_node(), unlink_node(), link_edge(), unlink_edge(), inner_split(), inner_contract(), wall_paint(), component_relabel() functions should be renamed according to the code conventions (linkNode(), linkEdge(), etc.)
  • CcwArcIt should be renamed to CcwBoundaryArcIt (just like its pair CwBoundaryArcIt).
  • "anticlockwise" should be replaced by "counter clockwise" everywhere.
  • "A disconnected planar graph has have an outer face for each of its components" I think, "has have" should be "has".
  • The third constructor of PlanarGraph() should also be documented.
  • edge_add_notify() and edge_erase_notify() should be renamed.
  • changeU() and changeV() are introduced in PlanarGraph, but they declared as unsupported operations. In this case, they could simply be left out, because they are not the part of the Graph concept.
  • For reserveXyz() functions, the \sa notes should be fixed. Each of the three functions should refer to the other two, or you could simply remove these links (I don't think they are important). (Note that reserveFace() currently refers to itself.)
  • Subclasses DualBase and ExtendedDualBase should not be public.
  • The doc of Dual should be extended. It should contain that a dual graph can be used exactly the same way as the original graph. (Both of them coform to he concepts::PlanarGraph concept - if it will be introduced.) Moreover, it could note that the original Node type is the same as the dual's Face and vice versa, and the Edge types of the two graph types are the same.
  • The indentation of the doc and the definition of Dual should be increased by two spaces.

• plane_graph.h
  • Apply all the relevant changes to this file from those that are suggested above. E.g. remove "UNDER CONSTRUCTION" and "REMOVE_BEFORE_RELEASE" parts.
  • The third constructor of PlaneGraph() should also be documented.
  • The doc lines of some functions are duplicated (nodePosMap(), locate()).
  • PlaneGraph has CwBoundaryIt and CcwBoundaryIt. Are they the same as CwBoundaryArcIt and CcwBoundaryArcIt of PlanarGraph (supposing the the latter one is renamed to this form, see above)? If yes then why are they redefined? Consistent naming should be used!
  • It would be slightly better if CwIncIt would be defined before CcwIncIt to ensure consistent order of cw and ccw everywhere.
  • Some Doxygen documentations are in wrong format (e.g. CcwIncIt, CwIncIt):

      /// Brief doc
        
      /// Full doc
      something
    

    In this case, the "Full doc" will be considered as brief doc, and the first doc line will simply be skipped. You should use one the following forms:

      /// Brief doc
        
      /// Full doc
      ///
      something
    

    or:

      /// \brief Brief doc
      ///
      /// Full doc
      something
    

  • If you have a nice EPS file of a planar graph, then it could be included in the doc of this class.

• planar_graph_test.h
  • LEMON_TEST_GRAPH_TEST_H should be LEMON_TEST_PLANAR_GRAPH_TEST_H.
  • I think, this file should include graph_test.h (which requires the above modification) and the common functions (e.g. checkGraphNodeList()) should be removed from this file. (Or the functions in this header file could call the old functions.) I would prefer to see only the new things in this header file compared to the standard graphs.
  • checkGraphBoundaryArcList() should check CcwBoundaryArcIt as well as CwBoundaryArcIt. This extension would reveal the incosistent naming of these functions (see above).

• planar_graph_test.cc
  • It is a detailed test file, I like it. However, some additional tests could be included in it. E.g. the testing of the dual planar graph would be quite important. The different edge shapes of PlaneGraph should also be checked.

[gyorokp]

New patch should be applied to the previous one (ea56aa8243b1) which in turn should be applied to revision 87569cb5734d.

*graph_to_eps.h: The only reason this file was modified is that PlaneGraph? supports graphs with custom edge shapes, but this is the only graph type to do so. One alternative is to add support in graphToEps to draw any graph with custom edge shapes, the other is to delegate the custom edge drawing to the graph type. Since this falls outside the scope of this thesis, I used the second option. However, simply inserting a call to GR::edgeToEps() wouldn't work as it would create a compilation error in normal graphs. A rudimentary solution was to make 2 separate functions named edgeToEps, one which calls the function in the graph type and the other does nothing. The extra template parameter serves to distinguish between the two. This is also why "inner_run()" (now renamed to start()) was split out of run(), since the two versions of run() would share almost all of the code except that single parameter. The choices of int and bool for parameter types are just as arbitrary as using int in T::operator++(int). The version that runs on normal graphs has a default value so existing code calling run() with no parameters will still work, while plane graphs will need the bool parameter. The convertibility between int and bool shouldn't be a problem since the user should put "true" or "false" in that parameter anyway.

*planar_graph.h:

There were no naming inconsistencies, actually a few iterators from that "family" were missing, now they have been fixed.

"REMOVE_BEFORE_RELEASE" is staying until its removal is the only thing left to do. The print() function is invaluable for debugging.

*plane_graph.h:

These iterators aren't exactly the same as the ones in PlanarGraph?. They have an extra dereference operator that returns the edge shape associated with the arcs. The names are changed to suggest that these iterators aren't for dealing with arcs specifically, since we do have the proper iterators for that in PlanarGraph?. So CcwOutArcIt/CcwInArcIt? becomes CcwIncIt?, CcwBoundaryArcIt? becomes CcwBoundaryIt? etc.

Images: the modified graph_to_eps can create EPS files. However, I'm not that experienced with Doxygen so I don't know how to include them and where they should be placed in the repository.

[Dave]

I am not sure what the status is on this patch... and to be very honest, I have not even been able to track down the branch it belongs to in the code repository: ended up manually patching the current tip and including the new headers in my project. While doing so, I have found a bug that might be worth fixing.

In plane_graph.h:

  template<typename Point>
  struct LexicographicPointOrdering {
    bool operator()(const Point &p1, const Point &p2) {
      return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
    }
  };

3rd line's definition should be:

    bool operator()(const Point &p1, const Point &p2) const

Otherwise std::map complains about not finding the operator.

Sorry about not submitting a patch file, but I had to make many other small modifications in order to make the file work outside of the actual branch.