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/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(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.

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
root 2008-01-09