Find isomorphism between two biograph objects
[
Isomorphic
, Map
]
= isomorphism(BGObj1
, BGObj2
)
[Isomorphic
, Map
]
= isomorphism(BGObj1
, BGObj2
,'Directed', DirectedValue
)
BGObj1 | Biograph object created by biograph (object
constructor). |
BGObj2 | Biograph object created by biograph (object
constructor). |
DirectedValue | Property that indicates whether the graphs are directed or
undirected. Enter false when both BGObj1 and BGObj2 produce
undirected graphs. In this case, the upper triangles of the sparse
matrices extracted from BGObj1 and BGObj2 are
ignored. Default is true , meaning that both graphs
are directed. |
Tip For introductory information on graph theory functions, see Graph Theory Functions. |
[
returns logical 1 (Isomorphic
, Map
]
= isomorphism(BGObj1
, BGObj2
)true
) in Isomorphic
if
two N-by-N adjacency matrices extracted from biograph objects BGObj1
and BGObj2
are
isomorphic graphs, and logical 0 (false
) otherwise.
A graph isomorphism is a 1-to-1 mapping of the nodes in the graph
from BGObj1
and the nodes in the graph
from BGObj2
such that adjacencies are preserved.
Return value Isomorphic
is Boolean. When Isomorphic
is true
, Map
is
a row vector containing the node indices that map from BGObj2
to BGObj1
.
When Isomorphic
is false
,
the worst-case time complexity is O(N!)
, where N
is
the number of nodes.
[
indicates whether the graphs are directed or undirected. Set Isomorphic
, Map
]
= isomorphism(BGObj1
, BGObj2
,'Directed', DirectedValue
)DirectedValue
to false
when
both BGObj1
and BGObj2
produce
undirected graphs. In this case, the upper triangles of the sparse
matrices extracted from BGObj1
and BGObj2
are
ignored. The default is true
, meaning that both
graphs are directed.
[1] Fortin, S. (1996). The Graph Isomorphism Problem. Technical Report, 96-20, Dept. of Computer Science, University of Alberta, Edomonton, Alberta, Canada.
[2] McKay, B.D. (1981). Practical Graph Isomorphism. Congressus Numerantium 30, 45-87.
[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).
allshortestpaths
| biograph
| conncomp
| graphisomorphism
| isdag
| isspantree
| maxflow
| minspantree
| shortestpath
| topoorder
| traverse