Detailed reference#

Module contents#

exception vf3py.ApplicabilityScopeError(message)#

Bases: Exception

VF3Py has two limitations:

  • nx.MultiGraph and nx.MultiDiGraph are not supported.

  • Complex rules for matching nodes and edges. In particular, can not allow the same node (or edge) to be matched with multiple ‘colors’.

This exception can be thrown by any of these functions: are_isomorphic, get_automorphisms, get_exact_isomorphisms, get_subgraph_isomorphisms, has_subgraph, main_vf3_caller.

vf3py.are_isomorphic(source_graph: Graph | DiGraph, target_graph: Graph | DiGraph, **kwargs) → bool#

Check if two graphs are isomorphic. This includes checks for number of nodes - are_isomorphic always returns False if two graphs have different number of nodes, as opposed to graph-subgraph isomorphisms.

Parameters:

  • main_graph (nx.Graph | nx.DiGraph) – First graph.

  • ref_graph (nx.Graph | nx.DiGraph) – Second graph. Swap between source_graph <-> target_graph changes nothing.

  • node_match (Callable[[dict, dict], bool], optional) – Nodes are allowed to be matched only if this function returns True for the nodes’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • edge_match (Callable[[dict, dict], bool], optional) – Edges are allowed to be matched only if this function returns True for the edges’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • verbose (bool, optional) – Whether to print info on some intermediate steps. Defaults to False.

Returns:

True if graphs are isomorphic, False - otherwise.

Return type:

bool

vf3py.get_automorphisms(graph: Graph | DiGraph, **kwargs) → List[Dict]#

Get isomorphic mappings of NetworkX graph onto itself (automorphism).

Parameters:

  • graph (nx.Graph | nx.DiGraph) – The graph of interest.

  • node_match (Callable[[dict, dict], bool], optional) – Nodes are allowed to be matched only if this function returns True for the nodes’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • edge_match (Callable[[dict, dict], bool], optional) – Edges are allowed to be matched only if this function returns True for the edges’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • return_integers (bool, optional) – Whether to represent isomorphisms using integers (True) or the original labels of NetworkX graphs (False). Defaults to False.

  • verbose (bool, optional) – Whether to print info on some intermediate steps. Defaults to False.

Returns:

List of graph<->graph isomorphisms (represented as dicts).

Return type:

List[Dict]

vf3py.get_exact_isomorphisms(source_graph: Graph | DiGraph, target_graph: Graph | DiGraph, **kwargs) → List[Dict]#

Get a list of all isomorphisms between two NetworkX graphs. This includes checks for number of nodes - get_exact_isomorphisms always returns [] if two graphs have different number of nodes, as opposed to graph-subgraph isomorphisms.

Parameters:

  • main_graph (nx.Graph | nx.DiGraph) – First graph.

  • ref_graph (nx.Graph | nx.DiGraph) – Second graph. Swap between source_graph <-> target_graph swaps keys with values in the resulting isomorphisms dicts.

  • node_match (Callable[[dict, dict], bool], optional) – Nodes are allowed to be matched only if this function returns True for the nodes’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • edge_match (Callable[[dict, dict], bool], optional) – Edges are allowed to be matched only if this function returns True for the edges’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • return_integers (bool, optional) – Whether to represent isomorphisms using integers (True) or the original labels of NetworkX graphs (False). Defaults to False.

  • verbose (bool, optional) – Whether to print info on some intermediate steps. Defaults to False.

Returns:

List of source_graph<->target_graph isomorphisms. Each isomorphism is represented by a dict that maps: ‘target_graph’ labels -> ‘source_graph’ labels.

Return type:

List[Dict]

vf3py.get_subgraph_isomorphisms(subgraph: Graph | DiGraph, graph: Graph | DiGraph, **kwargs) → List[Dict]#

Solve subgraph isomorphism problem, i.e. find ways to match nodes of subgraph with some/all nodes of graph.

