could_be_isomorphic#
- could_be_isomorphic(G1, G2, *, properties='dtc')[source]#
Returns False if graphs are definitely not isomorphic. True does NOT guarantee isomorphism.
- Parameters:
- G1, G2graphs
The two graphs
G1
andG2
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"
inproperties
: degree of each nodeif
"t"
inproperties
: number of triangles for each nodeif
"c"
inproperties
: 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 betweenG1
andG2
. Generally,properties="dt"
would be faster, andproperties="d"
faster still. See Notes for additional details on property selection.
- Returns:
- bool
A Boolean value representing whether
G1
could be isomorphic withG2
according to the specifiedproperties
.
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.