RhodeCode

%!PS-Adobe-2.0 EPSF-2.0

%%Creator: LEMON, graphToEps()

%%CreationDate: Fri Oct 19 18:32:32 2007

%%BoundingBox: 0 0 596 842

%%DocumentPaperSizes: a4

%%EndComments

/lb { setlinewidth setrgbcolor newpath moveto

      4 2 roll 1 index 1 index curveto stroke } bind def

/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def

/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def

/sq { newpath 2 index 1 index add 2 index 2 index add moveto

      2 index 1 index sub 2 index 2 index add lineto

      2 index 1 index sub 2 index 2 index sub lineto

      2 index 1 index add 2 index 2 index sub lineto

      closepath pop pop pop} bind def

/di { newpath 2 index 1 index add 2 index moveto

      2 index             2 index 2 index add lineto

      2 index 1 index sub 2 index             lineto

      2 index             2 index 2 index sub lineto

      closepath pop pop pop} bind def

/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill

     setrgbcolor 1.1 div c fill

   } bind def

/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill

     setrgbcolor 1.1 div sq fill

   } bind def

/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill

     setrgbcolor 1.1 div di fill

   } bind def

/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth

  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub

  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto

  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke

  5 index 5 index 5 index c fill

  setrgbcolor 1.1 div c fill

  } bind def

/nmale {

  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth

  newpath 5 index 5 index moveto

  5 index 4 index 1 mul 1.5 mul add

  5 index 5 index 3 sqrt 1.5 mul mul add

  1 index 1 index lineto

  1 index 1 index 7 index sub moveto

  1 index 1 index lineto

  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto

  stroke

  5 index 5 index 5 index c fill

  setrgbcolor 1.1 div c fill

  } bind def

/arrl 1 def

/arrw 0.3 def

/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def

/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def

       /w exch def /len exch def

       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto

       len w sub arrl sub dx dy lrl

       arrw dy dx neg lrl

       dx arrl w add mul dy w 2 div arrw add mul sub

       dy arrl w add mul dx w 2 div arrw add mul add rlineto

       dx arrl w add mul neg dy w 2 div arrw add mul sub

       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto

       arrw dy dx neg lrl

       len w sub arrl sub neg dx dy lrl

       closepath fill } bind def

/cshow { 2 index 2 index moveto dup stringwidth pop

         neg 2 div fosi .35 mul neg rmoveto show pop pop} def

gsave

15 138.307 translate

12.7843 dup scale

90 rotate

0.608112 -43.6081 translate

%Edges:

gsave

9 31 9.5 30.5 10 30 0 0 0 0.091217 lb

9 31 5.5 34.5 2 38 0 0 0 0.091217 lb

9 31 25.5 16 42 1 0 0 0 0.091217 lb

3 40 23 20.5 43 1 0 0 0 0.091217 lb

3 40 22.5 20.5 42 1 0 0 0 0.091217 lb

3 40 2.5 40.5 2 41 0 0 0 0.091217 lb

13 25 10.5 24.5 8 24 0 0 0 0.091217 lb

13 25 12 27 11 29 0 0 0 0.091217 lb

3 4 2.5 3 2 2 0 0 0 0.091217 lb

3 4 4.5 3 6 2 0 0 0 0.091217 lb

6 25 7 24.5 8 24 0 0 0 0.091217 lb

6 25 6 24.5 6 24 0 0 0 0.091217 lb

34 2 33.5 2 33 2 0 0 0 0.091217 lb

34 2 35 2 36 2 0 0 0 0.091217 lb

6 8 16 9 26 10 0 0 0 0.091217 lb

6 8 6 10.5 6 13 0 0 0 0.091217 lb

6 8 6 7.5 6 7 0 0 0 0.091217 lb

26 10 27.5 8.5 29 7 0 0 0 0.091217 lb

26 10 27.5 9 29 8 0 0 0 0.091217 lb

10 30 10.5 29.5 11 29 0 0 0 0.091217 lb

8 24 7 23.5 6 23 0 0 0 0.091217 lb