Parameters:

  • subgraph (nx.Graph | nx.DiGraph) – Searching for maps of this graph.

  • graph (nx.Graph | nx.DiGraph) – Searching for maps into this graph.

  • node_match (Callable[[dict, dict], bool], optional) – Nodes are allowed to be matched only if this function returns True for the nodes’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • edge_match (Callable[[dict, dict], bool], optional) – Edges are allowed to be matched only if this function returns True for the edges’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • return_integers (bool, optional) – Whether to represent isomorphisms using integers (True) or the original labels of NetworkX graphs (False). Defaults to False.

  • verbose (bool, optional) – Whether to print info on some intermediate steps. Defaults to False.

Returns:

List of subgraph->graph isomorphisms. Each isomorphism is represented by a dict that maps: ‘subgraph’ labels -> ‘graph’ labels.

Return type:

List[Dict]

vf3py.has_subgraph(subgraph: Graph | DiGraph, graph: Graph | DiGraph, **kwargs) → bool#

Check if subgraph is a subgraph of graph using VF3 algorithm.

Parameters:

  • subgraph (nx.Graph | nx.DiGraph) – Searching for maps of this graph.

  • graph (nx.Graph | nx.DiGraph) – Searching for maps into this graph.

  • node_match (Callable[[dict, dict], bool], optional) – Nodes are allowed to be matched only if this function returns True for the nodes’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • edge_match (Callable[[dict, dict], bool], optional) – Edges are allowed to be matched only if this function returns True for the edges’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • return_integers (bool, optional) – Whether to represent isomorphisms using integers (True) or the original labels of NetworkX graphs (False). Defaults to False.

  • verbose (bool, optional) – Whether to print info on some intermediate steps. Defaults to False.

Returns:

True if subgraph is, indeed, a subgraph of graph, False - otherwise.

Return type:

bool

vf3py.main_vf3_caller(subgraph: Graph | DiGraph, graph: Graph | DiGraph, node_match: Callable[[dict, dict], bool] = None, edge_match: Callable[[dict, dict], bool] = None, all_solutions=True, return_integers=False, verbose=False) → List[Dict]#

The core routine of the VF3Py library. It solves the subgraph isomorphism problem, i.e. finds ways to match nodes of subgraph with some/all nodes of graph. Only NetworkX graphs are accepted (either nx.Graph or nx.DiGraph). NOTE: It is not practical to call this function directly – use one of the front-end functions instead: are_isomorphic, get_exact_isomorphisms, get_automorphisms, has_subgraph, get_subgraph_isomorphisms.

Parameters:

  • subgraph (nx.Graph | nx.DiGraph) – Searching for maps of this graph.

  • graph (nx.Graph | nx.DiGraph) – Searching for maps into this graph.

  • node_match (Callable[[dict, dict], bool], optional) – Nodes are allowed to be matched only if this function returns True for the nodes’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • edge_match (Callable[[dict, dict], bool], optional) – Edges are allowed to be matched only if this function returns True for the edges’ attributes. Order of arguments: (1) dict of the source graph/subgraph, (2) target graph. Defaults to None.

  • all_solutions (bool, optional) – Whether to generate all possible subgraph->graph matches (True) or only one (False). Defaults to True.

  • return_integers (bool, optional) – Whether to represent isomorphisms using integers (True) or the original labels of NetworkX graphs (False). Defaults to False.

  • verbose (bool, optional) – Whether to print info on some intermediate steps. Defaults to False.

Returns:

List of subgraph->graph isomorphisms. Each isomorphism is represented by a dict that maps: ‘subgraph’ labels -> ‘graph’ labels.

Return type:

List[Dict]

Submodules#

vf3py.vf3py_base module#

This is the C++ backend that performs VF3 calculations. Some small modifications of the original VF3lib code were introduced to make it work with Pybind11 for calling C++ from Python.

vf3py.vf3py_base.calc_bothattrs(pattern: dict, target: dict, directed: bool = False, all_solutions: bool = True, verbose: bool = False) → object#
vf3py.vf3py_base.calc_edgeattr(pattern: dict, target: dict, directed: bool = False, all_solutions: bool = True, verbose: bool = False) → object#
vf3py.vf3py_base.calc_noattrs(pattern: dict, target: dict, directed: bool = False, all_solutions: bool = True, verbose: bool = False) → object#
vf3py.vf3py_base.calc_nodeattr(pattern: dict, target: dict, directed: bool = False, all_solutions: bool = True, verbose: bool = False) → object#