AGD Base ( AGD )

Definition

The class AGD provides a global key mapper, that maps strings to key items of type AgdKey. Furthermore, it defines static methods for testing and establishing properties of graphs.

We use key items to represent properties of instances of a particular type, e.g., ``planar'' for instances of type graph. We represent such properties by arbitrary strings, which are stored in a global hash table by the default keymapper of AGD. Strings in this hash table are accessed via keys of type AgdKey. We use < s > to denote a key for string s.

Predefined Properties

The class key defines an enumeration type Predefined. Constants of this type (e.g., key::directed) can be converted into AgdKey. The following constants are defined by key::Predefined:

Properties of subgraphs
constant	string value	meaning
maximal_planar	``maximal planar''	Inserting any edge of E' makes G' non-planar.
maximum_planar	``maximum planar''	G' is a maximum planar subgraph of G (there is no planar subgraph of G with more edges than G').
maximal_acyclic	``maximal acyclic''	Inserting any edge of E' into G' creates a cycle.
maximum_acyclic	``maximum acyclic''	G' is a maximum acyclic subgraph of G (there is no acyclic subgraph of G with more edges than G').

Properties of graphs
constant	string value	meaning
directed	``directed''	G is directed.
undirected	``undirected''	G is undirected.
planar	``planar''	G is planar.
simple	``simple''	G has no parallel edges.
no_self_loops	``no self loops''	G has no self loops.
no_reversals	``no reversals''	(v, w) $\in$ E $\Rightarrow$ (w, v)$\notin$E for all v, w $\in$ V
connected	``connected''	G is connected.
biconnected	``biconnected''	G is biconnected.
triconnected	``triconnected''	G is triconnected.
bipartite	``bipartite''	G is bipartite.
four_graph	``four-graph''	degree(v) < = 4 for all v $\in$ V
acyclic	``acyclic''	G is a digraph without cycle
forest	``forest''	G represents a forest.
tree	``tree''	G represents a tree.
single_source	``single source''	$\exists$! v $\in$ G : indeg(v) = 0
single_sink	``single sink''	$\exists$! v $\in$ G : outdeg(v) = 0
st_graph	``st-graph''	G is an acyclic digraph with exactly one source and exactly one sink
st_planar	``st-planar''	G is an st-graph an G $\cup$ (s, t) is planar
reduced_acyclic	``reduced acyclic''	G is a acyclic digraph without transitive edges

where G = (V, E).

Properties of clustergraphs
constant	string value	meaning
c_planar	``c-planar''	Clustergraph CG is c-planar.

where CG = (G, T).

Properties of layouts
constant	string value	meaning
straight_line	``straight-line''	All edge polylines have no bend points.
orthogonal	``orthogonal''	All edge segments are either horizontal or vertical.
no_crossings	``no crossings''	The edge polylines do not intersect.
upward_planar	``upward planar''	All edges are directed upwards (downwards).
convex	``convex''	All faces are convex.

where G' = (V, E $\setminus$ E') is subgraph of G = (V, E).

Predefined Rules on Properties

We define the following dependencies between predefined properties. These rules are maintained by the standard rule administrator of AGD.

$$\begin{eqnarray*} \mbox{\it tree\/} & \leftrightarrow & \mbox{\it forest\/} \wed... ...mbox{\it maximal acyclic\/} & \rightarrow & \mbox{\it acyclic\/} \end{eqnarray*}$$

#include < AGD.h >

Operations

double	AGD::version()	returns the version number of the library.
leda_string	AGD::version_string()	returns the version number as string (e.g., 1.1.2).

a) Testing Properties of Graphs

Some of the following functions simply call LEDA functions.

bool	AGD::is_simple(const leda_graph& G)
		returns true if G is simple, e.g. has no parallel edges, false otherwise.
bool	AGD::is_connected(const leda_graph& G)
		returns true if G is connected, false otherwise.
bool	AGD::is_biconnected(const leda_graph& G)
		returns true if G is biconnected, false otherwise.
bool	AGD::is_triconnected(const leda_graph& G)
		returns true if G is triconnected, false otherwise.
bool	AGD::is_cplanar(const ClusterGraph& CG)
		returns true if CG is c-planar, false otherwise.
bool	AGD::is_planar(const leda_graph& G)
		returns true if G is planar, false otherwise.
bool	AGD::is_bipartite(const leda_graph& G)
		returns true if G is bipartite, false otherwise.
bool	AGD::is_four_graph(const leda_graph& G)
		returns true if G is a four-graph, e.g. degree(v) < = 4 holds for every node v of G, false otherwise.
bool	AGD::has_no_self_loops(const leda_graph& G)
		returns true if G contains no self loops, false otherwise.
bool	AGD::has_no_reversals(const leda_graph& G)
		returns true if G is undirected, or if G contains no reversal edges, false otherwise.
