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 >
|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.
|const vtype&||M.inf(node v)||returns the information of node v.|
|const etype&||M.inf(edge e)||returns the information of edge e.|
|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 edge e.|
|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(e1), source(e2))
and its reversal edge e' into M.
Precondition e1 and e2 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.|
Parameterized planar maps are derived from planar maps. All additional operations for manipulating the node and edge contents take constant time.