Uniformly random connected minimally cyclic graph algorithm

Question

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.

Answer 1

As far as I can tell, if we ignore the cycle, the images are of minimum spanning trees (a weighted, connected, undirected graph). One way to create them follows:

1. Create a uniformly random set of connected edges.
2. Let the weight for each edge be the distance between its vertices.
3. Apply Borůvka's Algorithm to find the minimum spanning tree.
4. Trace the path between connections, applying the grid constraints.

The first three steps can be accomplished in Java as follows:

import java.util.*;

import static java.lang.Math.pow;
import static java.lang.Math.sqrt;
import static java.lang.String.format;
import static java.util.Comparator.naturalOrder;

public final class BoruvkaGraph {
  private static final Random sRandom = new Random();

  public record Vertex( int x, int y ) {
    private double distance( final Vertex v ) {
      return sqrt( pow( v.x() - x(), 2 ) + pow( v.y() - y(), 2 ) );
    }

    @Override
    public String toString() {
      return format( "(%2d, %2d)", x(), y() );
    }
  }

  public static final class Edge implements Comparable<Edge> {
    private boolean mVisited;

    private final Vertex mU;
    private final Vertex mV;
    private final double mW;
    private final Queue<Edge> mAdjoined = new PriorityQueue<>( naturalOrder() );

    public Edge( final Vertex u, final Vertex v ) {
      mU = u;
      mV = v;
      mW = u.distance( v );
    }

    public Vertex u() { return mU; }

    public Vertex v() { return mV; }

    public double w() { return mW; }

    public void adjoin( final Edge edge ) {
      if( edge != null ) {
        mAdjoined.add( edge );
      }
    }

    public Queue<Edge> adjoined() { return mAdjoined; }

    public void visited( final boolean visited ) { mVisited = visited; }
    public boolean visited() { return mVisited; }

    @Override
    public int compareTo( final Edge o ) {
      return (int) (w() - o.w());
    }

    @Override
    public String toString() {
      return format( "%s -> %s [%5.2f]", u(), v(), w() );
    }
  }

  public static List<Edge> connected( final int r, final int c, final int m ) {
    final var edges = new ArrayList<Edge>( m );
    Edge prev = null;

    for( var i = m - 1; i >= 0; i-- ) {
      Vertex a = new Vertex( sRandom.nextInt( r ), sRandom.nextInt( c ) );
      Vertex b = new Vertex( sRandom.nextInt( r ), sRandom.nextInt( c ) );

      if( prev != null ) {
        final var v = sRandom.nextBoolean() ? prev.u() : prev.v();

        if( sRandom.nextBoolean() ) {
          a = v;
        }
        else {
          b = v;
        }
      }

      final var edge = new Edge( a, b );

      edges.add( edge );
      edge.adjoin( prev );

      prev = edge;
    }

    return edges;
  }

  private final List<Edge> mEdges;

  /**
   * @param edges A connected graph.
   */
  public BoruvkaGraph( final List<Edge> edges ) {
    mEdges = edges;
  }

  public Collection<Edge> compute( final Edge source ) {
    final var tree = new ArrayList<Edge>();

    source.visited( true );

    for( final var outer : mEdges ) {
      final var inner = outer.adjoined();

      while( !inner.isEmpty() ) {
        final var edge = inner.poll();

        if( !edge.visited() ) {
          tree.add( edge );
          edge.visited( true );
          break;
        }
      }
    }

    return tree;
  }

  public static void main( final String[] args ) {
    final var edges = connected( 20, 20, 40 );
    final var graph = new BoruvkaGraph( edges );
    final var source = edges.get( sRandom.nextInt( edges.size() ) );

    edges.forEach( edge -> edge.adjoined().forEach( System.out::println ) );
    System.out.println( "------------------------" );
    graph.compute( source ).forEach( System.out::println );
  }
}

Example output of the minimally spanning tree:

( 2,  6) -> (11,  2) [ 9.85]
( 2,  6) -> (11,  7) [ 9.06]
( 2,  6) -> ( 3,  2) [ 4.12]
(18,  2) -> ( 3,  2) [15.00]
(18,  2) -> ( 4, 12) [17.20]
(18,  2) -> (10, 14) [14.42]
(18,  2) -> ( 8,  0) [10.20]
(18,  2) -> ( 6,  8) [13.42]
(17, 10) -> (18,  2) [ 8.06]
(18,  2) -> (19,  7) [ 5.10]
(18,  2) -> (18,  9) [ 7.00]
(18,  9) -> (13,  4) [ 7.07]
( 3, 15) -> (18,  9) [16.16]
( 1,  1) -> ( 3, 15) [14.14]
( 3, 15) -> ( 5, 16) [ 2.24]
( 5, 16) -> (19, 19) [14.32]
( 5, 16) -> (10,  0) [16.76]
( 5, 16) -> (15,  3) [16.40]
( 0, 19) -> (15,  3) [21.93]
(15,  3) -> ( 7,  3) [ 8.00]
( 3,  0) -> ( 7,  3) [ 5.00]
(11, 15) -> ( 7,  3) [12.65]
( 8,  7) -> ( 7,  3) [ 4.12]
( 7,  3) -> (18,  6) [11.40]
(11,  7) -> (18,  6) [ 7.07]
(13, 15) -> (18,  6) [10.30]
(18,  6) -> ( 9,  0) [10.82]
( 3, 11) -> ( 9,  0) [12.53]
( 3, 11) -> (13,  8) [10.44]
(16, 15) -> (13,  8) [ 7.62]
(13,  8) -> ( 3, 14) [11.66]
( 3, 14) -> ( 5, 14) [ 2.00]
( 3, 14) -> ( 1,  7) [ 7.28]
( 1,  7) -> (14,  4) [13.34]
( 6,  5) -> (14,  4) [ 8.06]
( 6,  5) -> ( 6, 19) [14.00]
( 6, 19) -> (18,  1) [21.63]
(18,  1) -> (10,  7) [10.00]