Background
I'm looking to replicate (as closely as possible) the graphs depicted in this question (in MetaPost).
Overview
The green edges and large green nodes in the following image depict a graph (the grid and small nodes are irrelevant):
The graph's properties include:
- Connected
- Uniformly random (or nearly so)
- Multiple leaf nodes
Here's another graph, with the same properties, showing a possible cycle, but still looks like it could be directed:
Requirements
From the graphs, the requirements appear to be:
- There exists one path between any two nodes, with a very low probability of two paths (i.e., few cycles).
- The nodes are randomly and uniformly distributed (i.e., evenly spread over a grid).
- Each node has a maximum of four directly connected nodes.
- Multiple sinks and multiple sources.
- Every node is connected to the graph.
It looks like a uniformly random, connected, acyclic graph. All the algorithms I've looked up, and two that I've implemented, don't generate the vertices and edges necessary to replicate the same properties.
Questions
What is the full technical name for this type of graph?
What algorithms would be needed to implement it?
Here's an example implementation of a connected graph:
import java.io.PrintStream;
import java.util.*;
public class ConnectedGraph {
private final static Random sRandom = new Random();
private static final class Vertex {
private final int mId;
private final int mPosition;
private final Set<Vertex> mAdjacent = new HashSet<>();
private Vertex( final int id, final int position ) {
assert id >= 0;
assert position >= 0;
mId = id;
mPosition = position;
}
public void join( final Vertex other ) {
assert other != null;
if( mAdjacent.size() < 4 && !equals( other ) ) {
mAdjacent.add( other );
}
}
@Override
public boolean equals( final Object o ) {
if( this == o ) {return true;}
if( o == null || getClass() != o.getClass() ) {return false;}
final Vertex vertex = (Vertex) o;
if( mId == vertex.mId ) {return false;}
return mPosition == vertex.mPosition;
}
@Override
public int hashCode() {
int result = mId;
result = 31 * result + mPosition;
return result;
}
@Override
public String toString() {
var sep = "";
final var sb = new StringBuilder( 32 );
sb.append( mId );
sb.append( " -> {" );
for( final var adjacent : mAdjacent ) {
sb.append( sep );
sb.append( ' ' );
sb.append( adjacent.mPosition );
sep = ",";
}
sb.append( " }" );
return sb.toString();
}
}
/**
* Sets the given array to a contiguous sequence of numbers, from 0 to the
* number of elements in the array.
*
* @param a The array to initialize.
*/
private static void initialize( final int[] a ) {
assert a != null;
assert a.length > 0;
for( var i = a.length - 1; i > 0; i-- ) {
a[ i ] = i;
}
}
/**
* Randomly rearranges the values in the given array, based on Richard
* Durstenfeld's random permutation algorithm. This modifies the array
* directly.
*
* @param a The array to reorder, randomly.
*/
private static void randomize( final int[] a ) {
assert a != null;
assert a.length > 0;
for( var i = a.length - 1; i > 0; i-- ) {
final var j = sRandom.nextInt( i + 1 );
a[ j ] ^= a[ i ];
a[ i ] ^= a[ j ];
a[ j ] ^= a[ i ];
}
}
private static List<Vertex> connectize( final int[] positions ) {
assert positions != null;
assert positions.length > 1;
final var vertices = new ArrayList<Vertex>();
var id = 0;
for( final var position : positions ) {
final var vertex = new Vertex( id++, position );
vertices.add( vertex );
if( id > 0 ) {
final var index = sRandom.nextInt( vertices.size() );
final var adjacent = vertices.get( index );
vertex.join( adjacent );
adjacent.join( vertex );
}
}
return vertices;
}
public ConnectedGraph() {}
/**
* @param n Number of vertices in the graph.
* @param m Number of edges in the graph.
* @return Randomly selected vertices.
*/
public List<Vertex> generate( final int n, final int m ) {
final var positions = new int[ n ];
initialize( positions );
randomize( positions );
return connectize( positions );
}
public void print( final Collection<Vertex> edges, final PrintStream out ) {
for( final var edge : edges ) {
out.println( edge );
}
}
public static void main( final String[] args ) {
final var graph = new ConnectedGraph();
final var edges = graph.generate( 20, 9 );
graph.print( edges, System.out );
}
}
Sample output:
0 -> { 6, 14, 0 }
1 -> { 4 }
2 -> { 4, 12, 1 }
3 -> { 2, 3, 0 }
4 -> { 0, 9, 0, 19 }
5 -> { 11, 1, 10 }
6 -> { 16 }
7 -> { 12 }
8 -> { 1 }
9 -> { 5, 19 }
10 -> { 17, 12 }
11 -> { 7, 19 }
12 -> { 2 }
13 -> { 13 }
14 -> { }
15 -> { 10 }
16 -> { 1 }
17 -> { 1 }
18 -> { 11 }
19 -> { 4 }
Rather, for the first image, the algorithm would produce:
(2, 7) -> {(1, 5)}
(1, 5) -> {(6, 7)}
(6, 7) -> {(5, 5), (5, 9), (8, 7)}
(5, 5) -> {(7, 1)}
(8, 7) -> {(9, 9)}
(5, 9) -> {}
etc.
Note: The coordinate system doesn't matter.