Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.graph_is_isomorphic#

graph_is_isomorphic(first, second, /, node_matcher=None, edge_matcher=None, id_order=True, call_limit=None)#

Determine if 2 undirected graphs are isomorphic

This checks if 2 graphs are isomorphic both structurally and also comparing the node data and edge data using the provided matcher functions. The matcher function takes in 2 data objects and will compare them. A simple example that checks if they’re just equal would be:

graph_a = rustworkx.PyGraph()
graph_b = rustworkx.PyGraph()
rustworkx.is_isomorphic(graph_a, graph_b,
                       lambda x, y: x == y)

Note

For better performance on large graphs, consider setting id_order=False.

Parameters:

  • first (PyGraph) – The first graph to compare

  • second (PyGraph) – The second graph to compare

  • node_matcher (callable) – A python callable object that takes 2 positional one for each node data object. If the return of this function evaluates to True then the nodes passed to it are vieded as matching.

  • edge_matcher (callable) – A python callable object that takes 2 positional one for each edge data object. If the return of this function evaluates to True then the edges passed to it are vieded as matching.

  • id_order (bool (default=True)) – If set to true, the algorithm matches the nodes in order specified by their ids. Otherwise, it uses a heuristic matching order based in [VF2] paper.

  • call_limit (int) – An optional bound on the number of states that VF2 algorithm visits while searching for a solution. If it exceeds this limit, the algorithm will stop and return False.

Returns:

True if the 2 graphs are isomorphic False if they are not.

Return type:

bool