TECHNICAL FIELD
The present disclosure is related to graph theory and its applications in solving isomorphism
problem and more specifically, to a method and system for determining the isomorphs for a query
graph from a graph dataset comprising Generalised Johnson graphs, in polynomial time.
BACKGROUND
A graph is a combination of vertices and edges. The edges of graphs can be directed or
undirected. For a graph, an edge connects a pair of vertices. Graphs are extremely diverse. An
example of some of the most symmetric types of the graph are Generalised Johnson graph, srg etc.
Generalised Johnson graphs are a special class of undirected graphs derived from the system of
subsets. Generalised Johnson graphs comprises three variables n, k and i and is denoted by GJ(n,k,i)
where n represents the total number of elements of the set, k represents the size of the subset and i
represents the intersection between the sets. Two vertices are said to be connected in a Generalised
Johnson graph if and only if their intersection has a size of i. Generalised Johnson graphs are highly
symmetrical distance transitive graphs.
FIELD OF INVENTION
Graphs are a unique way of representing information that may pertain to any combinatorial
arrangement or finite algorithmic problems. Graph theory represents the various designing and
representational aspects of many day-to-day computer based applications. The concepts of graph
theory can be incorporated in solving problems related to transportation, electrical circuits,
CAD/CAM, computer networks, chemistry, molecular biology and computer vision etc. Each of
these problems can be represented as a graph G(V, E) where V (finite set of vertices) represents the
junction point in transportation and electrical circuit problems, nodes or routers in computer
network problems, molecules in chemistry, while E (finite set of edges) represents a direct
connection between two vertices, analogously: a road in transportation, molecular bond in
chemistry, electrical wires in electrical circuits and computer networks.
The problem of graph isomorphism is determining whether two given finite graphs are
structurally different or one is just a perturbed variant of the other. More formally, two graphs are
said to be isomorphic if (1) Both the graphs have same number of vertices and edges; (2) The
corresponding vertices in these two graphs have same number of degrees; and (3) There is a
bijective mapping between the vertices of one graph to the vertices of the other graph such that the
2
edge connectivity is maintained.
Graph isomorphism is a classical problem that has gained huge attention in the theory of
computing because of its unresolved complexity status within the polynomial/ non-deterministic
polynomial (P/NP) space. The scientific community is divided among those who deem it “solvable
in Polynomial time (P-time)” and those who do not. However, until today, no efficient method or
system for it has yet been designed or created with P-time complexity. It is the last of the 12
problems (Graph isomorphism, Subgraph homeomorphism {for a fixed graph H}, Graph genus,
Chordal graph completion, Chromatic index, Spanning tree parity problem, Partial order dimension,
Precedence constrained 3-processor scheduling, Linear programming, Total unimodularity,
Composite number, Minimum length triangulation) whose complexity remains unresolved.
DESCRIPTION OF RELATED ART
There are sub-classes of graphs (e.g. Generalised Johnson graph) for which the identification
of isomorphs by the existing methods (in the prior art) is possible in non-deterministic polynomial
time. In the past, many groups have come up with methods to generate solutions for the graph
isomorphism.
Nauty was designed by McKay, B.D. and Piperno, A. (McKay, B.D. and Piperno, A., Journal
of Symbolic Computation, 60 (2014)) using degree information to build a search tree examining
choices not determined by degree information iteratively; and then using graph automorphisms, as
they are found, to prune the search tree. However, this method could not solve Generalised Johnson
graph isomorphism in P-time. The time complexity of this method is where n is number of
vertices in the graph. This makes it very difficult to analyse graphs bigger than a few million
vertices by this method.
Prof. Laszlo Babai came up with a quasi-polynomial time solution that starts by considering
a very small set of vertices in the first graph and colouring them differently. Then it identifies
isomorphism by assuming which vertices in the second graph might correspond to the initial set.
These vertices are coloured in the same hue. The method eventually cycles through all possible
combinations. Once the graphs are coloured, the method can rule out all matchings that pair vertices
of different colours. If the method is successful, the colouring process will divide the graphs into
many chunks of different colours, greatly reducing the number of possible isomorphisms the
method has to consider. Babai has developed a different way to reduce the number of possible
isomorphisms, which works except in one case: when the graph is a “Generalised Johnson graph”.
These are graphs that have so much symmetry that the colouring process and Babai’s further
3
refinements fail to provide enough information to guide the method (Babai L. 2015,
arXiv:1512.03547).
Thus, a method for solving the Generalised Johnson graph in P-time would shift the nature
of graph isomorphism from NP towards P-time and is required. The present disclosure describes a
method and system for solving graph isomorphism for Generalised Johnson graphs in P-time.
OBJECT OF INVENTION
It has already been proposed that there are sub-classes of graphs for which the identification
of isomorphs by the existing methods (in the prior art) is possible in non-deterministic polynomial
time. In the past, many groups have come up with methods to generate solutions for the graph
isomorphism, however, these methods could not solve Generalised Johnson graph isomorphism
within polynomial time. Thus, a method for solving the Generalised Johnson graph isomorphism in
P-time would shift the nature of graph isomorphism from non-deterministic polynomial time
towards polynomial time and is required. The principal object of this invention is to solve the graph
isomorphism for Generalised Johnson graphs in polynomial time.
SUMMARY
The shortcomings in the field of isomorphism with respect to Generalised Johnson graphs
are overcome and additional advantages are provided through the present disclosure. Additional
features and advantages are realized through the techniques of the present disclosure. Other
embodiments and aspects of the disclosure are described in detail herein and are considered a part
of the present disclosure.
The present disclosure provides a method for determination of graph isomorphism for
Generalised Johnson graphs. The process iterates over each member of the graph dataset. It starts by
taking two graphs: the query graph and a member of the graph dataset. The first step in this process
is to identify the number of vertices in the query graph and compare with the vertices of the other
graph. If the number of vertices in both the graphs are equal then the number of edges of both the
graphs are compared with each other. If both the graphs have same number of edges then the girth
of each graph is calculated by taking a vertex (the vertices taken into consideration are maintained
in a visited-list to keep a track of the vertices being already visited) and exploring its directly
connected vertices (neighbours). The list of neighbours are stored in a stack (i.e. last in-first out
order), called neighbour-list. The penultimate vertex (i.e. the vertex visited before the current
4
vertex) is omitted from the stack. The next vertex to be considered is taken from the neighbour-list
of the current vertex and its neighbour-list is updated in the same manner. This process is repeated
recursively until there are one or more vertex/vertices common in the neighbour-list and the visitedlist.
This implies that the path traversed has identified a cyclical structure. The length of this
cyclical structure is equal to the number of intermediate edges traversed while moving from the first
incidence to the last incidence of the common vertex and is stored as the current girth of the graph.
This process progresses until all the vertices of the graph are covered. During this process, the
calculated length for every such cyclical structure is compared with the one stored and whichever is
minimum is stored as the current girth. After all the vertices are covered, the girth stored is
considered as the girth of the graph. If the girth for both the graphs are equal, an exhaustive
calculation of the participation number for each vertex in primary cyclical shapes are performed
(wherein, the primary cyclical shapes are the vertices connected in closed chain, whose length is
equal to the girth, includes overlapping primary cyclical shapes). The primary participation number
for a vertex is the number of primary cyclical shapes in which it is a part. The traversed paths
during the identification of the primary cyclical shapes are stored. In case of Generalised Johnson
graph, the primary participation number itself distinguishes it from other non-isomorphic forms.
During this entire procedure, if at any point of time, the comparisons among different parameters
(the number of vertices, the number of edges, girth, primary participation numbers) between the
graphs differ then the graphs are classified as not isomorphic and that member of the graph dataset
is eliminated. When both the graphs are declared isomorphic by the current disclosure, then the last
step would be to give a one-to-one correspondence of each vertex of the query graph to its
isomorphic form (from the member of the graph dataset). As Generalised Johnson graphs are highly
symmetrical graphs it is impossible to distinguish any vertex from one another in case of isomorphs.
Hence, each vertex of the query graph corresponds to every vertex of its isomorphic form (from the
member of the graph dataset). Labelling is done by taking a vertex from both the graphs and
applying a traversal approach for exploring other vertices according to their neighbour-list. These
vertices are then labelled accordingly.
The present disclosure provides a system for identifying isomorphs for Generalised Johnson
graphs. The system comprises a processing unit and a memory unit. The processing unit is
configured to iterate over each member of the graph dataset. It starts by taking two graphs: the
query graph and a member of the graph dataset. The memory unit is configured to store data
associated with the plurality of vertices and edges connecting the vertices in the graph. The
processing unit is then configured to perform a comparison between the number of vertices in each
graph. If the number of vertices are equal then the comparison between the number of edges for
5
both the graphs are performed by the processing unit. If the number of edges are also equal then the
processing unit is configured to calculate the girth of the graphs. The girth is initialized by the
processing unit as one more than the number of vertices in the graph. The processing unit is
configured to calculate the girth by taking a vertex (the vertices taken into consideration are
maintained in a visited-list, by the memory unit, to keep a track of the vertices being already
visited) and exploring its directly connected vertices (neighbours). The memory unit is configured
to store the list of neighbours in a stack (i.e. last in-first out order), called neighbour-list. The
penultimate vertex (i.e. the vertex visited before the current vertex) is omitted from the stack. The
processing unit is configured to consider the next vertex from the neighbour-list of the current
vertex and its neighbour-list in the memory unit is updated in the same manner. This process is
repeated by the processing unit recursively until there are one or more vertex/vertices common in
the neighbour-list and the visited-list. The length of this cyclical structure is equal to the number of
intermediate edges traversed while moving from the first incidence to the last incidence of the
common vertex and is stored by the processing unit as the current girth of the graph in the memory
unit. This process progresses until all the vertices of the graph are covered by the processing unit.
During this process, the calculated length for every such cyclical structure is compared with the one
stored and whichever is minimum is stored as the current girth. After all the vertices are covered,
the girth stored in the memory unit is the girth of the graph. If the girth for both the graphs are
equal, an exhaustive calculation of the participation number for each vertex in primary cyclical
shapes are then performed by the processing unit (wherein, the primary cyclical shapes are the
vertices connected in closed chain, whose length is equal to the girth, includes overlapping primary
cyclical shapes). The primary participation number for a vertex is calculated by the processing unit
as the number of primary cyclical shapes in which it is a part. The traversed paths during the
identification of the primary cyclical shapes are stored in the memory unit. In case of Generalised
Johnson graph, the primary participation number itself distinguishes it from other non-isomorphic
forms. During this entire procedure, if at any point of time, the comparisons among different
parameters by the processing unit (the number of vertices, number of edges, girth and primary
participation numbers) between the graphs differ, then the graphs are classified as not isomorphic
and that member of the graph dataset is eliminated.
When both the graphs are declared isomorphic by the current disclosure, then the last step
would be to give a one-to-one correspondence of each vertex of the query graph to its isomorphic
form (from the member of the graph dataset) by the processing unit. As Generalised Johnson graphs
are highly symmetrical graphs it is impossible to distinguish any vertex from one another in case of
isomorphs. Hence, each vertex of the query graph corresponds to every vertex of its isomorphic
6
form (from the member of the graph dataset). Labelling is done by the processing unit by taking a
vertex from both the graphs and applying a traversal approach for exploring other vertices
according to their neighbour-list. These vertices are then labelled accordingly and stored in the
memory unit.
The foregoing summary is illustrative only and is not intended to be limiting in any way. In
addition to the illustrative aspects and features described above, further aspects, and features will
become apparent by reference to the drawings and the following detailed description.
BRIEF DESCRIPTION OF THE DRAWINGS
The novel features and characteristics of the disclosure are set forth in the appended claims.
The embodiments of the disclosure itself, however, as well as a preferred mode of use, further
objectives and advantages thereof, will best be understood by reference to the following detailed
description of an illustrative embodiment when read in conjunction with the accompanying
drawings. One or more embodiments are now described, by way of example only, with reference to
the accompanying drawings.
Figure 1 illustrates a system for identifying isomorphs for Generalised Johnson graphs and
strongly regular graphs in accordance with an embodiment of the present disclosure;
Figure 2a and 2b show two graphs which are isomorphic to each other in accordance with
the present disclosure;
Figure 3 shows a graph which is Generalised Johnson graph GJ(4,2,1) with n=4, k=2 and
i=1 also strongly regular SRG(6,4,2,4) with λ=2 and μ=4 with an exemplary embodiment of the
present disclosure; and
Figure 4-7 illustrates primary cyclical shapes (pcs) involving vertex 1 in graph (GJ(4,2,1) /
SRG(6,4,2,4)) in accordance with the present disclosure;
The figures depict embodiments of the disclosure for the purpose of illustration only. One
familiar with the art would readily undertand from the detailed description that alternative
embodiments of the structures and methods illustrated herein may be employed without departing
from the principles of the disclosure described herein.
DETAILED DESCRIPTION
The foregoing has broadly outlined the features and technical advantages of the present
7
disclosure in order that the detailed description of the disclosure that follows may be better
understood. Additional features and advantages of the disclosure will be described hereinafter
which form the subject of the claims of the disclosure. It should be appreciated by those skilled in
the art that the conception and specific aspect disclosed may be readily utilized as a basis for
modifying or designing other structures for carrying out the same purposes of the present
disclosure. It should be also realised by those skilled in the art that such equivalent constructions do
not depart from the spirit, scope and principles of the disclosure as set forth in the appended claims.
The present disclosure is related to a method and system for identification of isomorphs
among Generalised Johnson graphs in polynomial time. A set of two graphs are considered for this
purpose where graph G1 consists of V1 number of vertices and E1 number of edges and graph G2
consists of V2 number of vertices and E2 number of edges with each edge connecting two vertices.
Two graphs are said to be isomorphic to each other if there is a bijective function for one-to-one and
onto mapping. In this disclosure, graphs are considered to be undirected, non-labelled and
unweighted. However, the notion of isomorphism may be applied to all other variants of graph, by
appending the prerequisite to preserve the corresponding additional elements of structure.
Determining whether two graphs, both when are Generalised Johnson graphs, are
isomorphic, is highly complex and there are no existing techniques which solve this anywhere close
to polynomial time. On the other hand, the best existing solution for solving Generalised Johnson
graph isomorphism was given by Nauty with exponential running time complexity. The complexity
of the present disclosure is dependent upon the calculation of primary cyclical shapes (pcs). The
length of pcs is the girth (g). The time required to calculate the girth in worst-case is linear. In the
present disclosure, the length of pcs is bounded between 6. Hence, the run-time complexity is
, where n represents the number of vertices of the graph, which is P-time.
The procedure followed for carrying out the Generalised Johnson graph isomorphism test is
as follows: Two graphs are taken wherein one is a query graph (G1) and the other is a member of the
graph dataset (G2). The graph dataset consists of Generalised Johnson graphs. The process iterates
over each member of the graph dataset. The first process proceeds by determining the number of
vertices of both the graphs G1 and G2 and comparing with each other. If the number of vertices are
equal then the number of edges for both the graphs are deduced and a comparison is made whether
both the graphs have equal number of edges. An edge of a graph is defined as the direct connection
between vertices. If the number of edges of both the graphs G1 and G2 are equal then the girth of
both the graphs are calculated. Girth of a graph is defined as the length of the shortest cycle
contained in the graph. Girth of each graph is calculated by taking a vertex (the vertices taken into
8
consideration are maintained in a visited-list to keep a track of the vertices being already visited)
and exploring its directly connected vertices (neighbours). The list of neighbours are stored in a
stack (i.e. last in-first out order), called neighbour-list. The penultimate vertex (i.e. the vertex visited
before the current vertex) is omitted from the stack. The next vertex to be considered is taken from
the neighbour-list of the current vertex and its neighbour-list is updated in the same manner. This
process is repeated recursively until there are one or more vertex/vertices common in neighbour-list
and visited-list. This implies that the path traversed has identified a cyclical structure. The length of
this cyclical structure is equal to the number of intermediate edges traversed while moving from the
first incidence to the last incidence of the common vertex and is stored as the current girth of the
graph. This process progresses until all the vertices of the graph are covered. During this process,
the calculated length for every such cyclical structure is compared with the one stored and
whichever is minimum is stored as the current girth. After all the vertices are covered, the girth
stored is considered as the girth of the graph.
If the girth for both the graphs G1 and G2 are equal then the primary participation number of
each vertex in the formation of entire set of primary cyclical shapes (pcs) of which it is a part, is
calculated and stored. This is calculated to gain the knowledge of the organization of the graph. The
arrangement of cycles in a graph constitutes the entire organization of the graph in symmetrical
graphs. Primary cyclical shapes are the minimum circular arrangement of vertices connected by
edges. Its length is equal to the girth of the graph and includes overlapping primary cyclical shapes.
The traversed paths during the identification of the primary cyclical shapes are stored. If two graphs
are isomorphic then the arrangement of the shortest cycles in the graphs must also be the same.
Hence, the participation number of each vertex in the formation of pcs should be the same. In case
of Generalised Johnson graph, the primary participation number itself distinguishes it from other
non-isomorphic forms. The traversed paths during the identification of the pcs are stored. If the
participation numbers of pcs for each vertex are same for both the graphs then the graphs are
classified as isomorphic.
During this entire procedure, if at any point of time, the comparisons among different
parameters (the number of vertices, number of edges, girth and primary participation numbers)
between the graphs differ, then the graphs are classified as not isomorphic and that member of the
graph dataset is eliminated.
When G1 and G2 are declared isomorphic by the current disclosure, then the last step would
be to give a one-to-one correspondence of each vertex of G1 to G2. As Generalised Johnson graphs
are highly symmetrical graphs it is impossible to distinguish any vertex from one another in case of
9
isomorphs. Hence, each vertex of G1 corresponds to every vertex of G2. Labelling is done by taking
a vertex from both the graphs and applying a traversal approach for exploring other vertices
according to their neighbour-list. These vertices are then labelled accordingly.
Figure 1 illustrates a system 100 for identifying isomorphs among Generalised Johnson
graphs in accordance with an embodiment of the present disclosure. The system comprises a
processing unit 103 and a memory unit 105. The memory unit 105 is configured to store data
associated with the plurality of vertices and edges connecting the vertices in the graph. The
processing unit 103 is then configured to perform a comparison between the number of vertices in
each graph. If the number of vertices equal then the comparison between the number of edges for
both the graphs are performed by the processing unit 103. If the number of edges are also equal then
the processing unit 103 is configured to calculate the girth of the graphs. The girth is initialized by
the processing unit 103 as one more than the number of vertices in the graph. The processing unit
103 is configured to calculate the girth by taking a vertex (the vertices taken into consideration are
maintained in a visited-list, by the memory unit 105, to keep a track of the vertices being already
visited) and exploring its directly connected vertices (neighbours). The memory unit 105 is
configured to store the list of neighbours in a stack (i.e. last in-first out order), called neighbour-list.
The penultimate vertex (i.e. the vertex visited before the current vertex) is omitted from the stack.
The processing unit 103 is configured to consider the next vertex from the neighbour-list of the
current vertex and its neighbour-list in the memory unit 105 is updated in the same manner. This
process is repeated by the processing unit 103 recursively until there are one or more vertex/vertices
common in neighbour-list and visited-list. The length of this cyclical structure is equal to the
number of intermediate edges traversed while moving from the first incidence to the last incidence
of the common vertex and is stored by the processing unit 103 as the current girth of the graph in
the memory unit 105. This process progresses until all the vertices of the graph are covered by the
processing unit 103. During this process, the calculated length for every such cyclical structure is
compared with the one stored in the memory unit 105 and whichever is minimum is stored as the
current girth. After all the vertices are covered, the girth stored in the memory unit 105 is the girth
of the graph. If the girth for both the graphs are equal, an exhaustive calculation of the participation
number for each vertex in primary cyclical shapes are then performed by the processing unit 103
(wherein, the primary cyclical shapes are the vertices connected in closed chain, whose length is
equal to girth, includes overlapping primary cyclical shapes. The primary participation number for a
vertex is calculated by the processing unit 103 as the number of primary cyclical shapes in which it
is a part. The traversed paths during the identification of the primary cyclical shapes are stored in
the memory unit 105. In case of Generalised Johnson graph, the primary participation number itself
10
distinguishes it from other non-isomorphic forms and the graphs are classified as isomorphic by the
system 100. When both the graphs are declared isomorphic by the current disclosure, then the last
step would be to give a one-to-one correspondence of each vertex of the query graph to its
isomorphic form (from the member of the graph dataset) by the processing unit 103. Generalised
Johnson graphs are highly symmetrical graphs it is impossible to distinguish any vertex from one
another in case of isomorphs. Hence, each vertex of the query graph corresponds to every vertex of
its isomorphic form (from the member of the graph dataset). Labelling is done by the processing
unit 103 by taking a vertex from both the graphs and applying a traversal approach for exploring
other vertices according to their neighbour-list. These vertices are then labelled accordingly and
stored in the memory unit 105. During this entire procedure, if at any point of time, the comparisons
among different parameters (the number of vertices, number of edges, girth and primary
participation numbers) between the graphs differ, then the graphs are classified as not isomorphic
by the processing unit 103 and that member of the graph dataset is eliminated.
Figure 2 depicts two simple graphs with 5 vertices and 5 edges. Figure 2a and 2b are tested
for isomorphism. As clear from the figures, both have equal number of vertices and edges. If
checked for correspondence, 1→a, 2→c, 3→e, 4→b, 5→d. Hence, there is a bijective one-to-one
and onto mapping for both the graphs. Therefore, by the definition of graph isomorphism, both the
graphs in Figure 2a and 2b are isomorphic to each other.
Figure 3 shows a graph (GJ(n,k,i) / SRG(v,d,λ,μ)). In the current figure, the graph is a
Generalised Johnson graph where n=4 represents the total number of elements of the set, k=2
represents the size of the subset and i=1 intersection among subsets. The number of vertices
possible in GJ(4, 2, 1) is given by 4C2 . Hence, the number of vertices in this graph is equal to 6. In
the current figure, the graph is also a strongly regular graph where v=6, d=4, λ=2 and μ=4
represents the number of vertices in the graph, the degrees of each vertex of the graph, the common
neighbours between every adjacent pair of vertices and the common neighbours between every nonadjacent
pair of vertices, respectively. The girth calculated for this graph is 3. Table 1 illustrates the
procedure for calculation of girth for the graph represented in Figure 3. The current girth is
initialised to 7(one more than the number of vertices).
Current
Node Neighbour Parent Visited Unfinished Current Girth
1 2 3 5 6 - 1 2 3 5 6 7
6 1 2 4 5 1 1 6 3 2 4 5 7
5 1 3 4 6 6 1 6 5 2 1 3 4 7
4 2 3 5 6 5 1 6 5 4 1 2 3 Min(3, 7) = 3
11
3 1 2 4 5 4 1 6 5 4 3 2 Min(5, 3, 3) = 3
2 1 3 4 6 3 1 6 5 4 3 2 - Min(6, 3, 5, 3) = 3
Table 1: Table showing the calculation of girth of J(4,2)
Figure 4-7 depicts a graph whose pcs are marked. The total participation number of vertex 1
in the formation of primary cyclical shapes (triangles as in this case) in the figures are as follows: 1-
2-3, 1-2-6, 1-3-5, 1-3-2, 1-5-3, 1-5-6, 1-6-2, 1-6-5, 2-1-3, 2-1-6, 2-3-1, 2-6-1, 3-1-2, 3-1-5, 3-2-1, 3-
5-1, 5-1-3, 5-1-6, 5-3-1, 5-6-1, 6-1-2, 6-1-5, 6-2-1, 6-5-1. 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2 and 3-2-1
illustrate the overlapping primary cyclical shapes. Hence, the total participation number of vertex 1
in the formation of primary cyclical shapes is equal to 24. Likewise, the total participation number
for each of the vertices is calculated and stored. If two graphs are isomorphic then the arrangement
of the shortest cycles in the graphs must also be the same. Hence, the participation number of each
vertex in the formation of pcs should be the same. In case of Generalised Johnson graphs, the
primary participation number itself distinguishes it from other non-isomorphic forms.
Referral Numberals:
Reference Number Description
100 System
103 Processing Unit
105 Memory Unit
12

CLAIMS
We claim:
1. A method for identification of isomorphs for a query graph from a graph dataset in polynomial
time; comprising:
determining the number of vertices of the query graph and the members of the graph
dataset;
comparing the number of vertices of the query graph with that of the members of the
graph dataset;
eliminating those graphs from the graph dataset which have different number of
vertices from the query graph;
determining the number of edges of the query graph and the members of the graph
dataset;
comparing the number of edges of the query graph with that of the members of the
graph dataset;
eliminating those graphs from the graph dataset which have different number of
edges from the query graph;
calculating the girths for the query graph and the members of the graph dataset;
comparing the girth of the query graph with that of the members of the graph dataset;
eliminating those graphs from the graph dataset which have different girths from the
query graph;
identifying a primary participation number for each vertex, in the query graph and
for every member of the graph dataset;
13
labelling the vertices of the query graph and members of the graph dataset;
identifying the vertex correspondence between the query graph and for every
member of the graph dataset; and
obtaining the isomorphs for the query graph by eliminating those graphs from the
graph dataset which have non-equivalent vertex correspondence.
2. The method as claimed in claim 1, wherein the query graph must be Generalised Johnson graph.
3. The method as claimed in claim 1, wherein the primary participation number for a vertex is
obtained upon calculating all primary cyclical shapes in which it is participating, includes
overlapping primary cyclical shapes.
4. The method as claimed in claim 1, wherein the vertices are labelled by their respective primary
and secondary participation numbers.
5. The method as claimed in claim 1, wherein the vertex correspondence is identified by comparing
the labels of vertices.
6. A system for identification of isomorphs for a query graph from a graph dataset in polynomial
time; comprising:
a memory unit configured to store data associated with plurality of vertices and edges
connecting the plurality of vertices in the query graph; and
a processing unit communicatively connected to the memory unit to obtain the data
associated with plurality of vertices and edges connecting the plurality of vertices in the
query graph, the processing unit being capable of:
determining the number of vertices of the query graph and the members of the graph
dataset;
comparing the number of vertices of the query graph with that of the members of the
14
graph dataset;
eliminating those graphs from the graph dataset which have different number of
vertices from the query graph;
determining the number of edges of the query graph and the members of the
graph dataset;
comparing the number of edges of the query graph with that of the members of the
graph dataset;
eliminating those graphs from the graph dataset which have different number of
edges from the query graph;
calculating the girths for the query graph and the members of the graph dataset;
comparing the girth of the query graph with that of the members of the graph
dataset;
eliminating those graphs from the graph dataset which have different girths
from the query graph;
identifying a primary participation number for each vertex, in the query graph and
for every member of the graph dataset;
labelling the vertices of the query graph and members of the graph dataset;
identifying the vertex correspondence between the query graph and for every
member of the graph dataset; and
obtaining the isomorphs for the query graph by eliminating those graphs from the
graph dataset which have non-equivalent vertex correspondence.
7. The system as claimed in claim 6, wherein the query graph must be Generalised Johnson graph.
15
8. The system as claimed in claim 6, wherein the processing unit obtains the primary participation
number for a vertex is by calculating all primary cyclical shapes in which it is participating,
includes overlapping primary cyclical shapes and stores these in the memory unit.
9. The system as claimed in claim 6, wherein the processing unit labels the vertices by their
respective primary participation numbers and stores them in the memory unit.
10. The system as claimed in claim 6, wherein the processing unit identifies the vertex
correspondence by comparing the labels of vertices and stores them in the memory