could_be_isomorphic

could_be_isomorphic(G1, G2, *, properties='dtc')

Returns False if graphs are definitely not isomorphic. True does NOT guarantee isomorphism.

Parameters:

G1, G2graphs

The two graphs G1 and G2 must be the same type.

propertiesstr, default=”dct”

Determines which properties of the graph are checked. Each character indicates a particular property as follows:

• if "d" in properties: degree of each node

• if "t" in properties: number of triangles for each node

• if "c" in properties: number of maximal cliques for each node

Unrecognized characters are ignored. The default is "dtc", which compares the sequence of (degree, num_triangles, num_cliques) properties between G1 and G2. Generally, properties="dt" would be faster, and properties="d" faster still. See Notes for additional details on property selection.

Returns:

bool

A Boolean value representing whether G1 could be isomorphic with G2 according to the specified properties.

Notes

The triangle sequence contains the number of triangles each node is part of. The clique sequence contains for each node the number of maximal cliques involving that node.

Some properties are faster to compute than others. And there are other properties we could include and don’t. But of the three properties listed here, comparing the degree distributions is the fastest. The “triangles” property is slower (and also a stricter version of “could”) and the “maximal cliques” property is slower still, but usually faster than doing a full isomorphism check.