isisomorphic
Determine whether two graphs are isomorphic
Description
tf = isisomorphic(
returns logical
G1,G2
)1
(true
) if a graph isomorphism exists
between graphs G1
and G2
; otherwise, it
returns logical 0
(false
).
tf = isisomorphic(
specifies additional options with one or more name-value pair arguments. For
example, you can specify G1,G2
,Name,Value
)'NodeVariables'
and a list of node
variables to indicate that the isomorphism must preserve these variables to be
valid.
Examples
Compare Graphs
Create and plot two directed graphs, and then determine if they are isomorphic.
G1 = digraph([1 1 1 2 3 4],[2 3 4 4 4 1]); G2 = digraph([3 3 3 2 1 4],[1 4 2 3 2 2]); subplot(1,2,1) plot(G1) subplot(1,2,2) plot(G2)
isisomorphic(G1,G2)
ans = logical
1
Compare Graphs with Different Labels and Layouts
Create and plot two graphs, G1
and G2
.
G1 = graph([1 1 1 2 2 3 3 4 5 5 7 7],[2 4 5 3 6 4 7 8 6 8 6 8]); plot(G1,'XData',[1 4 4 1 2 3 3 2],'YData',[4 4 1 1 3 3 2 2])
G2 = graph({'a' 'a' 'a' 'b' 'b' 'b' 'c' 'c' 'c' 'd' 'd' 'd'}, ... {'g' 'h' 'i' 'g' 'h' 'j' 'g' 'i' 'j' 'h' 'i' 'j'}); plot(G2,'XData',[1 2 2 2 1 2 1 1],'YData',[4 4 3 2 3 1 2 1])
Determine whether an isomorphism exists for G1
and G2
. The result indicates that the graphs are structurally the same despite their different labels and layouts.
tf = isisomorphic(G1,G2)
tf = logical
1
Preserve Node Properties in Isomorphism Comparison
Use two different comparisons to determine if there is an isomorphism relation between two graphs. One of the comparisons preserves a node property, while the other ignores it.
Create two similar graphs. Add a node property Color
to each of the graphs.
G1 = graph({'d' 'e' 'f'},{'e' 'f' 'd'}); G1.Nodes.Color = {'red' 'red' 'blue'}'; G2 = graph({'a' 'b' 'c'},{'b' 'c' 'a'}); G2.Nodes.Color = {'blue' 'blue' 'red'}';
Plot the graphs side-by-side in the same figure. Color the nodes red that have Color = 'red'
.
subplot(1,2,1) p1 = plot(G1); highlight(p1,{'d' 'e'},'NodeColor','r') subplot(1,2,2) p2 = plot(G2); highlight(p2,'c','NodeColor','r')
Determine if the graphs are isomorphic, ignoring the Color
property.
tf = isisomorphic(G1,G2)
tf = logical
1
Determine if the graphs are isomorphic and preserve the value of the Color
property in the comparison. In this case, there is no isomorphism since the Color
property of each graph contains different numbers of 'red'
and 'blue'
values.
tf = isisomorphic(G1,G2,'NodeVariables','Color')
tf = logical
0
Input Arguments
G1,G2
— Input graphs (as separate arguments)
graph
objects | digraph
objects
Name-Value Arguments
Specify optional pairs of arguments as
Name1=Value1,...,NameN=ValueN
, where Name
is
the argument name and Value
is the corresponding value.
Name-value arguments must appear after other arguments, but the order of the
pairs does not matter.
Before R2021a, use commas to separate each name and value, and enclose
Name
in quotes.
Example: tf = isisomorphic(G1,G2,'NodeVariables',{'Var1'
'Var2'})
EdgeVariables
— Edge variables to preserve
character vector | string scalar | cell array of character vectors | string array
Edge variables to preserve, specified as the comma-separated pair
consisting of 'EdgeVariables'
and a character vector,
string scalar, cell array of character vectors, or string array. Use
this option to specify one or more edge variables that are in both
G1.Edges
and G2.Edges
. The
isomorphism comparison must preserve the specified edge variables in
order to be valid. For multigraphs with multiple edges between the same
two nodes, the ordering of the edge variables for the same node pair is
irrelevant.
Data Types: char
| string
| cell
NodeVariables
— Node variables to preserve
character vector | string scalar | cell array of character vectors | string array
Node variables to preserve, specified as the comma-separated pair
consisting of 'NodeVariables'
and a character vector,
string scalar, cell array of character vectors, or string array. Use
this option to specify one or more node variables that are in both
G1.Nodes
and G2.Nodes
. The
isomorphism comparison must preserve the specified node variables in
order to be valid.
Data Types: char
| string
| cell
More About
Graph Isomorphism
Two graphs, G1
and G2
, are
isomorphic if there exists a permutation of the nodes P
such that
reordernodes(G2,P)
has the same structure as
G1
.
Two graphs that are isomorphic have similar structure. For example, if a graph contains one cycle, then all graphs isomorphic to that graph also contain one cycle.
Extended Capabilities
Thread-Based Environment
Run code in the background using MATLAB® backgroundPool
or accelerate code with Parallel Computing Toolbox™ ThreadPool
.
Version History
Introduced in R2016b
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)