isomorphism (biograph)
(Removed) Find isomorphism between two biograph objects
The function has been removed. Use the isomorphism
function of graph
or digraph
instead.
Syntax
[
Isomorphic
, Map
]
= isomorphism(BGObj1
, BGObj2
)
[Isomorphic
, Map
]
= isomorphism(BGObj1
, BGObj2
,'Directed', DirectedValue
)
Arguments
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. |
Description
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.
References
[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).
Version History
Introduced in R2006bSee Also
isomorphism
| graph
| digraph