Graph Isomorphism 2

          First in thread      Previous in thread

An annotated example

Here is an annotated version of the example of the construction of the canonical representation of a graph that was presented at the end of the previous post. The algorithm responsible for this output will be sketched later in this post. Discussion of 'medial analysis' will be found after the algorithm sketch. Since the degree signature is also the length of the adjacency signature, it has been omitted where possible for the sake of clarity.

Comments have been added as lines that begin with '//' and usually follow the output being commented upon.

Augmented Adjacency Sets for Graph0

0  : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14 }
1  : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14 }
2  : { 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14 }
3  : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
4  : { 0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14 }
5  : { 0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14 }
6  : { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 13, 14 }
7  : { 0, 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14 }
8  : { 0, 1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14 }
9  : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
10 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }
11 : { 1, 2, 3, 5, 7, 8, 9, 10, 11, 13, 14 }
12 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14 }
13 : { 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13 }
14 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14 }

//  Each line in the list of augmented adjacency sets starts with a label for node X
//  and is followed by the set of the labels of those nodes that are adjacent to 
//  node X, including the label of node X. This inclusion of the label of X in the
//  set makes set operations easier and is the 'augmented' in 'augmented adjacency
//  set'.


Application of the algorithm for constructing the canonical representation of Graph0

distributing nodes into their initial equivalence classes based upon their degree
    ( the degree of each node is the index of the class it will be placed in )

//  The IDs of classes that aren't assigned any nodes by this initial distribution
//  are enqueued in ascending order in an AvailableClassIDs queue (smallest class ID
//  at the head of the queue). 

enqueuing signature-refresh tasks for each of the equivalence cases that are in use

//  The SignatureRefreshTasks queue contains the IDs of all classes whose node 
//  signatures should be refreshed. The head of the queue is the first element 
//  within the parentheses. A class ID is enqueued only if it is not already in the
//  queue. A class ID is dequeued from the left at the beginning of each task and
//  specifies the ID of the class that will have its nodes' signatures refreshed
//  during the task. 


phase 1

//  A second phase will be necessary only if the medial analysis that is performed
//  at the end of phase 1 determines that it is necessary. It is not necessary in
//  this example.

equivalence classes

  10 : degree sig     [ 10 ]
       graph0 members { 11, 13 }

  11 : degree sig     [ 11 ]
       graph0 members { 7 }

  12 : degree sig     [ 12 ]
       graph0 members { 2, 4, 5, 6, 8, 12 }

  13 : degree sig     [ 13 ]
       graph0 members { 0, 1, 14 }

  14 : degree sig     [ 14 ]
       graph0 members { 3, 9, 10 }


signature-refresh task queue: ( 10 11 12 13 14 )

begin task 1: refresh the signatures of the 2 nodes in equivalence class 10
    moving node 13 to equivalence class 0
    moving node 11 to equivalence class 1
    equivalence class 10 is no longer in use
    enqueuing refresh tasks for equivalence classes ( 0 1 )
        because their signatures refer to retired equivalence class 10
end task

//  The first thing that happens in a task is the construction of new signatures
//  for each node in the task class (class 10 in task 1). The adjacency signature
//  for a node X is formed by constructing a list of the IDs of the classes that
//  contain each of the nodes that are adjacent to X, then by sorting this list
//  of class IDs into ascending order.

//  The sorting of new signatures prior to assigning them to new classes helps to
//  keep this algorithm from being label-dependent.

//  If every node in the task class has the same new refreshed signature, the nodes
//  are left in the current task class and the task class is assigned the common
//  new signature.

//  If some nodes in the task class have different refreshed signatures, they can
//  no longer belong to the same class. The task class will be retired after its
//  nodes are moved to two or more new classes. The list of new signatures are 
//  sorted into ascending order and assigned to new classes whose IDs are dequeued
//  from the AvailableClassIDs queue. Each node in the task class is then moved to
//  the new class that has the node's new signature. The ID of the task class is
//  enqueued on the AvailableClassIDs queue and the task class is retired.

//  If the task class needs to be split and retired, all classes whose signatures
//  contain references to the task class need to be scheduled for signature
//  refreshment by enqueing their class IDs on the SignatureRefreshTasks queue in
//  ascending order.

equivalence classes

   0 : adjacency sig  [ 10 11 12 12 12 12 13 14 14 14 ]
       graph0 members { 13 }

   1 : adjacency sig  [ 10 11 12 12 12 13 13 14 14 14 ]
       graph0 members { 11 }

  11 : degree sig     [ 11 ]
       graph0 members { 7 }

  12 : degree sig     [ 12 ]
       graph0 members { 2, 4, 5, 6, 8, 12 }

  13 : degree sig     [ 13 ]
       graph0 members { 0, 1, 14 }

  14 : degree sig     [ 14 ]
       graph0 members { 3, 9, 10 }

