0

A random large connected undirected graph in JAVA with 5K vertices and D density is to be generated. But generating an edge between random V1 and a random V2 is taking a lot of time. I tried eliminating a created edge from the list of all possible edges and then selecting a random one from the remaining edges, but again it is taking a lot of time.

What do you think will be a fast way to generate the edges for the huge connected graph in a random fashion?

PuppyHeadedNinja
  • 112
  • 8

2 Answers2

0

You have N = 5k number of vertixes. You need M = number of edges. Its fixed or random? If random it's a number between 1 and N*N. Just create a random number from randomizer.

Then in a look generate M pairs of random numbers each 0<=P1 and P2<=N. Each pair is an edge. Then just add weight to the pair.

StanislavL
  • 56,971
  • 9
  • 68
  • 98
  • I need to keep generating edges till I achieve D density and the graph becomes connected in a random way. But generating an edge between two random vertices (V1 = Random(size of graph) and V2 = Random (size of graph)) is taking a really long time. Is there any way that I can improve the random function? – PuppyHeadedNinja Oct 22 '13 at 06:26
  • If it is being generated purely randomly then it could take a very, very long time. You could try things like doing multiple passes across every vertex and creating an edge to a random vertex and if it already has a certain number of edges connected to that vertex then chose another one. This would hopefully generate a connected graph but it is possible that it will create subtrees. – iambeanie Oct 22 '13 at 06:33
  • http://www.javamex.com/tutorials/random_numbers/generators_overview.shtml or http://stackoverflow.com/questions/2523492/choosing-random-numbers-efficiently or you caan generate 10 random arrays of 1-100 pairs and use the random arrays for each next 10 vertexes – StanislavL Oct 22 '13 at 06:40
0

The easiest solution i can think of (might be cheating), would be to loop through each vertex and create an edge from itself to the next vertex in the list. This would meet the criteria of it being connected, then you could generate random edges until you meet the required density by generating a random number between 0 and the length of the list of vertices for the start and end of the edge and creating it.

iambeanie
  • 315
  • 1
  • 8