next up previous contents index
Next: Node Arrays ( node_array Up: Graphs and Related Data Previous: Planar Maps ( planar_map   Contents   Index


Parameterized Planar Maps ( PLANAR_MAP )

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 planar$ \_$map 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/planar _map.h >

Creation

PLANAR_MAP<vtype,etype,ftype> M(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

vtype M.inf(node v) returns the information of node v.

etype M.inf(edge e) returns the information of node v.

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, vtype x) makes x the information of node v.

void M.assign(edge e, etype x) makes x the information of node v.

void M.assign(face f, ftype x) makes x the information of face f.

edge M.new_edge(edge e1, edge e2, 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, 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, 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, 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.


next up previous contents index
Next: Node Arrays ( node_array Up: Graphs and Related Data Previous: Planar Maps ( planar_map   Contents   Index
LEDA research project
2000-02-09