Next: Planar Subgraphs ( PlanarSubgraph Up: Computation of Subgraphs Previous: Computation of Subgraphs Contents Index

Subgraph Modules ( SubgraphModule )

Baseclasses

$\begin{picture}(6.5,2.5) \thicklines \put(0,1.5){\framebox (5.5,1){\bf AGDModu... ...\vector(0,-1){1}}\put(1,0){\framebox (6,1){\bf SubgraphModule}} \end{picture}$

Definition

The class SubgraphModule is the base class for subgraph modules. A subgraph module computes a subgraph G' = (V, E $\setminus$ E') of an input graph G = (V, E), where E' $\subseteq$ E. Usually, G' satisfies a certain condition, e.g, planar or acyclic. This condition is expressed by the postcondition of the module.

Input and Output Parameters

input parameter: graph in_graph=1

output parameter: subgraph out_subgraph=1

The integer constants in_graph and out_subgraph 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.

Implementing Subgraph Modules

An implementation of a subgraph module must override the protected method do_call(G,L), which gets as input a const reference to graph G. It determines the set of edges E', and returns it as a list in L.

#include < AGD/SubgraphModule.h >

Initialization

SubgraphModule S initializes a subgraph module.

Operations

Standard Interface

bool S.check(const leda_graph& G, AgdKey& p)

returns true if G satisfies the precondition of S. Otherwise, false is returned and p contains a property that is not satisfied.

void S.call(const leda_graph& G, leda_list<leda_edge>& L)

calls the subgraph module for graph G. Returns in L the list of edges in E'.

void S.call(leda_graph& G) calls the subgraph module for graph G, and deletes in G all edges in E'.

void S.call(GraphCopy& GC, leda_list<leda_edge>& L)

calls the subgraph module for graph copy GC. Deletes in GC all edges in E' = {e₁,..., e_k}, and returns in L the list of corresponding edges original(e₁),..., original(e_k) in original(GC).

int S.num_del_edges() returns the number of edges in E' after a call of the algorithm.

Protected Overridables to Implement Functionality

void S.do_call(const leda_graph& G, leda_list<leda_edge>& L)

implements the computation of the subgraph for graph G. Returns in L the list of edges in E', which are the edges that must be deleted in G in order to get the subgraph G'.

Next: Planar Subgraphs ( PlanarSubgraph Up: Computation of Subgraphs Previous: Computation of Subgraphs Contents Index

input parameter:	graph	in_graph=1
output parameter:	subgraph	out_subgraph=1

bool	S.check(const leda_graph& G, AgdKey& p)
		returns true if G satisfies the precondition of S. Otherwise, false is returned and p contains a property that is not satisfied.
void	S.call(const leda_graph& G, leda_list<leda_edge>& L)
		calls the subgraph module for graph G. Returns in L the list of edges in E'.
void	S.call(leda_graph& G)	calls the subgraph module for graph G, and deletes in G all edges in E'.
void	S.call(GraphCopy& GC, leda_list<leda_edge>& L)
		calls the subgraph module for graph copy GC. Deletes in GC all edges in E' = {e₁,..., e_k}, and returns in L the list of corresponding edges original(e₁),..., original(e_k) in original(GC).
int	S.num_del_edges()	returns the number of edges in E' after a call of the algorithm.

void	S.do_call(const leda_graph& G, leda_list<leda_edge>& L)
		implements the computation of the subgraph for graph G. Returns in L the list of edges in E', which are the edges that must be deleted in G in order to get the subgraph G'.