Generate all possible graphs

mehdi62b · #1 (**permalink**) September 25th, 2004, 02:27 PM

Hello everybody,
can anybody give an idea on how to solve this problem....
I need an algorithm to generate all possible undirected regular graph having N nodes and degree D.
an undirected regular graph of degree D is one in which all nodes have same degree D
any help, ideas...will be appreciated
Thanks in advance.

--------------------------------------------
Mehdi.:)

mehdi62b · #2 (**permalink**) September 25th, 2004, 02:44 PM

I know just
N*D=2*q
(q=the numbers of edges)
so if N*D is an odd number we will not have any possible graph!

--------------------------------------------
Mehdi.:)

kokon · #3 (**permalink**) October 6th, 2004, 01:30 PM

I'm not really following your question.

You can use graph-coloring or Dijkstra SPF if you're looking for the shortest graph.

KOkon.

mehdi62b · #4 (**permalink**) October 6th, 2004, 03:28 PM

I didnt want the shortest graph,
Thanks anyway.

--------------------------------------------
Mehdi.:)