Sets of a Canonical Ordering ( OrderSet )

Definition

An instance V of type OrderSet represents one set of a canonical ordering C of a graph G = (V, E). It contains a set {v_,..., v_p} of nodes of G ordered from left to right, a leftvertex c_$\ell$, a rightvertex c_r, and additional information has_left and has_right, where has$\_$left = true$\iff$(v₁, c_$\ell$) $\in$ E, and has$\_$right = true$\iff$(v_p, c_r) $\in$ E.

#include < AGD/CanonicalOrder.h >

Creation

OrderSet	V	creates an instance V of type OrderSet representing an empty set.
OrderSet	V(int l, leda_edge el = nil, leda_edge er = nil)
		creates an instance V of type OrderSet representing a set of length l with left edge el and right edge er.

Operations

leda_node	V.left()	returns the leftvertex c$\ell$ of V.
leda_node	V.right()	returns the rightvertex cr of V.
leda_edge	V.left_edge()	returns the edge (z1, c$\ell$) or nil.
leda_edge	V.right_edge()	returns the edge (zp, cr) or nil.
bool	V.has_left()	returns the information has_left of V.
bool	V.has_right()	returns the information has_right of V.
void	V.left(leda_node cl)	sets the leftvertex of V to cl.
void	V.right(leda_node cr)	sets the rightvertex of V to cr.
void	V.left_edge(leda_edge el)	sets the edge (z1, c$\ell$).
void	V.right_edge(leda_edge er)
		sets the edge (zp, cr).
int	V.len()	returns the length of V, i.e. the number of nodes in V.
leda_node&	V[const int i]	returns the i-th node of V from left (the leftmost node has index 1).

Implementation

Order sets are implemented by arrays. All operations take constant time.