//  The ID of each class is shown at the left of the first line of each class's
//  description. Classes that are not in use are not shown.


signature-refresh task queue: ( 11 12 13 14 0 1 )

begin task 2: refresh the signature of the node in equivalence class 11
end task

//  If the task class contains only one node, there is no possibility of the task 
//  class being split and retired.

signature-refresh task queue: ( 12 13 14 0 1 )

begin task 3: refresh the signatures of the 6 nodes in equivalence class 12
    moving node 5 to equivalence class 2
    moving node 8 to equivalence class 2
    moving node 6 to equivalence class 3
    moving node 4 to equivalence class 4
    moving node 2 to equivalence class 5
    moving node 12 to equivalence class 6
    equivalence class 12 is no longer in use
    enqueuing refresh tasks for equivalence classes ( 2 3 4 5 6 11 )
        because their signatures refer to retired equivalence class 12
end task

equivalence classes

   0 : adjacency sig  [ 10 11 12 12 12 12 13 14 14 14 ]
       graph0 members { 13 }

   1 : adjacency sig  [ 10 11 12 12 12 13 13 14 14 14 ]
       graph0 members { 11 }

   2 : adjacency sig  [ 0 1 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 5, 8 }

   3 : adjacency sig  [ 0 11 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 6 }

   4 : adjacency sig  [ 0 12 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 4 }

   5 : adjacency sig  [ 1 11 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 2 }

   6 : adjacency sig  [ 11 12 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 12 }

  11 : adjacency sig  [ 0 1 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 7 }

  13 : degree sig     [ 13 ]
       graph0 members { 0, 1, 14 }

  14 : degree sig     [ 14 ]
       graph0 members { 3, 9, 10 }


signature-refresh task queue: ( 13 14 0 1 2 3 4 5 6 11 )

begin task 4: refresh the signatures of the 3 nodes in equivalence class 13
    moving node 0 to equivalence class 7
    moving node 1 to equivalence class 8
    moving node 14 to equivalence class 8
    equivalence class 13 is no longer in use
    enqueuing refresh tasks for equivalence classes ( 7 8 )
        because their signatures refer to retired equivalence class 13
end task

equivalence classes

   0 : adjacency sig  [ 10 11 12 12 12 12 13 14 14 14 ]
       graph0 members { 13 }

   1 : adjacency sig  [ 10 11 12 12 12 13 13 14 14 14 ]
       graph0 members { 11 }

   2 : adjacency sig  [ 0 1 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 5, 8 }

   3 : adjacency sig  [ 0 11 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 6 }

   4 : adjacency sig  [ 0 12 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 4 }

   5 : adjacency sig  [ 1 11 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 2 }

   6 : adjacency sig  [ 11 12 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 12 }

   7 : adjacency sig  [ 0 2 2 3 4 5 6 11 13 13 14 14 14 ]
       graph0 members { 0 }

   8 : adjacency sig  [ 1 2 2 3 4 5 6 11 13 13 14 14 14 ]
       graph0 members { 1, 14 }

  11 : adjacency sig  [ 0 1 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 7 }

  14 : degree sig     [ 14 ]
       graph0 members { 3, 9, 10 }


signature-refresh task queue: ( 14 0 1 2 3 4 5 6 11 7 8 )

begin task 5: refresh the signatures of the 3 nodes in equivalence class 14
    all nodes in equivalence class 14 have the same new signature
end task

signature-refresh task queue: ( 0 1 2 3 4 5 6 11 7 8 )

begin task 6: refresh the signature of the node in equivalence class 0
end task

signature-refresh task queue: ( 1 2 3 4 5 6 11 7 8 )

begin task 7: refresh the signature of the node in equivalence class 1
end task

signature-refresh task queue: ( 2 3 4 5 6 11 7 8 )

begin task 8: refresh the signatures of the 2 nodes in equivalence class 2
    moving node 8 to equivalence class 9
    moving node 5 to equivalence class 15
    equivalence class 2 is no longer in use
    enqueuing refresh tasks for equivalence classes ( 0 1 9 14 15 )
        because their signatures refer to retired equivalence class 2
end task

