# Random undirected graph generation

I would like to generate graphs randomly, like this:

I have found that Box2d maybe can do it to me. But I do not know, how to use it, so how can I generate bobies after world initialization?

• What exactly do these graphs represent? Are they visible objects? Do they represent some kind of game data? It's very unclear what you are asking for here. – user1430 Oct 17 '14 at 20:20
• These graphs' vertex should be clickable in the future. At this time I would like only generate them, to be visible on the screen. – plaidshirt Oct 18 '14 at 7:28
• Are there any other constraints? Why is this game related? The graph appears to be embedded in a 2D plain, do the nodes need to be embedded or not in the real case? Does it have to be connected? – AturSams Oct 18 '14 at 8:58
• This is not related at all to Box2D from the question you describe. – AturSams Oct 18 '14 at 9:24

Considering the example, I assume you mean a connected graph, i.e., there is a path from any point to any other point.

First decide if you want it to be very sparse or if the graph might need be very dense (each type prefers a different data structure).

Dense graphs are handled better by a 2D matrix of Booleans where position (j, i) is lit if j and i are connected. Sparse graphs use a list of neighbors for each vertex in the Graph. If i and j are connected, then each will be stored in the others neighbors list. I will assume it is spare because of the image example; which is all I have to go after at this point.

1. Create a struct (POD) or a class that describes a Vertex, it needs to store an id of type Int, a position (which is possibly two Floats) and a list of all neighboring vertices, which is an Array or List of Vertex named neighbors.
2. Randomize N Positions ( on the 2d plain) for a graph where |V| = N (in plain English, the number of vertices equals N).
3. Iterate over the random positions:
1. Create a new Vertex from each one, with the Position stored as the Vertex's position.
2. Randomly pick a neighbor from one of the vertices created until this point (don't do it for the first Vertex as there will be no other vertices at that point).
3. Connect the two by adding each to the others neighbors list.
4. To increase density, loop again and pick two vertices v and u each iteration where v != u and connect them until the number of edges is satisfactory to your needs. If you want a very dense graph, it is better if you assume all vertices are connected and pick ones to disconnect instead.

To draw the graph:

1. Iterate over the vertices of type Vertex:
1. Draw line from their position to all the neighbors' positions if the current Vertex's Id is lower than that of the neighbor.
2. Draw a circle in the Vertex's position.
3. Draw the ID number in the center of the circle and on top of it.
• Is the solution easier with use of bodies? -I will generate bodies, with given distance around them. So there is no matrix needed. -Then I will iterate through the bodies(vertex) and draw the lines beetween them(randomly). How do you think, is this idea correct? Can you show me please some working tutorials about your or my described method? – plaidshirt Oct 21 '14 at 18:12
• Box2d is a 2d physics Simulator. It won't make it easier imho. If what you want is simply to draw circles and lines between them with this library, then read about the ShapeRenderer, If you don't need to save the data, randomly picking x & y values, drawing lines between them and then circles would work. – AturSams Oct 21 '14 at 18:20
• I see, but the problem is with the drawing. How can I draw lines randomly between the circles? – plaidshirt Oct 24 '14 at 20:31
• @KovacsAkos You pick two points and draw a line. To randomize a point, you pick a random x & y values and save them. To draw a line use the ShapeRenderer. These questions have nothing to do with graphs. Ask a new question instead. – AturSams Oct 25 '14 at 8:53

You want to create a list of nodes in an array and randomize the position values. You can then make a new array to store arcs. Make an Arc object with "Start Node, EndNode" and simply store random (Different) node numbers together for each arc you want.