Types
#include < LEDA/graph/graph_morphism_algorithm.h >
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() | return 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 g2 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. |