equivalence classes

   0 : adjacency sig  [ 1 2 2 3 4 7 11 14 14 14 ]
       graph0 members { 13 }

   1 : adjacency sig  [ 0 2 2 5 8 8 11 14 14 14 ]
       graph0 members { 11 }

   3 : adjacency sig  [ 0 11 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 6 }

   4 : adjacency sig  [ 0 12 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 4 }

   5 : adjacency sig  [ 1 11 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 2 }

   6 : adjacency sig  [ 11 12 12 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 12 }

   7 : adjacency sig  [ 0 2 2 3 4 5 6 11 13 13 14 14 14 ]
       graph0 members { 0 }

   8 : adjacency sig  [ 1 2 2 3 4 5 6 11 13 13 14 14 14 ]
       graph0 members { 1, 14 }

   9 : adjacency sig  [ 0 1 2 3 4 6 7 8 8 14 14 14 ]
       graph0 members { 8 }

  11 : adjacency sig  [ 0 1 12 12 12 13 13 13 14 14 14 ]
       graph0 members { 7 }

  14 : adjacency sig  [ 0 1 2 2 3 4 5 6 7 8 8 11 14 14 ]
       graph0 members { 3, 9, 10 }

  15 : adjacency sig  [ 0 1 2 4 5 6 7 8 8 14 14 14 ]
       graph0 members { 5 }


signature-refresh task queue: ( 3 4 5 6 11 7 8 0 1 9 14 15 )

begin task 9: refresh the signature of the node in equivalence class 3
end task

signature-refresh task queue: ( 4 5 6 11 7 8 0 1 9 14 15 )

begin task 10: refresh the signature of the node in equivalence class 4
end task

signature-refresh task queue: ( 5 6 11 7 8 0 1 9 14 15 )

begin task 11: refresh the signature of the node in equivalence class 5
end task

signature-refresh task queue: ( 6 11 7 8 0 1 9 14 15 )

begin task 12: refresh the signature of the node in equivalence class 6
end task

signature-refresh task queue: ( 11 7 8 0 1 9 14 15 )

begin task 13: refresh the signature of the node in equivalence class 11
end task

signature-refresh task queue: ( 7 8 0 1 9 14 15 )

begin task 14: refresh the signature of the node in equivalence class 7
end task

signature-refresh task queue: ( 8 0 1 9 14 15 )

begin task 15: refresh the signatures of the 2 nodes in equivalence class 8
    all nodes in equivalence class 8 have the same new signature
end task

signature-refresh task queue: ( 0 1 9 14 15 )

begin task 16: refresh the signature of the node in equivalence class 0
end task

signature-refresh task queue: ( 1 9 14 15 )

begin task 17: refresh the signature of the node in equivalence class 1
end task

signature-refresh task queue: ( 9 14 15 )

begin task 18: refresh the signature of the node in equivalence class 9
end task

signature-refresh task queue: ( 14 15 )

begin task 19: refresh the signatures of the 3 nodes in equivalence class 14
    all nodes in equivalence class 14 have the same new signature
end task

signature-refresh task queue: ( 15 )

begin task 20: refresh the signature of the node in equivalence class 15
end task

equivalence classes

   0 : adjacency sig  [ 1 3 4 7 9 11 14 14 14 15 ]
       graph0 members { 13 }

   1 : adjacency sig  [ 0 5 8 8 9 11 14 14 14 15 ]
       graph0 members { 11 }

   3 : adjacency sig  [ 0 4 5 6 7 8 8 9 11 14 14 14 ]
       graph0 members { 6 }

   4 : adjacency sig  [ 0 3 5 6 7 8 8 9 14 14 14 15 ]
       graph0 members { 4 }

   5 : adjacency sig  [ 1 3 4 6 7 8 8 11 14 14 14 15 ]
       graph0 members { 2 }

   6 : adjacency sig  [ 3 4 5 7 8 8 9 11 14 14 14 15 ]
       graph0 members { 12 }

   7 : adjacency sig  [ 0 3 4 5 6 8 8 9 11 14 14 14 15 ]
       graph0 members { 0 }

   8 : adjacency sig  [ 1 3 4 5 6 7 8 9 11 14 14 14 15 ]
       graph0 members { 1, 14 }

   9 : adjacency sig  [ 0 1 3 4 6 7 8 8 14 14 14 15 ]
       graph0 members { 8 }

  11 : adjacency sig  [ 0 1 3 5 6 7 8 8 14 14 14 ]
       graph0 members { 7 }

  14 : adjacency sig  [ 0 1 3 4 5 6 7 8 8 9 11 14 14 15 ]
       graph0 members { 3, 9, 10 }

  15 : adjacency sig  [ 0 1 4 5 6 7 8 8 9 14 14 14 ]
       graph0 members { 5 }

