what-when-how
In Depth Tutorials and Information
C3
C2
u
C1
Figure 10.3
Neighborhood and its components (the dashed edges are just for
illustrationpurposeandarenotintheneighborhoodsubgraph).(FromBinZhou
andJianPei.DataEngineering,2008.
IEEE 24th International Conference on ICDE
2008
.April7-12,2008,pp.506-515.)
he
DFScode
of
G
with respect to
T
,
code
(
G,T
), is a list of all edges in
E
(
G
)
according to the order
≺
. For instance, the DFS code in Figure 4b is
=
−
−
−
1
code G T
(
,
)
(
v v x x
,
,
,
)
(
v v
,
,
x z
,
)
(
v v z
,
,
,
x
)
(
v v x y
,
,
,
) ,
1
0
1
1
2
2
0
3
where an edge is denoted as
(
v v
,
,
� �
.
(
v
),
(
v
))
i
j
i
j
In Figure 4c,
code G T
(
,
)
=
(
v v y x
,
,
,
)
−
(
v v
,
,
x x
,
)
−
(
v v x
,
,
,
z
)
−
3
(
v v z x
,
,
,
) .
2
0
1
1
2
2
3
1
A predefined linear order in the label set
L
can produce the order of edges which
determines the lexically
minimum DFS code
, denoted as
DFS
(
G
). For example,
DFS G
=
=
1 2 1
)
in Figure 10.4. he prop-
erty of minimum DFS code (two graphs
G
and
G
'
are isomorphic if and only if
DFS G
(
) min(
code G T code G T
(
,
),
(
,
))
code G T
(
,
( ) ( '
=
[5]) is useful for coding the components of the neighborhood
of a vertex. he minimum DFS code of all components can be combined to one
code according to the neighborhood component order.
Given two neighborhood components
C
i
and
C
j
in
Neighbor
G
(
u
),
C
i
≺
if (a)
|
V
(
C
i
)
<
V
(
C
j
)| ; or (b) |
V
(
C
i
)
=
V
(
C
j
)| and |
E
(
C
i
)
<
E
(
C
j
)|; or (c) |
V
(
C
i
)
=
V
(
C
j
)|
|
E
(
C
i
)
=
E
(
C
j
)|, and |
DFS
(
C
i
)
<
DFS
(
C
j
)|. hus, the neighborhood component code
of
Neighbor u
DFS G
=
G
( )
is a vector
NCC u
( )
(
DFS C
(
),...,
DFS C
m
(
))
where
C
1
,...,
C
m
1
are the neighborhood components of
Neighbor u
G
( )
, i.e.,
Neighbor u
( )
=
∪
1
C
,
i
m
G
i
≺
for
1
≤ < ≤
=
C
C
i
j m
. For example,
NCC u
( )
(
DFS C DFS C DFS C
(
),
(
),
(
))
i
j
1
2
3
in Figure 10.4. According to the property of minimum DFS codes, two neigh-
borhoods
Neighbor u
G
( )
and
Neighbor v
G
( )
are isomorphic if and only if
