Graph Checker ( GraphChecker )

Definition

The class GraphChecker maintains a list of check-graph handler functions Checkers, which are used in order to test if a graph satsifies a given set of properties, or to compute the set of properties a given graph satisfies. The type check_graph_handler is a pointer to a check-graph handler function. Such a function, e.g. f, has to be declared as

AgdKey f(const graph& G, KeySet& props, KeySet& satisfied, bool check_all);

It has to test if input graph G satisfies the properties in props. Each property that has been checked must be removed from props. If check_all is true, each satisfied property is added to satsified. If check_all is false, f returns an unsatisfied property or a nil key (cf. Sect. Keys) if it cannot find an unsatisfied property.

GraphChecker allows to add and remove functions from Checkers. New handler functions are added at the beginning of Checkers, i.e., a newly added handler is called before any other handler. Initially, Checkers contains a default handler function, which can test for the following properties:

directed	undirected	planar	simple	no_self_loops	no_reversals
connected	biconnected	triconnected	bipartite	four_graph	acyclic
forest	tree	single_source	single_sink

#include < AGD/GraphChecker.h >

Creation

GraphChecker

C

creates an instance C of type GraphChecker.

Operations

bool	C.check(const leda_graph& G, KeySet& props)
		returns true iff G satisfies all properties in props.
bool	C.check(const leda_graph& G, KeySet& props, AgdKey& not_satisfied)
		returns true if G satisfies all properties in props, otherwise false is returned and not_satsified is a property in props that is not satisfied by G.
KeySet	C.get_properties(const leda_graph& G, KeySet& props)
		returns the set of all properties in props which are satisfied by G.
list_item	C.add_checker(check_graph_handler f)
		appends a new handler function f at the beginning of Checkers. Returns the corresponding list item.
void	C.rem_checker(list_item it)
		removes the check-handler function at position it in Checkers. Precondition: it is a list item in Checkers.