8 24 8 24.5 8 25 0 0 0 0.091217 lb

33 2 32.5 2 32 2 0 0 0 0.091217 lb

29 7 17.5 7 6 7 0 0 0 0.091217 lb

2 2 1.5 22 1 42 0 0 0 0.091217 lb

2 2 3.5 2 5 2 0 0 0 0.091217 lb

21 15 13.5 14.5 6 14 0 0 0 0.091217 lb

21 15 21 15.5 21 16 0 0 0 0.091217 lb

1 42 0.5 42.5 0 43 0 0 0 0.091217 lb

1 42 1.5 41.5 2 41 0 0 0 0.091217 lb

6 15 6 15.5 6 16 0 0 0 0.091217 lb

6 15 6 14.5 6 14 0 0 0 0.091217 lb

43 1 22 0.5 1 0 0 0 0 0.091217 lb

31 2 18.5 2 6 2 0 0 0 0.091217 lb

31 2 31.5 2 32 2 0 0 0 0.091217 lb

6 24 6 23.5 6 23 0 0 0 0.091217 lb

6 16 6 16.5 6 17 0 0 0 0.091217 lb

6 23 6 20 6 17 0 0 0 0.091217 lb

6 2 5.5 2 5 2 0 0 0 0.091217 lb

6 2 6 4.5 6 7 0 0 0 0.091217 lb

0 43 0.5 21.5 1 0 0 0 0 0.091217 lb

1 1 19.5 1.5 38 2 0 0 0 0.091217 lb

1 1 1 0.5 1 0 0 0 0 0.091217 lb

2 38 5.5 31.5 9 25 0 0 0 0.091217 lb

25 13 15.5 13 6 13 0 0 0 0.091217 lb

25 13 15.5 13.5 6 14 0 0 0 0.091217 lb

8 25 8.5 25 9 25 0 0 0 0.091217 lb

11 29 24.5 15.5 38 2 0 0 0 0.091217 lb

6 17 11.5 18 17 19 0 0 0 0.091217 lb

16 23 26.5 12.5 37 2 0 0 0 0.091217 lb

16 23 18.5 19.5 21 16 0 0 0 0.091217 lb

36 2 36.5 2 37 2 0 0 0 0.091217 lb

36 2 32.5 5 29 8 0 0 0 0.091217 lb

6 13 6 13.5 6 14 0 0 0 0.091217 lb

37 2 37.5 2 38 2 0 0 0 0.091217 lb

21 16 19 17.5 17 19 0 0 0 0.091217 lb

grestore

%Nodes:

gsave

29 8 0.304556 1 1 1 nc

2 41 0.304556 1 1 1 nc

6 7 0.304556 1 1 1 nc

5 2 0.304556 1 1 1 nc

17 19 0.304556 1 1 1 nc

21 16 0.304556 1 1 1 nc

1 0 0.304556 1 1 1 nc

9 25 0.304556 1 1 1 nc

6 14 0.304556 1 1 1 nc

42 1 0.304556 1 1 1 nc

38 2 0.304556 1 1 1 nc

37 2 0.304556 1 1 1 nc

6 13 0.304556 1 1 1 nc

36 2 0.304556 1 1 1 nc

16 23 0.304556 1 1 1 nc

6 17 0.304556 1 1 1 nc

11 29 0.304556 1 1 1 nc

8 25 0.304556 1 1 1 nc

32 2 0.304556 1 1 1 nc

25 13 0.304556 1 1 1 nc

2 38 0.304556 1 1 1 nc

1 1 0.304556 1 1 1 nc

0 43 0.304556 1 1 1 nc

6 2 0.304556 1 1 1 nc

6 23 0.304556 1 1 1 nc

6 16 0.304556 1 1 1 nc

6 24 0.304556 1 1 1 nc

31 2 0.304556 1 1 1 nc

43 1 0.304556 1 1 1 nc

6 15 0.304556 1 1 1 nc

1 42 0.304556 1 1 1 nc

21 15 0.304556 1 1 1 nc

2 2 0.304556 1 1 1 nc

29 7 0.304556 1 1 1 nc

