I would like to generate graphs randomly, like this:
I think, that ShapeRenderer in libgdx can help to solve this. I would like to generate randomly x, y coordinates, then draw circles, but I do not know how to draw lines randomly between the circles?
Can you please show me some working tutorials?
Don’t constrain the problem to a specific rendering platform.
It’s a graph, all there is are node and edges. They can be rendered however you please, generating the graph has nothing to do with it.
Maybe something like:
int numNodes = (int) (Math.random() * MAX_NODES);
int numEdges = (int) (/* suitable expression*/);
List<Point> nodes = new ArrayList<>(numNodes);
List<Line> edges = new ArrayList<>(numEdges);
for (int i = 0; i < numNodes; i++)
nodes.add(new Point((int) (Math.random() * MAX_X), (int) (Math.random() * MAX_Y)));
// this gets more complicated if you want the graphs
// to be simple, or have other specific properties.
for (int i = 0; i < numEdges; i++) {
Point p1 = nodes.get((int) (Math.random() * numNodes));
Point p2 = nodes.get((int) (Math.random() * numNodes));
edges.add(new Line(p1, p2));
}
Then you can render it just by iterating over edges and nodes and rendering lines and circles.
Note that loops must either be eliminated (while p1 == p2, try again, etc.) or handled as a special case in rendering, as currently they will not be visible using just a drawLine() like primitive.
Yes, the graphs should be simple.
I see, but it is a complicated, complex problem and I think rendering platforms give some plus, through the implementation.
Logic and view should be separated.
In you case, the rendering is only iterating throught the nodes and drawing a circle with a specific radius on the given point as well as iterating throught the edges and drawing a line between the given points. I guess thats easy.
The logic instead needs to “place” (create) the nodes with random, but usable positions and connect them randomly but simple.
Thats where it gets complex, here you need to think about, what is simple, how do you want them to connect, how many connections can one node have etc.
As soons as you know, what exactly you want to reach, you might be able to translate that into conditions for the node-edge generation.
You could make nice looking simple graphs via Delaunay triangulation.
Then remove random edges until desired sparseness is achieved.
If you really want to discourage sharp skinny faces then the seed points could be generated via Poisson disk sampling.
Quick attempt at using Poisson:
No Delaunay, would look much nicer (read: planar), this simply uses the code I posted above to generate edges, then removes parallels and loops to make the graph simple.
http://pastebin.java-gaming.org/8dfef702c131c
(Note, code is quite inefficient)
Poisson disk sampling seems great.
Can you please help me a bit more about parameters.
I should generate graphs containing edges with at least one edge. So each degree should be greater than zero, so the graph will be coherent.
Like I said, Delaunay triangulation is probably your best bet, graphs generated by it are simple, complete, and planar, and fed with Poisson points, it will look aesthetically pleasing.
The completeness guarantees that every node is connected.
Sample image from Wikipedia:
.svg/500px-Delaunay_Triangulation_(100_Points).svg.png)
Now imagine the points are nicely distributed a-la Poisson.
Once you have a complete simple graph, edges can be removed to create a desired subgraph.
I have searched for an efficient code, I have found a solution, but there is an error in the import section.
You don’t have to import classes from the same package, in this case the default (unnamed) package.
I have fixed the missed imports, but this code isn’ t working well.
Can you offer me please some more useful codes/code snippets?
I have tried to solve this on several ways and think, that “filtering/check” should be in simpleGraph, but I don’t know what exactly.