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
Christian Uhrig 2017-04-07