20 tasks were executed in phase 1

performing medial analysis
    identifying internally medial classes
        there are no internally medial classes
    identifying medial components
        there are no medial components of the class graph

//  Medial analysis determines whether a second phase is required. It will be
//  discussed later in this post.

20 tasks were executed overall

The final list of equivalence classes in example is a canonical representation of Graph0.

Construct Canonical Representation of a Strict Graph Algorithm - Serial - Sketch

//  This sketch of the algorithm has been kept short and will be expanded in the 
//  next post in this series. This presentation is intended to provide some
//  structure to supplement the previous example - much has not yet been defined. 
//  'Medial' terms will be later in this post.

distribute nodes to equivalence classes initially according to their degree
for each equivalence class that is in use
    enqueue a signature-refresh task for the class  (simply the class ID)
phase = 1
done = false
while not done
   while the signature-refresh task queue is not empty
      dequeue a signature-refresh task
      for each node in the task's equivalence class
         construct a new signature for the node
      sort the collection of new signatures  (ignoring any label information)
      if the number of distinct new signatures is 1
         assign the new signature to the nodes, reusing the equivalence class
      else
         for each new signature
            identify the number of the new equivalence class for the signature
            move the nodes having the signature to the new equivalence class
         retire the old equivalence class
         if the signature-refresh task queue does not contain the old class ID
            enqueue a signature-refresh task for each class whose signature          
                  refers to the retired class
   if phase == 1
      perform medial analysis
      if there are any medial components
         phase = 2
      else
         done = true
   else
      done = true

This sketch of the algorithm leaves several terms undefined - most importantly, 'signature'. There is a problem with the signature as I have presented it so far. I have talked about two components to the signature - a degree signature and an adjacency signature. For many graphs, these are sufficient to construct a canonical representation. For several graphs, however, another signature component is needed.

My current research on this problem is attempting to prove that a candidate that I have identified for this third component results in a signature that is a complete invariant.

The algorithm constructs new signatures with one component (degree) prior to phase 1, with two components (degree and adjacency) during phase 1, and with three components (degree, adjacency, and tertiary) during phase 2.

Medial analysis

How can graphs that require this third signature component (and phase 2) be characterized?

To decide whether phase 2 of the algorithm will be required, the equivalence classes of the graph at the end of phase 1 are examined. Every class has an adjacency signature that contains zero or more references to each class, including itself. We'll partition this list of references into 'internal references', referring to edges with other nodes in the same class, and 'external references', referring to edges with nodes in other classes.

The signature for a class might contain no internal references, every possible internal reference, or somewhere in between. The first two cases I consider to be 'extremal' and the third to be 'medial'. For example, consider class 137 that has 6 member nodes. If class 137 has an adjacency signature with 0 or 5 references to class 137, it is an internally extremal class; otherwise it is an internally medial class. In other words, if the subgraph induced by the set of the members of 137 is a clique or an independent set, class 137 is internally extremal; otherwise, it is internally medial.

The adjacency signature for a class may also contain references to other classes. Class X and class Y may be extremally or medially connected. For example, assume that class X has 4 member nodes and Y has 4 member nodes. If class X's adjacency signature has 0 or 4 references to class Y, then class X is extremally connected with class Y; otherwise class X is medially connected to with respect to class Y. In other words, if either no node of class X is connected to a node of class Y, or every node of class X is connected to every node of class Y, then X and Y are extremely connected; otherwise, they are medially connected.

I have found that it helps to make use of a class graph, in which every node in the class graph corresponds to an equivalence class of the graph at the end of phase 1. Connect each pair of nodes that correspond to medially connected classes with an edge. The class graph now consists of one or more connected components, with no connections between components. A component is either medial, consisting of one internally medial class or two or more classes having some chain of connection between them, or extremal, consisting of an isolated node that represents a class that is internally extremal and not medially connected to any class.

If the equivalence relation at the end of phase 1 has any medial components in its class graph, then phase 2 of the algorithm is required; otherwise, it is not.

Note that regular graphs (all nodes having the same degree) whose nodes have neither minimum or maximum degree will have a single internally medial class at the end of phase 1 and thus require phase 2.

I have been searching for an effective and efficient third signature component for more than four years. I found one that worked but was extremely inefficient for one variety of graph. I think I have found a variation on that signature that avoids this problem and am examining it carefully.

I'll provide a more detailed verion of the Construct Canonical Representation algorithm in my next post in this series.

          First in thread      Previous in thread

Copyright and Legal Notices

All Rights Reserved.