Subject: Improved Algorithm for Checking for Graph Isomorphism

From: Shlomi Fish <[email-masked]>
Date: Tue, 28 Nov 2000 13:55:57 +0200 (IST)

You can find an improved version of my Graph Isomorphism check algorithm
on its site at:

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

The improvements from the last time are:

1. The algorithm now consider the prev_id of the node as part of its
identification form.

2. Now there are |V| super-iteration of the entire algorithm. At the end
of every super-iteration if the algorithm sees that there is an ID that is
allocated to more than one node, then one node from each graph is
allocated a new ID. Then the regular process repeats.

Now, the improved algorithm can distinguish between a 6-node circle and
two triangles, but it doesn't mean it is a valid algorithm yet.

Anyway, here is the source code for the improved function for your review:

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);
    my ($super_iteration);

    $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($super_iteration=0;$super_iteration<$num_nodes;$super_iteration++)
    {
        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]));

                    my $string = join(";", $prev_ids[$g]->[$node], $link_ids[0], (map { join(",", (sort { $a <=> $b } @{$_})); } @link_ids[1 .. $#link_ids]));

                    #print "\$super_iteration=$super_iteration\n\$iteration=$iteration\n\$node=$node\n\$g=$g\n\$string = \"$string\"\n\n\n\n";
                    
                    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++;
                        }
                    }
                }
            }

            #{
            #    my $d = Data::Dumper->new([ \@next_ids], [ "next_ids" ]);
            #    print $d->Dump(); 
            #}

            if (join(",", (sort { $a <=> $b } @{$next_ids[0]})) ne 
                join(",", (sort { $a <=> $b } @{$next_ids[1]}))   )
            {
                return 0;
            }
            #print "\$si=$super_iteration\n\$iteration=$iteration\n";
            #print join(",", @{$next_ids[0]}), "\n", join(",", @{$next_ids[1]}), "\n\n\n";
            @prev_ids = @next_ids;
        }
        if ($new_id == $num_nodes)
        {
            return 1;
        } 
        {
            my (@sorted_ids, $i, $id_to_change);
            # Find an ID that is shared by two or more nodes.
            @sorted_ids = (sort {$a <=> $b } @{$prev_ids[0]});
            for($i=0;$i<$num_nodes;$i++)
            {
                if ($sorted_ids[$i] == $sorted_ids[$i+1])
                {
                    $id_to_change = $sorted_ids[$i];
                    last;
                }
            }
            # Take one node from each graph that was assigned this ID and
            # modify its ID to a non-existant one.
            for($g=0;$g<2;$g++)
            {
                for($i=0;$i<$num_nodes;$i++)
                {
                    if ($prev_ids[$g]->[$i] == $id_to_change)
                    {
                        $prev_ids[$g]->[$i] = $new_id;
                        last;
                    }
                }
            }
        }
    }

    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: Wed, 29 Nov 2000 06:15:49 +0200 (IST)

Well, I realized even my improved algorithm has a fault. Let's take for
example two graphs in which there is one 6-node circle and one triangle.
Now, at the end of the first super iteration all of the nodes will have id
0. But then the algorithm will report isomorphism or not based on whether
it will choose in both graphs one node from either circle or two notes
from different circles.

Solution: Count the number of nodes which are reachable by each node and
include it in the identification form. Thus, at the beginning of the
algorithm two arrays with the connected nodes counts of each node are
prepared. That way, the algorithm distinguishes between symettery
constructs of variable multiplexity.

Here is the updated code for your review, but it is also available at the
site.

