## Re: [hackers-il] Updated version of Graph Isomorphism Algorithm

Expand Messages
• ... 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
Message 1 of 12 , Nov 30, 2000
• 0 Attachment
On Thu, Nov 30, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
>
> 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.

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
nyh@... |-----------------------------------------
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.
• ... Because it has a lower complexity. I think the safe one is in the worst-case |V|!, and the safe one is |V|^5 or so. ... Well, I m _almost_ certain that the
Message 2 of 12 , Nov 30, 2000
• 0 Attachment
On Thu, 30 Nov 2000, Chen Shapira wrote:

> Why run an unsafe one?
>

Because it has a lower complexity. I think the safe one is in the
worst-case |V|!, and the safe one is |V|^5 or so.

> Which one is more correct algorithmicaly?
>

Well, I'm _almost_ certain that the safe one is valid, but I don't have an
official prove yet. As for the unsafe one, it could be valid too, but I'm

Regards,

Shlomi Fish

>
> To unsubscribe from this group, send an email to:
> hackers-il-unsubscribe@egroups.com
>
>
>
>

----------------------------------------------------------------------
Shlomi Fish shlomif@...
Home E-mail: shlomif@...

The prefix "God Said" has the extraordinary logical property of
converting any statement that follows it into a true one.
• ... 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
Message 3 of 12 , Nov 30, 2000
• 0 Attachment
On Fri, 1 Dec 2000, Nadav Har'El wrote:

> On Thu, Nov 30, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
> >
> > 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.
>
> 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).
>

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.

> 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 ;)
>

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

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

> --
> Nadav Har'El | Friday, Dec 1 2000, 4 Kislev 5761
> nyh@... |-----------------------------------------
> 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.
>
>
> To unsubscribe from this group, send an email to:
> hackers-il-unsubscribe@egroups.com
>
>
>
>

----------------------------------------------------------------------
Shlomi Fish shlomif@...
Home E-mail: shlomif@...

The prefix "God Said" has the extraordinary logical property of
converting any statement that follows it into a true one.
• ... 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
Message 4 of 12 , Dec 1, 2000
• 0 Attachment
On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
> 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.

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...

> > 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 ;)
> 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.

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.

> 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

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

> I don't think this discussion is off topic, but if enough people are fed
> 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

--
Nadav Har'El | Friday, Dec 1 2000, 4 Kislev 5761
nyh@... |-----------------------------------------
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.
• ... 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
Message 5 of 12 , Dec 1, 2000
• 0 Attachment
On Fri, 1 Dec 2000, Nadav Har'El wrote:

> On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
> > 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.
>
> 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...
>

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

----------------------------------------------------------------------
Shlomi Fish shlomif@...
Home E-mail: shlomif@...

The prefix "God Said" has the extraordinary logical property of
converting any statement that follows it into a true one.
• ... 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
Message 6 of 12 , Dec 1, 2000
• 0 Attachment
On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
> > 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...
>
> 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.

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
nyh@... |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |The 3 stages of sex: Tri-weekly, try
• Revision 2 of the document is available on the site. Site URL: http://t2.technion.ac.il/~shlomif/graphs_equal/ Exact URL:
Message 7 of 12 , Dec 2, 2000
• 0 Attachment
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

Regards,

Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish shlomif@...