Augmentation Modules ( AugmentationModule )

Baseclasses

Definition

The class AugmentationModule is the base class for augmentation modules. An augmentation module transforms an input graph G into an output graph G' by adding edges, such that G' satisfies a certain condition, e.g., biconnected. This condition is expressed by the postcondition of the module.

Input and Output Parameters

input parameter:	graph	in_graph=1
output parameter:	supergraph	out_supergraph=1

The integer constants in_graph and out_supergraph denote the positions in the input and output parameter lists. The values can be used to reference the desired parameter when setting the pre- and postcondition.

Implementation of Augmentation Algorithms

An implementation of an augmentation module must override the protected method do_call(G,L), which gets as input a graph reference G. The augmented edges are added to G, and the list of added edges is returned in L.

#include < AGD/AugmentationModule.h >

Initialization

AugmentationModule

A

initializes an augmentation module.

Operations

Standard Interface

bool	A.check(const leda_graph& G, AgdKey& p)
		returns true if G satisfies the precondition of A. Otherwise, false is returned and p contains a property that is not satisfied.
void	A.call(leda_graph& G)	calls the augmentation module for graph G.
void	A.call(leda_graph& G, leda_list<leda_edge>& L)
		calls the augmentation module for graph G. Returns the list of added edges in L.
int	A.num_added_edges()	returns the number of added edges.

Protected Overridables to Implement Functionality

void	A.do_call(leda_graph& G, leda_list<leda_edge>& L)
		implements the augmentation algorithm for graph G. Returns the list of added edges in L.

Protected Auxiliary Methods

void	AugmentationModule::hide_self_loops(leda_graph& G, leda_list<leda_edge>& L)
		hides all self loops and appends them to L.
void	AugmentationModule::hide_multiple_edges(leda_graph& G, leda_list<leda_edge>& L)
		hides all but one of each set of parallel edges and appends all hidden edges to L.