Subject: Algorithm for checking if two graphs have the same topology

From: Shlomi Fish <[email-masked]>
Date: Thu, 23 Nov 2000 07:09:38 +0200 (IST)

I came up with an algorithm for checking if two graphs have the same
topology. Two graphs with same topology have the same arrangements of
edges, only with different ordering of the nodes.

I wrote an implementation of it in perl, and placed it on the web:

http://t2.technion.ac.il/~shlomif/graphs_equal/

Anyway, I'd like to know what you think of it and if you happen to know it
from other sources.

A basic explanation of it is as follows:

I iterate |V| times (|V| is the number of nodes/vertexes) and in each
iteration I try to build a better model of the graph. The model involves
assigning IDs to each node. The IDs stand for node identification strings
which encode what are the node IDs (of the previous iteration) of the
nodes at the end of the links that extend from that node. At the end of
each iteration the sorted list of IDs of each graph is compared, and if
they are different than the algorithm returns a false value.

If after the |V|th iteration the lists are still the same, then the
algorithm returns true. The IDs are all initialized to 0 before the first
iteration.

The perl code is included below.

Regards,

	Shlomi Fish

sub are_graphs_equal
{
    my $num_nodes = shift;
    my (@graphs);
    $graphs[0] = shift;
    $graphs[1] = shift;

    my (@prev_ids, @next_ids, %id_map);

    @prev_ids = ([ (0) x $num_nodes ], [ (0) x $num_nodes ]);

    my ($iteration, $node, $g, $to_node, 
        @link_ids, $max_link_count, $new_id);

    $max_link_count = 0;
    for($node=0;$node<$num_nodes;$node++)
    {
        for($to_node=0;$to_node<$num_nodes;$to_node++)
        {
            if ($node != $to_node)
            {
                $max_link_count = numeric_max(
                    $max_link_count,
                    $graphs[0]->[$node][$to_node],
                    $graphs[1]->[$node][$to_node]
                    );
            }
        }
    }
    
    for($iteration=0;$iteration<$num_nodes;$iteration++)
    {
        @next_ids = ([], []);
        %id_map = ();
        $new_id = 0;

        for($g=0;$g<2;$g++)
        {
            for($node=0;$node<$num_nodes;$node++)
            {
                for(my $a=0;$a<=$max_link_count;$a++)
                {
                    $link_ids[$a] = [];
                }
                
                for($to_node=0;$to_node<$num_nodes;$to_node++)
                {
                    if ($to_node == $node)
                    {
                        $link_ids[0] = $graphs[$g]->[$node][$node];
                    }
                    elsif ($graphs[$g]->[$node][$to_node] > 0)
                    {
                        push @{$link_ids[$graphs[$g]->[$node][$to_node]]}, 
                            $prev_ids[$g]->[$to_node];
                    }
                }

                # Serialize the node ID
                my $string = join(";", $link_ids[0], 
                    (map { join(",", (sort { $a <=> $b } @{$_})); } 
                         @link_ids[1 .. $#link_ids]));
                
                if (exists($id_map{$string}))
                {
                    $next_ids[$g]->[$node] = $id_map{$string};
                }
                else
                {
                    if ($g == 1)
                    {
                        return 0;  # I encountered a string that 
                        # wasn't present in the previous graph, so 
                        # the graphs cannot be the same.
                    }
                    else
                    {
                        $id_map{$string} = $new_id;
                        $next_ids[$g]->[$node] = $new_id;
                        $new_id++;
                    }
                }
            }
        }

        if (join(",", (sort { $a <=> $b } @{$next_ids[0]})) ne 
            join(",", (sort { $a <=> $b } @{$next_ids[1]}))   )
        {
            return 0;
        }
        @prev_ids = @next_ids;
    }

    return 1;
}

----------------------------------------------------------------------
Shlomi Fish        [email-masked] 
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

The prefix "God Said" has the extraordinary logical property of 
converting any statement that follows it into a true one.

---

From: Shlomi Fish <[email-masked]>
Date: Tue, 28 Nov 2000 11:20:59 +0200 (IST)

After discussing my algorithm with a Technion professor who specializes in
Graph Theory, I realized it has a fault. Sometimes it report two graphs to
be isomorphic (i.e: have the same topology) while in fact they are not.

For example: a circle of 6 nodes and two separate triangles will be
considered the same according to it. However, as far as I can see if it
reports two graphs to be distinct then they are for certain distinct.

The professor told me that the problem of Graph Isomorphism was
efficiently solved only for a certain number of maximal outgoing links per
node. But, I on my part will think on my algorithm for a while, and see
how to proceed from the stage that it reports that two graphs are
isomorphic.

Regards,

	Shlomi Fish