Leveled Graphs ( LeveledGraph )

Baseclasses

Definition

An instance LG of type LeveledGraph is a graph G = (V, E) with an injective mapping level : V $\rightarrow$ ZZ from the nodes of LG into the integer numbers. We call the set of nodes L_i : = {v | level(v) = i} the ith level of LG. The number of levels of LG is

$\left\{ \begin{array}{cl} \max \{i\mid L_i\neq\emptyset\}-\min\{i\mid L_i\neq\... ...t\}+1 & \mbox{ if }V\neq\emptyset\\ 0 & \mbox{ otherwise} \end{array} \right.$
LeveledGraph also maintains the current number of sources and sinks.

#include < AGD/LeveledGraph.h >

Creation

LeveledGraph

LG

creates an instance LG of type LeveledGraph initialized to an empty graph.

Operations

int	LG.number_of_levels()	returns the number of levels of LG.
int	LG.min_level()	returns min{i | Li! = $\emptyset$}. Precondition: V! = $\emptyset$
int	LG.max_level()	returns max{i | Li! = $\emptyset$}. Precondition: V! = $\emptyset$
int	LG.level(leda_node v)	returns the index i of the level Li to which v belongs.
void	LG.level(leda_node v, int i)
		changes the level to which v belongs to Li.
const leda_list<leda_node>&	LG.nodes(int i)	returns the list of nodes on level Li.
int	LG.nodes(int i, leda_list<leda_node>& L)
		assigns the list of nodes on level Li to L and returns the number of nodes on Li.
int	LG.length(int i)	returns the number of nodes on level Li.
bool	LG.is_isolated(leda_node v)
		returns true iff v is a isolated node, i.e., degree(v) = 0.
int	LG.number_of_sources()	returns the current number of sources (nodes with no incoming edges) in LG.
int	LG.number_of_sinks()	returns the current number of sinks (nodes with no outgoing edges) in LG.
leda_node	LG.new_node(int i)	adds a new node on level Li to LG and returns it.
leda_node	LG.new_node()	adds a new node on level L0 to LG and returns it.

Implementation

Most operations take time $\protectO$(1) or expected time $\protectO$(1), except for invert, which takes time $\protectO$(n + m + $\ell$), where n is the number of nodes, m is the number of edges, and $\ell$ is the number of levels in LG.