Answer: Graphs

Question: Write a program to convert from an adjacency list graph representation to an adjacency matrix. Say you have the following type definitions and you want to write the AdjMatrixGraph constructor.

  struct AdjListElt {
    int neighbor;
    AdjListElt *next;
  };

  class AdjListGraph {
  private:
    int num_nodes;
    // head[i] points to the first element in the ith vertex's adjacency list
    AdjListElt **head;
    friend class AdjMatrixGraph;
  };

  class AdjMatrixGraph {
  public:
    AdjMatrixGraph(AdjListGraph *source);
  private:
    int num_nodes;
    int **matrix; // a num_nodes x num_nodes adjacency matrix
  };

Answer: This is mine; of course yours may be different.

AdjMatrixGraph::AdjMatrixGraph(AdjListGraph *source) {
  num_nodes = source->num_nodes;
  matrix = new int*[num_nodes]; // create pointers for the matrix rows
  for(int u = 0; u < num_nodes; u++) {
    matrix[u] = new int[num_nodes]; // create a row
    for(int v = 0; v < num_nodes; v++) {
      matrix[u][v] = 0; // assume there is not an edge between u and v
    }
    for(AdjListElt *n = source->head[u]; n; n = n->next) {
      matrix[u][n->neighbor] = 1; // there is an edge, so set the bit
    }
  }
}