next up previous contents index
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 up previous contents index
Next: Graphs and Iterators Up: Graph Algorithms Previous: Graph Morphism Algorithms (   Contents   Index