Definition
A parameterized planar map M is a planar map whose nodes, edges and faces contain additional (user defined) data. Every node contains an element of a data type vtype , called the node type of M ,every edge contains an element of a data type etype , called the edge type of M , and every face contains an element of a data type ftype called the face type of M . All operations of the data type planarmap are also defined for instances of any parameterized planar_map type. For parameterized planar maps there are additional operations to access or update the node and face entries.
#include < LEDA/graph/planar_map.h >
Creation
PLANAR_MAP< vtype,etype,ftype> | M(const GRAPH< vtype,etype> & G) | |
creates an instance M of type PLANAR_MAP<vtype,etype,ftype> and initializes it to
the planar map represented by the parameterized directed graph G
.
The node and edge entries of G
are copied into the corresponding
nodes and edges of M
. Every face f
of M
is assigned the default
value of type ftype
.
Precondition G represents a planar map. |
Operations
const vtype& | M.inf(node v) | returns the information of node v . |
const etype& | M.inf(edge e) | returns the information of node v . |
const ftype& | M.inf(face f) | returns the information of face f . |
vtype& | M[node v] | returns a reference to the information of node v . |
etype& | M[edge e] | returns a reference to the information of edge e . |
ftype& | M[face f] | returns a reference to the information of face f . |
void | M.assign(node v, const vtype& x) | |
makes x the information of node v . | ||
void | M.assign(edge e, const etype& x) | |
makes x the information of node v . | ||
void | M.assign(face f, const ftype& x) | |
makes x the information of face f . | ||
edge | M.new_edge(edge e1, edge e2, const ftype& y) | |
inserts the edge
e = (source(e_{1}), source(e_{2}))
and its reversal edge e'
into M
.
Precondition e_{1} and e_{2} are bounding the same face F . The operation splits F into two new faces f , adjacent to edge e , and f' , adjacent to edge e' , with inf(f ) = inf (F ) and inf(f' ) = y . |
||
edge | M.split_edge(edge e, const vtype& x) | |
splits edge e = (v, w) and its reversal r = (w, v) into edges (v, u) , (u, w) , (w, u) , and (u, v) . Assigns information x to the created node u and returns the edge (u, w) . | ||
node | M.new_node(list< edge> & el, const vtype& x) | |
splits the face bounded by the edges in el
by
inserting a new node u
and connecting it to all
source nodes of edges in el
. Assigns information x
to u
and returns u
.
Precondition all edges in el bound the same face. |
||
node | M.new_node(face f, const vtype& x) | |
splits face f into triangles by inserting a new node u with information x and connecting it to all nodes of f . Returns u . |
Implementation
Parameterized planar maps are derived from planar maps. All additional operations for manipulating the node and edge contents take constant time.