Next: SPQR-Trees Up: Canonical Orderings Previous: The Canonical Ordering of Contents Index

The Leftmost Canonical Order of a Graph ( LmcOrder )

Baseclasses

$\begin{picture}(6.5,2.5) \thicklines \put(0,1.5){\framebox (5,1){\bf Canonical... ...,2){\vector(0,-1){1}}\put(1.5,0){\framebox (5,1){\bf LmcOrder}} \end{picture}$

Definition

An instance Lmc of type LmcOrder is a leftmost canonical ordering of a graph G. We define a leftmost canonical ordering as follows:

Definition: A canonical ordering is a leftmost canonical (lmc-)ordering if we can add in any step k a vertex V_k with leftvertex c_l or a vertex set V_k' with leftvertex c_l', and l < l' holds, then k < k'.

#include < AGD/CanonicalOrder.h >

Creation

LmcOrder Lmc(leda_graph& g, CanonicalOrderType co_type = co_triconnected, leda_face F = nil, bool prefer_nodes = false, double base_ratio = 0.0)

creates an instance Lmc of type LmcOrder initialized to a leftmost canonical order for G. Precondition: G is a directed graph representing a planar map.

Implementation

LmcOrder derives from CanonicalOrder. The transformation into a leftmost ordering takes time $\protectO$ (n), where n is the number of nodes of G.

Next: SPQR-Trees Up: Canonical Orderings Previous: The Canonical Ordering of Contents Index

LmcOrder	Lmc(leda_graph& g, CanonicalOrderType co_type = co_triconnected, leda_face F = nil, bool prefer_nodes = false, double base_ratio = 0.0)
		creates an instance Lmc of type LmcOrder initialized to a leftmost canonical order for G. Precondition: G is a directed graph representing a planar map.