Public Types | Public Member Functions

PlanarDrawing< Graph > Class Template Reference


Detailed Description

template<typename Graph>
class lemon::PlanarDrawing< Graph >

The planar drawing algorithm calculates positions for the nodes in the plane. These coordinates satisfy that if the edges are represented with straight lines, then they will not intersect each other.

Scnyder's algorithm embeds the graph on an (n-2)x(n-2) size grid, i.e. each node will be located in the [0..n-2]x[0..n-2] square. The time complexity of the algorithm is O(n).

See also:
PlanarEmbedding

#include <lemon/planarity.h>

List of all members.

Public Types

typedef dim2::Point< int > Point
 The point type for storing coordinates.
typedef Graph::template
NodeMap< Point
PointMap
 The map type for storing the coordinates of the nodes.

Public Member Functions

 PlanarDrawing (const Graph &graph)
 Constructor.
bool run ()
 Calculate the node positions.
template<typename EmbeddingMap >
void run (const EmbeddingMap &embedding)
 Calculate the node positions according to a combinatorical embedding.
Point operator[] (const Node &node) const
 The coordinate of the given node.
const PointMapcoords () const
 Return the grid embedding in a node map.

Constructor & Destructor Documentation

PlanarDrawing ( const Graph graph) [inline]

Constructor

Precondition:
The graph must be simple, i.e. it should not contain parallel or loop arcs.

Member Function Documentation

bool run ( ) [inline]

This function calculates the node positions on the plane.

Returns:
true if the graph is planar.
void run ( const EmbeddingMap &  embedding) [inline]

This function calculates the node positions on the plane. The given embedding map should contain a valid combinatorical embedding, i.e. a valid cyclic order of the arcs. It can be computed using PlanarEmbedding.

Point operator[] ( const Node &  node) const [inline]

This function returns the coordinate of the given node.

const PointMap& coords ( ) const [inline]

This function returns the grid embedding in a node map of dim2::Point<int> coordinates.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines