Graph.java

package socialnet;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * Graph holds a problem instance.
 *
 * @author Paul A. Rubin (rubin@msu.edu)
 */
public final class Graph {
  private final int nVertices;         // number of vertices
  private final edge[] edges;          // list of edges
  private final int[][] distance;      // distance matrix
  private final int diameter;          // graph diameter
  private final ArrayList<HashSet<Integer>> incident;
    // indices of edges incident at each node

  /**
   * Constructor.
   * @param nV the number of vertices
   * @param nE the target number of edges
   * @param seed a seed for the random number generator
   * @param prog print a progress report after every `prog` edges are added
   */
  public Graph(final int nV, final int nE, final long seed, final int prog) {
    System.out.println("Building the graph ...");
    nVertices = nV;
    HashSet<edge> edgeSet = new HashSet<>();
    // Create a random number generator.
    Random rng = new Random(seed);
    // Track which pairs of nodes are connected.
    boolean[][] connected = new boolean[nVertices][nVertices];
    for (int i = 0; i < nVertices; i++) {
      connected[i][i] = true;
    }
    int edgeCount = 0;
    boolean allConnected = false;
    // Add edges until the target count is reached and the graph is connected.
    while (edgeCount < nE || !allConnected) {
      // Pick random endpoints.
      int i = rng.nextInt(0, nVertices - 1);      // lower endpoint
      int j = rng.nextInt(i + 1, nVertices);      // higher endpoint
      // Check if the edge already exists.
      edge e = new edge(i, j);
      if (!edgeSet.contains(e)) {
        edgeSet.add(e);
        allConnected = connect(connected, i, j);
        // Increment the edge count.
        edgeCount += 1;
        if (edgeCount % prog == 0) {
          System.out.println("... edge count now " + edgeCount);
        }
      }
    }
    // For the purpose of checking solutions, we need to construct a
    // distance matrix for the graph.
    distance = new int[nVertices][nVertices];
    // Initially, all distance are "infinity" except for the distance between
    // a node and itself.
    for (int i = 0; i < nVertices; i++) {
      Arrays.fill(distance[i], nVertices);
      distance[i][i] = 0;
    }
    // The distance between two nodes is 1 if they are connected by an edge.
    for (edge e : edgeSet) {
      distance[e.head()][e.tail()] = 1;
      distance[e.tail()][e.head()] = 1;
    }
    // We use the Floyd-Warshall algorithm to compute the remaining distances.
    for (int k = 0; k < nVertices; k++) {
      for (int i = 0; i < nVertices; i++) {
        for (int j = i + 1; j < nVertices; j++) {
          int x = distance[i][k] + distance[k][j];
          if (x < distance[i][j]) {
            distance[i][j] = x;
            distance[j][i] = x;
          }
        }
      }
    }
    // Compute the graph diameter.
    int d = 0;
    for (int i = 0; i < nVertices; i++) {
      d = Math.max(d, Arrays.stream(distance[i]).max().getAsInt());
    }
    diameter = d;
    // Convert the edge set into an array, while recording which edges are
    // incident at each node.
    edges = new edge[edgeSet.size()];
    incident = new ArrayList<>();
    for (int i = 0; i < nVertices; i++) {
      incident.add(new HashSet<>());
    }
    int index = 0;
    for (edge e : edgeSet) {
      edges[index] = e;
      incident.get(e.head()).add(index);
      incident.get(e.tail()).add(index);
      index++;
    }
  }

  /**
   * Connects two nodes, updates the connectedness array, and checks whether
   * all node pairs are connected.
   * @param connected matrix signaling connectedness of node pairs
   * @param i first node to connect
   * @param j second node to connect
   * @return true if all node pairs are connected
   */
  private boolean connect(final boolean[][] connected,
                          final int i, final int j) {
    connected[i][j] = true;
    connected[j][i] = true;
    boolean allConnected = true;  // are all node pairs connected?
    // Check every pair of vertices.
    for (int i0 = 0; i0 < nVertices; i0++) {
      for (int j0 = 0; j0 < nVertices; j0++) {
        // If the vertices are not connected, see if they connect through
        // the designated nodes.
        if (!connected[i0][j0]) {
          if (connected[i0][i] && connected[j0][j]) {
            connected[i0][j0] = true;
            connected[j0][i0] = true;
          } else {
            allConnected = false;
          }
        }
      }
    }
    return allConnected;
  }

  /**
   * Generates a description of the graph.
   * @return the graph description
   */
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("The graph has ").append(nVertices).append(" vertices and ")
      .append(edges.length).append(" edges.\n")
      .append("The graph diameter = ").append(diameter).append(".");
    return sb.toString();
  }

  /**
   * Record representing an edge.
   */
  private record edge(int tail, int head) {};

  /**
   * Gets the number of vertices in the graph.
   * @return the vertex count
   */
  public int getnVertices() {
    return nVertices;
  }

  /**
   * Gets the number of edges.
   * @return the edge count
   */
  public int getnEdges() {
    return edges.length;
  }

  /**
   * Gets the graph diameter.
   * @return the diameter
   */
  public int getDiameter() {
    return diameter;
  }

  /**
   * Gets the set of indices of edges incident at a given node.
   * @param node the node index
   * @return the indices of edges incident at the node
   */
  public Set<Integer> incidentAt(final int node) {
    return new HashSet<>(incident.get(node));
  }

  /**
   * Checks whether a vertex is the head of an edge.
   * @param v the index of the vertex
   * @param e the index of the edge
   * @return true if the vertex is the head of the edge
   */
  public boolean isHead(final int v, final int e) {
    return edges[e].head() == v;
  }

  /**
   * Checks a solution.
   * @param solution the proposed solution.
   * @return a string summarizing the solution
   */
  public String check(final Set<Integer> solution) {
    StringBuilder sb = new StringBuilder();
    sb.append("The proposed solution selects ").append(solution.size())
      .append(" nodes:\n");
    solution.stream().sorted().forEach(i -> sb.append("\t").append(i)
                                              .append("\n"));
    // Compute the sum of all distances to selected nodes.
    int sum = 0;
    for (int i = 0; i < nVertices; i++) {
      if (!solution.contains(i)) {
        final int[] x = distance[i];
        sum += solution.stream().mapToInt(j -> x[j]).min().getAsInt();
      }
    }
    sb.append("Sum of shortest distances to selected nodes = ")
      .append(sum).append(".");
    return sb.toString();
  }

  /**
   * Finds the set of nodes at a specified distance from a given node.
   * @param node the target node
   * @param dist the desired distance
   * @return the set of nodes (if any) at that distance from the target node
   */
  public Set<Integer> getNeighborhood(final int node, final int dist) {
    HashSet<Integer> nbd = new HashSet<>();
    for (int i = 0; i < nVertices; i++) {
      if (distance[node][i] == dist) {
        nbd.add(i);
      }
    }
    return nbd;
  }

  /**
   * Gets the distance (shortest path length) between two nodes.
   * @param i the first node
   * @param j the second node
   * @return the length of the shortest path between the nodes
   */
  public int getDistance(final int i, final int j) {
    return distance[i][j];
  }
}