473,326 Members | 2,813 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Need graph isomorphism algorithm


Hello everybody!

Could anyone help with a practical graph isomorphism algorithm, coded
in C++ (C would also do), to work with genus bounded graphs of a
bounded degree.

Currently, any algorithm to work with planar graphs with degree bounded
by 4 (on a quadratic grid) would also help.

Thanks a lot,

Alex.
--
Posted via http://dbforums.com
Nov 13 '05 #1
4 5001
sasha.mal wrote:
Hello everybody!

Could anyone help with a practical graph isomorphism algorithm, coded
in C++ (C would also do), to work with genus bounded graphs of a
bounded degree.

Currently, any algorithm to work with planar graphs with degree bounded
by 4 (on a quadratic grid) would also help.

Thanks a lot,

Alex.


Perhaps a search engine:
http://www.google.com/search?hl=en&i...=Google+Search

Perhaps a graphics newsgroup:
news:comp.graphics

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Nov 13 '05 #2

On Tue, 14 Oct 2003, Thomas Matthews wrote:

sasha.mal wrote:

Could anyone help with a practical graph isomorphism algorithm, coded
in C++ (C would also do), to work with genus bounded graphs of a
bounded degree.

Currently, any algorithm to work with planar graphs with degree bounded
by 4 (on a quadratic grid) would also help.


Perhaps a search engine:
http://www.google.com/search?q=graph...hism+%22C++%22

Perhaps a graphics newsgroup:
news:comp.graphics


Okay, I wasn't going to post to this thread, seeing as all I know about
graph isomorphism is that it's hard, and since I recognize 'sasha.mal'
from sci.math (or was it rec.puzzles?) I'm fairly sure he knows that.

But do you know something I don't? What would comp.graphics know about
graph isomorphism -- does it have some common application in graphics
programming? Pray elucidate!

(Sasha, try comp.programming on this one.)

-Arthur
Nov 13 '05 #3
Arthur J. O'Dwyer <aj*@nospam.andrew.cmu.edu> spoke thus:
Okay, I wasn't going to post to this thread, seeing as all I know about
graph isomorphism is that it's hard, and since I recognize 'sasha.mal'
from sci.math (or was it rec.puzzles?) I'm fairly sure he knows that.


Isn't the graph isomorphism problem one of those lovely NP-hard problems? Or
something like that?

--
Christopher Benson-Manica | Upon the wheel thy fate doth turn,
ataru(at)cyberspace.org | upon the rack thy lesson learn.
Nov 13 '05 #4

On Tue, 14 Oct 2003, Christopher Benson-Manica wrote:

Arthur J. O'Dwyer <aj*@nospam.andrew.cmu.edu> spoke thus:
Okay, I wasn't going to post to this thread, seeing as all I know about
graph isomorphism is that it's hard, and since I recognize 'sasha.mal'
from sci.math (or was it rec.puzzles?) I'm fairly sure he knows that.


Isn't the graph isomorphism problem one of those lovely NP-hard problems?
Or something like that?


Almost. AIUI from a brief tour of MathWorld, graph isomorphism

is in NP (of course)
is not known to be in P
is not known to be NP-complete

so it's not known to be NP-hard. Up until now, I've been kind of
colloquially using the English word "hard" to denote "not known to
be in P" (i.e., "not easy" :), but I suppose I should know to be
more precise.

[There *are* apparently a *lot* of problems reducible to graph
isomorphism, but AFAICT the problem isn't known to be NP-complete.]

-Arthur
Nov 13 '05 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Paul Moore | last post by:
I'm trying to check a graph (represented in the usual Python adjacency list format) for loops. This is dead simple - you use a depth-first search, and look out for "back edges" (edges from a vertex...
9
by: Lilith | last post by:
Is there a python module somewhere (been searching today, no luck) which has efficiently coded various graph-handling routines, such as finding the shortest path through a graph, or the set of all...
25
by: Magnus Lie Hetland | last post by:
Is there any interest in a (hypothetical) standard graph API (with 'graph' meaning a network, consisting of nodes and edges)? Yes, we have the standard ways of implementing graphs through (e.g.)...
0
by: sasha.mal | last post by:
Hello everybody! Could anyone help with a practical graph isomorphism algorithm, coded in C++ (C would also do), to work with genus bounded graphs of a bounded degree. Currently, any...
1
by: aredo3604gif | last post by:
On Sun, 10 Apr 2005 19:46:32 GMT, aredo3604gif@yahoo.com wrote: >The user can dynamically enter and change the rule connection between >objects. The rule is a "<" and so given two objects: >a <...
4
by: enigma261 | last post by:
Hello, I am looking for graph layout algorithms. I am representing a process flow using a graph. I have the visual representation of nodes and connectors. I would like to use a graph layout...
3
by: Amol | last post by:
I am working on an interesting graph optimization problem and I would like to have a few expert opinions for helping me with a solution. So here goes ... I have a black box with a complex...
4
by: Shuch | last post by:
Hi all, I am in shortage of time...and i want to know if someone has a code written in c++ or c for finding the shortest path using stack or queue??????my specifications r as follow: Input...
1
by: Glenton | last post by:
Hi All Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm: #!/usr/bin/env python #This is meant to solve a maze with Dijkstra's...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.