33 2 0.304556 1 1 1 nc

8 24 0.304556 1 1 1 nc

10 30 0.304556 1 1 1 nc

26 10 0.304556 1 1 1 nc

6 8 0.304556 1 1 1 nc

34 2 0.304556 1 1 1 nc

6 25 0.304556 1 1 1 nc

3 4 0.304556 1 1 1 nc

13 25 0.304556 1 1 1 nc

3 40 0.304556 1 1 1 nc

9 31 0.304556 1 1 1 nc

grestore

grestore

showpage

Makefile Variables

==================

Some Makefile variables are reserved by the GNU Coding Standards for

the use of the "user" - the person building the package. For instance,

CXX and CXXFLAGS are such variables, and have the same meaning as

explained in the previous section. These variables can be set on the

command line when invoking `make' like this:

`make [VARIABLE=VALUE]...'

WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us

to hold several compiler flags related to warnings. Its default value

can be overridden when invoking `make'. For example to disable all

warning flags use `make WARNINGCXXFLAGS='.

In order to turn off a single flag from the default set of warning

flags, you can use the CXXFLAGS variable, since this is passed after

WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is

used by default when g++ is detected) you can use

`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps

	planar.eps \

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref BellmanFordDefaultTraits

  /// "BellmanFordDefaultTraits<GR, LEN>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  ///

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm.

  ///\tparam TR The traits class that defines various types used by the

  ///algorithm. By default, it is \ref BfsDefaultTraits

  ///"BfsDefaultTraits<GR>".

  ///In most cases, this parameter should not be set directly,

  ///consider to use the named template parameters instead.

  ///

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref BfsVisitDefaultTraits

  /// "BfsVisitDefaultTraits<GR>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  /// and supply values in the algorithm. By default, it is \c int.

  /// algorithm. By default, it is the same as \c V.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits

  /// "CapacityScalingDefaultTraits<GR, V, C>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

     \tparam TR The traits class that defines various types used by the

     algorithm. By default, it is \ref CirculationDefaultTraits

     "CirculationDefaultTraits<GR, LM, UM, SM>".

     In most cases, this parameter should not be set directly,

     consider to use the named template parameters instead.

  /// and supply values in the algorithm. By default, it is \c int.

  /// algorithm. By default, it is the same as \c V.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref CostScalingDefaultTraits

  /// "CostScalingDefaultTraits<GR, V, C>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

    /// By default, it is \c long \c long if the \c Cost type is integer,

  ///\tparam TR The traits class that defines various types used by the

  ///algorithm. By default, it is \ref DfsDefaultTraits

  ///"DfsDefaultTraits<GR>".

  ///In most cases, this parameter should not be set directly,

  ///consider to use the named template parameters instead.

  ///

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref DfsVisitDefaultTraits

  /// "DfsVisitDefaultTraits<GR>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  ///\tparam TR The traits class that defines various types used by the

  ///algorithm. By default, it is \ref DijkstraDefaultTraits

  ///"DijkstraDefaultTraits<GR, LEN>".

  ///In most cases, this parameter should not be set directly,

  ///consider to use the named template parameters instead.

  ///

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits

  /// "HartmannOrlinDefaultTraits<GR, LEN>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

    /// By default, it is \c long \c long if the \c Value type is integer,

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref HowardDefaultTraits

  /// "HowardDefaultTraits<GR, LEN>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

    /// By default, it is \c long \c long if the \c Value type is integer,

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref KarpDefaultTraits

  /// "KarpDefaultTraits<GR, LEN>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

    /// By default, it is \c long \c long if the \c Value type is integer,

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  template <typename GR, typename CM, typename TR>

  /// planarity checking of an undirected simple graph. It is a simplified

  /// the embedding nor the Kuratowski subdivisons are computed.

  /// embedding of an undirected simple graph. The planar embedding is an

  /// such ordering then the graph contains a K<sub>5</sub> (full graph

  /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on

  /// 3 Red and 3 Blue nodes) subdivision.

  /// Kuratowski subdivision. The running time of the algorithm is O(n).

  ///

  /// \see PlanarDrawing, checkPlanarity()

    /// \brief The map type for storing the embedding

    ///

    /// The map type for storing the embedding.

    /// \see embeddingMap()

    /// Constructor.

    /// \pre The graph must be simple, i.e. it should not

    /// contain parallel or loop arcs.

    /// \brief Run the algorithm.

    /// This function runs the algorithm.

    /// \param kuratowski If this parameter is set to \c false, then the

    /// \return \c true if the graph is planar.

    /// \brief Give back the successor of an arc

    /// This function gives back the successor of an arc. It makes

    /// \brief Give back the calculated embedding map

    /// This function gives back the calculated embedding map, which

    /// contains the successor of each arc in the cyclic order of the

    /// outgoing arcs of its source node.

    /// \brief Give back \c true if the given edge is in the Kuratowski

    /// subdivision

    /// This function gives back \c true if the given edge is in the found

    /// Kuratowski subdivision.

    /// \pre The \c run() function must be called with \c true parameter

    /// before using this function.

    bool kuratowski(const Edge& edge) const {

  /// in the plane. These coordinates satisfy that if the edges are

  /// represented with straight lines, then they will not intersect

  /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,

  /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.

  ///

  /// \see PlanarEmbedding

    /// \brief The point type for storing coordinates

    /// \brief The map type for storing the coordinates of the nodes

    /// \pre The graph must be simple, i.e. it should not

    /// contain parallel or loop arcs.

    /// \brief Calculate the node positions

    /// This function calculates the node positions on the plane.

    /// \return \c true if the graph is planar.

    /// \brief Calculate the node positions according to a

    /// This function calculates the node positions on the plane.

    /// The given \c embedding map should contain a valid combinatorical

    /// embedding, i.e. a valid cyclic order of the arcs.

    /// It can be computed using PlanarEmbedding.

    /// This function returns the coordinate of the given node.

    /// \brief Return the grid embedding in a node map

    /// This function returns the grid embedding in a node map of

    /// \c dim2::Point<int> coordinates.

  /// so that there are no adjacent nodes with the same color. The

  /// planar graphs can always be colored with four colors, which is

  /// proved by Appel and Haken. Their proofs provide a quadratic

  /// implement an efficient algorithm. The five and six coloring can be

  /// made in linear time, but in this class, the five coloring has

  /// decide whether a planar graph is three colorable is NP-complete.

  /// This order can be computed by selecting the node with least

  /// outgoing arcs to unprocessed nodes in each phase. This order

    /// \brief The map type for storing color indices

    /// \brief The map type for storing colors

    ///

    /// The map type for storing colors.

    /// \see Palette, Color

    /// Constructor.

    /// \pre The graph must be simple, i.e. it should not

    /// contain parallel or loop arcs.

    /// \brief Return the node map of color indices

    /// This function returns the node map of color indices. The values are

    /// in the range \c [0..4] or \c [0..5] according to the coloring method.

    /// \brief Return the node map of colors

    /// This function returns the node map of colors. The values are among

    /// five or six distinct \ref lemon::Color "colors".

    /// \brief Return the color index of the node

    /// This function returns the color index of the given node. The value is

    /// in the range \c [0..4] or \c [0..5] according to the coloring method.

    /// \brief Return the color of the node

    /// This function returns the color of the given node. The value is among

    /// five or six distinct \ref lemon::Color "colors".

    /// \brief Calculate a coloring with at most six colors

    /// \return \c true if the algorithm could color the graph with six colors.

    /// If the algorithm fails, then the graph is not planar.

    /// \note This function can return \c true if the graph is not

    /// planar, but it can be colored with at most six colors.

    /// \brief Calculate a coloring with at most five colors

    /// \param embedding This map should contain a valid combinatorical

    /// embedding, i.e. a valid cyclic order of the arcs.

    /// It can be computed using PlanarEmbedding.

    /// \brief Calculate a coloring with at most five colors

    /// \return \c true if the graph is planar.

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref PreflowDefaultTraits

  /// "PreflowDefaultTraits<GR, CAP>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.