Regards,

	Shlomi Fish

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

    $max_link_count = 0;

    my (@connected_nodes, @num_connected_nodes);

    @num_connected_nodes = ([ (-1) x $num_nodes ], [ (-1) x $num_nodes ]);

    for($g=0;$g<2;$g++)
    {
        for($node=0;$node<$num_nodes;$node++)
        {
            if ($num_connected_nodes[$g]->[$node] == -1)
            {
                @connected_nodes = ();

                my $dfs;
                $dfs = sub {
                    my $n = shift;

                    if (grep { $_ == $n } @connected_nodes)
                    {
                        # do nothing
                    }
                    else
                    {
                        push @connected_nodes, $n;
                        for(my $tn=0;$tn<$num_nodes;$tn++)
                        {
                            if ($graphs[$g]->[$n][$tn] > 0)
                            {
                                $dfs->($tn);
                            }
                        }
                    }
                };

                $dfs->($node);

                foreach my $n (@connected_nodes)
                {
                    $num_connected_nodes[$g]->[$n] = scalar(@connected_nodes);
                }
            }
        }
    }

            for($g=0;$g<2;$g++)
            {

                    # Serialize the node ID

                    my $string = join(";", $prev_ids[$g]->[$node], $num_connected_nodes[$g]->[$node], $link_ids[0], (map { join(",", (sort { $a <=> $b } @{$_})); } @link_ids[1 .. $#link_ids]));

            #{

    return 1;
}

---

From: Shlomi Fish <[email-masked]>
Date: Wed, 29 Nov 2000 14:53:15 +0200 (IST)

A newer and much optimized version of the graph isomorphism algorithm is
available at its site. The API has changed a bit due to the introduction
of a preprocess function.

The URL is:

I'm not posting it here this time to save bandwidth.

Regards,

	Shlomi Fish

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 30 Nov 2000 13:54:01 +0200 (IST)

Once again I discovered that sometimes my algorithm returns an erroneous
value for some graphs. So I modified it again, and now it doesn't, at
least not on the examples I unputted it with.

You can take a look at the code to see how it works. I'll try to add more
comments as time goes by. Note that there is a "safe" parameter. The
algorithm with safe set to 1 is more correct than the one with safe set to
0, but I'm not sure about it. (So far both yield the same correct
results).

The URL is:

Enjoy!

	Shlomi Fish

---

From: "Nadav Har'El" <[email-masked]>
Date: Fri, 1 Dec 2000 00:18:00 +0200

> least not on the examples I unputted it with.

It's nice that you're sharing with us all the versions and improvements
in the code, don't get me wrong, but maybe what you should be doing instead
is trying to prove that your algorithm does work? Graph algorithms is a
very interesting subject, and the beautiful thing about it is that, like
Mathematics, you're usually expected to _prove_ that your algorithm works
in all cases (or say in which cases it doesn't).

When you go about proving such algorithms, many times you'll see a reason
why you can't prove it - which will point you to a counter-example that
you'd have never found by random experimentation.

By the way, I assume you studied Graph Algorithms in the Technion, and read
a book about it, like Shimon Even's great "Graph Algorithms", right? If not,
this would certainly be the first step before dabbling in graph algorithms ;)

-- 
Nadav Har'El                        |        Friday, Dec 1 2000, 4 Kislev 5761
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |I love deadlines. I love the whooshing
http://nadav.harel.org.il           |sound they make as they go by.

---

From: Shlomi Fish <[email-masked]>
Date: Fri, 1 Dec 2000 06:43:20 +0200 (IST)

> in all cases (or say in which cases it doesn't).

Well part of the reason that I post the versions here is so that I'll have
prior art claims. I don't plan to patent the algorithm, but I wish to be
credited for it. Otherwise, I also wish to receive feedback for it.

Not that I'm planning not to prove it evntually, though.

> this would certainly be the first step before dabbling in graph algorithms ;)

I took a course of the Electrical Engineering faculty named "Intro to Data
Structures and Algorithms" which covers graph algorithms among other
things. There weren't too many proves there, though. I also once took a
correspondence course for Youth about graph theory. I glanced through the
first chapter of Even's book, but did not read it thouroughly yet.

Anyway, I did meet with Prof. Even's last Monday, and he noted why the
initial version of the alogirthm would not always work. I deduced other
cases why the later versions wouldn't work based on his example. It is my
intention to meet him next Monday (at his office hours) and present to him
the most recent version and ask for his opinion and input.

I don't think this discussion is off topic, but if enough people are fed
up with it, I will lower the posting rate.

BTW, there's a new version of the _code_ at the site. Nothing new has
changed in the algorithm, but I recommend you download it anyway. In case,
you are interested of course.

Regards,

	Shlomi Fish
 
> To unsubscribe from this group, send an email to:
> [email-masked]
> 
> 
> 
>

---

From: "Nadav Har'El" <[email-masked]>
Date: Fri, 1 Dec 2000 15:14:29 +0200

> credited for it. Otherwise, I also wish to receive feedback for it.

Ok ;) Though I have to warn you - the hackers-il mailing-list isn't exactly
a known group of graph-algorithmers, so saying "I mailed it to hackers-il
first" wouldn't give you much against another researcher who sent his research
to an accredited journal...

> first chapter of Even's book, but did not read it thouroughly yet.

If you're interested in the subject, I wholeheartedly recommend reading
Prof. Even's book, even though it is not an easy undertaking. That book is
now out-of-print, but you can try getting it in the Technion library.
I don't know what they teach in "Intro to Data Structures and Algorithms",
but Even teaches his "Algorithms in Graph Theory" course following his
book almost exactly, so if you read the book you'll know everything they
teach in the Technion's CS "Algorithms in Graph Theory" course.

> the most recent version and ask for his opinion and input.

That's good :) I don't want to doubt the inteligence of myself and other
people in this list, but let's just say that Prof. Even is probably an
order-of-magnitude better in Graph Theory then the rest of us, so if you
got him to help you, that is great.

> up with it, I will lower the posting rate.

Don't worry - even if you send an daily update it won't bother me too much ;)
But I was just trying to suggest to you a more productive method than sending
us an update each day. I don't know about the other people of the mailing
list, but I know that I don't have patience to read your code every day, try
to see what changed, and what is still wrong with the algorithm, etc., so I
doubt I'll be able to help you much...

