0
$\begingroup$

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):

graph 1

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:

graph 2

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.

$\endgroup$
4
  • $\begingroup$ I don't understand what concept you are trying to describe. A picture is not a substitution for a description of the thing you're looking for a name for. Most "things" don't have a name. One of the wonderful aspects of the English language is that we can describe a lot of concepts that don't have any existing name. I don't understand why you think the second graph is directed, or understand what you mean by uniformly random, or how one can tell looking at a single graph whether it was generated at random or not. I don't know what you mean by "implement it". $\endgroup$
    – D.W.
    Oct 2, 2022 at 3:35
  • $\begingroup$ If I knew the concept I was trying to describe, I probably wouldn't have asked the question. :-) I'm looking to create an algorithm that can generate graphs similar to those depicted. They look like DAGs with multiple sources and sinks. By "uniformly random", I mean that the nodes cover most of the grid without bias in any direction, similar to Erdős–Rényi graphs, but without overlaps and minimal connections between nodes. I've added an example implementation to the question. Perhaps they are random walks, like a Hamiltonian graph that was cut short? $\endgroup$ Oct 2, 2022 at 4:14
  • $\begingroup$ "Here are two graphs, what is a type of graph that could generate those two graphs?" sounds too ambiguous to be usefully answerable. If you have a definition of a type of graph, with some specific requirements, we might be able to tell you (a) whether there's a standard name for that, (b) an algorithm to generate graphs that meet those requirements. The visualizations look to me undirected graphs (no edges have any arrows), so I would not have considered them directed graphs or dags. To me, this illustrates the ambiguity of trying to define a concept by giving examples. $\endgroup$
    – D.W.
    Oct 2, 2022 at 4:55
  • $\begingroup$ I think I'm looking for a type of tree. I don't know whether it's directed or not. A polytree with undirected edges looks similar. $\endgroup$ Oct 2, 2022 at 5:00

1 Answer 1

1
$\begingroup$

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]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.