bool	AGD::is_acyclic(const leda_graph& G)
		returns true if G is acyclic, false otherwise.
bool	AGD::is_st_graph(const leda_graph& G, leda_node& s, leda_node& t)
		returns true and sets s to the source and t to the sink of G if G an st-graph, false otherwise.
bool	AGD::is_st_graph(const leda_graph& G)
		returns true if G an st-graph, false otherwise.
bool	AGD::is_st_planar(const leda_graph& G, leda_node& s, leda_node& t)
		returns true and sets s to the source and t to the sink of G if G is st-planar, false otherwise.
bool	AGD::is_st_planar(const leda_graph& G)
		returns true if G is st-planar, false otherwise.
bool	AGD::is_forest(const leda_graph& G)
		returns true if G represents a forest, false otherwise.
bool	AGD::is_tree(const leda_graph& G)
		returns true if G represents a tree, false otherwise.
bool	AGD::has_single_source(const leda_graph& G, leda_node& s)
		returns true if G is directed and contains exactly one source (a node with no incoming edges) and sets s to this node, false otherwise.
bool	AGD::has_single_source(const leda_graph& G)
		returns true if G is directed and contains exactly one source, false otherwise.
bool	AGD::has_single_sink(const leda_graph& G, leda_node& t)
		returns true if G is directed and contains exactly one sink (a node with no outgoing edges) and sets t to this node, false otherwise.
bool	AGD::has_single_sink(const leda_graph& G)
		returns true if G is directed and contains exactly one sink, false otherwise.

b) Establishing Properties of Graphs

leda_list<leda_edge>	AGD::triangulate(leda_graph& G)
		triangulates a directed graph G representing a planar map. Returns the list of inserted edges.
leda_list<leda_edge>	AGD::make_bidirected(leda_graph& G)
		makes G bidirected by inserting missing reversal edges. Returns the list of inserted edges.
leda_list<leda_edge>	AGD::make_biconnected(leda_graph& G)
		makes G biconnected. Returns the list of inserted edges.
leda_list<leda_edge>	AGD::augment_planar_biconnected(leda_graph& G)
		augments a planar graph G to a planar and biconnected graph. Returns the list of inserted edges.
leda_list<leda_edge>	AGD::make_map(leda_graph& G)
		makes G bidirected and turns it into a map. Returns the list of inserted edges.
bool	AGD::embed_planar_graph(leda_graph& G)
		takes as input a bidirected graph G. Returns true and turns G into a planar map if G is planar, false otherwise.
bool	AGD::embed_cplanar_graph(ClusterGraph& CG, leda_list<leda_edge>& L)
		takes as input a clustergraph CG. Returns true and turns CG into a planar map if CG is c-planar, false otherwise. L contains added reversal edges.

c) Access to the Default Keymapper and Rule System

const DefaultKeymapper&	AGD::get_keymapper()	returns the default keymapper of AGD.
int	AGD::number_of_keys()	returns the number of defined keys.
AgdKey	AGD::ask_key(const leda_string& s)
		returns the key < s > if < s > is already defined, nil otherwise.
AgdKey	AGD::get_key(const leda_string& s)
		returns the key < s >.
AgdKey	AGD::predefined(key::Predefined k)
		converts k into a key of type AgdKey.
KeySet	AGD::get_properties(const leda_graph& G)
		returns the set of all properties that G satisfies.
KeySet	AGD::get_properties(const ClusterGraph& G)
		returns the set of all properties that CG satisfies.
DefaultRuleAdmin&	AGD::get_rule_admin()	returns the default rule administrator of AGD.
KeySet	AGD::closure(const KeySet& S)
		returns the closure of set S according to the rule system of AGD.
PreCond	AGD::closure(const PreCond& P)
		returns the closure of precondition P according to the rule system of AGD.
PostCond	AGD::closure(const PostCond& P)
		returns the closure of postcondition P according to the rule system of AGD.
bool	AGD::implies(const KeySet& P, const KeySet& Q)
		returns true iff P $\rightarrow$ Q, i.e., if P* $\supseteq$ Q.
bool	AGD::implies(const CondBase& P, const CondBase& Q)
		returns true iff P $\rightarrow$ Q.

d) Access to Checkers

GraphChecker&	AGD::get_graph_checker()	returns a reference to the global graph checker.
ClusterGraphChecker&	AGD::get_clustergraph_checker()
		returns a reference to the global clustergraph checker.
SubgraphChecker&	AGD::get_subgraph_checker()
		returns a reference to the global subgraph checker.

Implementation

Most functions for testing and establishing graph properties take time $\protectO$(n + m), except for is_four_graph(), has_single_source() and has_single_sink() which take time $\protectO$(n). In each case, n is the number of nodes and m is the number of edges of the input graph G.