Next: Graphs and Iterators Up: Graph Algorithms Previous: Graph Morphism Algorithms ( Contents Index

Graph Morphism Algorithm Functionality ( graph_morphism_algorithm )

Types

#include < LEDA/graph/graph_morphism_algorithm.h >

graph_morphism_algorithm< graph_t >::node the type of an input graph node

graph_morphism_algorithm< graph_t >::edge the type of an input graph edge

graph_morphism_algorithm< graph_t >::node_morphism the type for a found node mapping

graph_morphism_algorithm< graph_t >::edge_morphism the type for a found edge mapping

graph_morphism_algorithm< graph_t >::node_compat the type for a node compatibility functor

graph_morphism_algorithm< graph_t >::edge_compat the type for an edge compatibility functor

graph_morphism_algorithm< graph_t >::morphism the type for a found node and edge mapping

graph_morphism_algorithm< graph_t >::morphism_list the type of a list of all found morphisms

graph_morphism_algorithm< graph_t >::callback the type for the callback functor

graph_morphism_algorithm< graph_t >::cardinality_t the number type of the returned cardinality

graph_morphism_algorithm< graph_t >::prep_graph the type of a prepared graph data structure

Operations

prep_graph alg.prepare_graph(const graph_t& g, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)

prepares a data structures of a graph to be used as input to subsequent morphism search calls. This may speed up computation if the same graph is used several times.

void alg.delete_prepared_graph(prep_graph pg)

frees the memory allocated to a prepared graph data structure constructed before.

cardinality_t alg.get_num_calls() returns the number of recursive calls the algorithm has made so far.

void alg.reset_num_calls() resets the number of recursive calls to 0.

bool alg.find_iso(const graph_t& g1, const graph_t& g2, node_morphism* _node_morph = NULL, edge_morphism* _edge_morph = NULL, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for a graph isomorphism between g1 and g2 and returns it through node_morph and edge_morph if a non-NULL pointer to a node map and a non-NULL pointer to an edge map are passed respectively. Those must be initialized to g2 and will therefore carry references to the mapped node or edge in g1. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.cardinality_iso(const graph_t& g1, const graph_t& g2, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for a graph isomorphism between g1 and g2 and returns its cardinality. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.find_all_iso(const graph_t& g1, const graph_t& g2, list<morphism*>& _isomorphisms, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for all graph isomorphisms between g1 and g2 and returns them through _isomorphisms. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.enumerate_iso(const graph_t& g1, const graph_t& g2, leda_callback_base<morphism>& _callback, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for all graph isomorphisms between g1 and g2 and calls the callback functor callb for each one. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

bool alg.find_sub(const graph_t& g1, const graph_t& g2, node_morphism* _node_morph = NULL, edge_morphism* _edge_morph = NULL, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for a subgraph isomorphism from g2 to g1 and returns it through node_morph and edge_morph if a non-NULL pointer to a node map and a non-NULL pointer to an edge map are passed respectively. Those must be initialized to g2 and will therefore carry references to the mapped node or edge in g1. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.cardinality_sub(const graph_t& g1, const graph_t& g2, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for a subgraph isomorphism from g2 to g1 and returns its cardinality. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.find_all_sub(const graph_t& g1, const graph_t& g2, list<morphism*>& _isomorphisms, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for all subgraph isomorphisms from g2 to g1 and returns them through _isomorphisms. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.enumerate_sub(const graph_t& g1, const graph_t& g2, leda_callback_base<morphism>& _callback, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for all subgraph isomorphisms from g2 to g1 and calls the callback functor callb for each one. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

bool alg.find_mono(const graph_t& g1, const graph_t& g2, node_morphism* _node_morph = NULL, edge_morphism* _edge_morph = NULL, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for a graph monomorphism from g2 to g1 and returns it through node_morph and edge_morph if a non-NULL pointer to a node map and a non-NULL pointer to an edge map are passed respectively. Those must be initialized to g2 and will therefore carry references to the mapped node or edge in g1. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.cardinality_mono(const graph_t& g1, const graph_t& g2, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for a graph monomorphism from g2 to g1 and returns its cardinality. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.find_all_mono(const graph_t& g1, const graph_t& g2, list<morphism*>& _isomorphisms, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for all graph monomorphisms from g2 to g1 and returns them through _isomorphisms. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp. This method can be called with prepared graph data structures as input for either graph, too.

cardinality_t alg.enumerate_mono(const graph_t& g1, const graph_t& g2, leda_callback_base<morphism>& _callback, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)

searches for all graph monomorphisms from g2 to g1 and calls the callback functor callb for each one. g2 must not have more nodes or more edges than g1 to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp.
This method can be called with prepared graph data structures as input for either graph, too.

bool alg.is_graph_isomorphism(const graph_t& g1, const graph_t& g2, node_morphism const* node_morph, edge_morphism const* edge_morph = NULL, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)

checks whether the morphism given by node_morph and edge_morph (optional) is a valid graph isomorphisms between g1 and g2. The allowed mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp.

bool alg.is_subgraph_isomorphism(const graph_t& g1, const graph_t& g2, node_morphism const* node_morph, edge_morphism const* edge_morph = NULL, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)

checks whether the morphism given by node_morph and edge_morph (optional) is a valid subgraph isomorphisms from g1 to g2. The allowed mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp.

bool alg.is_graph_monomorphism(const graph_t& g1, const graph_t& g2, node_morphism const* node_morph, edge_morphism const* edge_morph = NULL, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)

checks whether the morphism given by node_morph and edge_morph (optional) is a valid graph monomorphisms from g2 to g1. The allowed mappings can be restricted by the node and edge compatibility functors node_comp and edge_comp.

Next: Graphs and Iterators Up: Graph Algorithms Previous: Graph Morphism Algorithms ( Contents Index

graph_morphism_algorithm< graph_t >::node	the type of an input graph node
graph_morphism_algorithm< graph_t >::edge	the type of an input graph edge
graph_morphism_algorithm< graph_t >::node_morphism	the type for a found node mapping
graph_morphism_algorithm< graph_t >::edge_morphism	the type for a found edge mapping
graph_morphism_algorithm< graph_t >::node_compat	the type for a node compatibility functor
graph_morphism_algorithm< graph_t >::edge_compat	the type for an edge compatibility functor
graph_morphism_algorithm< graph_t >::morphism	the type for a found node and edge mapping
graph_morphism_algorithm< graph_t >::morphism_list	the type of a list of all found morphisms
graph_morphism_algorithm< graph_t >::callback	the type for the callback functor
graph_morphism_algorithm< graph_t >::cardinality_t	the number type of the returned cardinality
graph_morphism_algorithm< graph_t >::prep_graph	the type of a prepared graph data structure

prep_graph	alg.prepare_graph(const graph_t& g, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)
		prepares a data structures of a graph to be used as input to subsequent morphism search calls. This may speed up computation if the same graph is used several times.
void	alg.delete_prepared_graph(prep_graph pg)
		frees the memory allocated to a prepared graph data structure constructed before.
cardinality_t	alg.get_num_calls()	returns the number of recursive calls the algorithm has made so far.
void	alg.reset_num_calls()	resets the number of recursive calls to 0.
bool	alg.find_iso(const graph_t& g1, const graph_t& g2, node_morphism* _node_morph = NULL, edge_morphism* _edge_morph = NULL, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for a graph isomorphism between `g1` and `g2` and returns it through `node_morph` and `edge_morph` if a non-NULL pointer to a node map and a non-NULL pointer to an edge map are passed respectively. Those must be initialized to `g2` and will therefore carry references to the mapped node or edge in `g1`. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.cardinality_iso(const graph_t& g1, const graph_t& g2, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for a graph isomorphism between `g1` and `g2` and returns its cardinality. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.find_all_iso(const graph_t& g1, const graph_t& g2, list<morphism*>& _isomorphisms, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for all graph isomorphisms between `g1` and `g2` and returns them through `_isomorphisms`. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.enumerate_iso(const graph_t& g1, const graph_t& g2, leda_callback_base<morphism>& _callback, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for all graph isomorphisms between `g1` and `g2` and calls the callback functor `callb` for each one. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
bool	alg.find_sub(const graph_t& g1, const graph_t& g2, node_morphism* _node_morph = NULL, edge_morphism* _edge_morph = NULL, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for a subgraph isomorphism from `g2` to `g1` and returns it through `node_morph` and `edge_morph` if a non-NULL pointer to a node map and a non-NULL pointer to an edge map are passed respectively. Those must be initialized to `g2` and will therefore carry references to the mapped node or edge in `g1`. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.cardinality_sub(const graph_t& g1, const graph_t& g2, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for a subgraph isomorphism from `g2` to `g1` and returns its cardinality. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.find_all_sub(const graph_t& g1, const graph_t& g2, list<morphism*>& _isomorphisms, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for all subgraph isomorphisms from `g2` to `g1` and returns them through `_isomorphisms`. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.enumerate_sub(const graph_t& g1, const graph_t& g2, leda_callback_base<morphism>& _callback, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for all subgraph isomorphisms from `g2` to `g1` and calls the callback functor `callb` for each one. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
bool	alg.find_mono(const graph_t& g1, const graph_t& g2, node_morphism* _node_morph = NULL, edge_morphism* _edge_morph = NULL, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for a graph monomorphism from `g2` to `g1` and returns it through `node_morph` and `edge_morph` if a non-NULL pointer to a node map and a non-NULL pointer to an edge map are passed respectively. Those must be initialized to `g2` and will therefore carry references to the mapped node or edge in `g1`. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.cardinality_mono(const graph_t& g1, const graph_t& g2, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for a graph monomorphism from `g2` to `g1` and returns its cardinality. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.find_all_mono(const graph_t& g1, const graph_t& g2, list<morphism*>& _isomorphisms, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for all graph monomorphisms from `g2` to `g1` and returns them through `_isomorphisms`. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
cardinality_t	alg.enumerate_mono(const graph_t& g1, const graph_t& g2, leda_callback_base<morphism>& _callback, const node_compat& _node_comp = DEFAULT_NODE_CMP, const edge_compat& _edge_comp = DEFAULT_EDGE_CMP)
		searches for all graph monomorphisms from `g2` to `g1` and calls the callback functor `callb` for each one. `g2` must not have more nodes or more edges than `g1` to make a mapping possible. The possible mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`. This method can be called with prepared graph data structures as input for either graph, too.
bool	alg.is_graph_isomorphism(const graph_t& g1, const graph_t& g2, node_morphism const* node_morph, edge_morphism const* edge_morph = NULL, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)
		checks whether the morphism given by `node_morph` and `edge_morph` (optional) is a valid graph isomorphisms between `g1` and `g2`. The allowed mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`.
bool	alg.is_subgraph_isomorphism(const graph_t& g1, const graph_t& g2, node_morphism const* node_morph, edge_morphism const* edge_morph = NULL, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)
		checks whether the morphism given by `node_morph` and `edge_morph` (optional) is a valid subgraph isomorphisms from `g1` to `g2`. The allowed mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`.
bool	alg.is_graph_monomorphism(const graph_t& g1, const graph_t& g2, node_morphism const* node_morph, edge_morphism const* edge_morph = NULL, const node_compat& node_comp = DEFAULT_NODE_CMP, const edge_compat& edge_comp = DEFAULT_EDGE_CMP)
		checks whether the morphism given by `node_morph` and `edge_morph` (optional) is a valid graph monomorphisms from `g2` to `g1`. The allowed mappings can be restricted by the node and edge compatibility functors `node_comp` and `edge_comp`.