-- 
Nadav Har'El                        |        Friday, Dec 1 2000, 4 Kislev 5761
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Tea or coffee? Coffee, without cream. It
http://nadav.harel.org.il           |will be without milk, we have no cream.

---

From: Shlomi Fish <[email-masked]>
Date: Fri, 1 Dec 2000 23:40:49 +0200 (IST)

> to an accredited journal...

Yes, but what if I posted this today, and a month later the letter with
the Algorithm description was received in the Journal's office, and it was
published six or 8 weeks later. Obviously, I am the one who came up with
the algorithm first.

Regards,

	Shlomi Fish

---

From: "Nadav Har'El" <[email-masked]>
Date: Sat, 2 Dec 2000 00:24:20 +0200

> published six or 8 weeks later. Obviously, I am the one who came up with

Unfortunately, this is not exactly how the academic world works... I mean,
consider the editor of some world-renowned graph-algorithm journal (I have
to admit that I don't know the name of one...). If in a month he'll get
from somebody else a submittion of an article with your algorithm in it,
he'll do his best to make sure that this algorithm wasn't published before -
including giving giving the submitted paper to referees familiar with the
subject to look at it. But none of them read hackers-il, and none of them
will know that you have previously published the same algorithm in hackers-il.
So they print the article, and every graph-algorithmist in the world reads
this paper, and the algorithm becomes known as TheOtherGuy's algorithm.
Several months later you find this published paper, and write the editor
telling him you invented the algorithm before that - and you have the proof
in hackers-il's archives. What do you think they'll do? The most they'll do
is publish a short note, but the algorithm will still be known as TheOtherGuy's
algorithm.
This is why you'll see people in Academia publishing several papers a year,
many of them with only small contributions - as they say, "Publish or Perish".

But don't let that disparage you ;)

-- 
Nadav Har'El                        |      Saturday, Dec 2 2000, 5 Kislev 5761
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |The 3 stages of sex: Tri-weekly, try
http://nadav.harel.org.il           |weekly, try weakly.

---

From: Shlomi Fish <[email-masked]>
Date: Sat, 2 Dec 2000 17:28:37 +0200 (IST)

Revision 2 of the document is available on the site.

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

Exact URL:
http://t2.technion.ac.il/~shlomif/graphs_equal/Docs/Description.txt

Comments are welcome.

Regards,

	Shlomi Fish