Notes on DFS orderings

/* Data structures and methods for graph traversal. Includes a short demonstration
 * showing different depth-first search orderings including pre-order and reverse
 * post-order.
 * Source: Open Data Structures by Pat Morin.
 */

// vertex colors
const white = 0, offwhite = 1, grey = 2, black = 3;

class Vertex {
  /** constructor() credit: Morin 12.2, 12.3.2.
   * @param {string} name vertex name
   * @param {number} index index in adjacency lists
   */
  constructor(name, index) {
    this.name = name;
    this.index = index;
    this.adjacent = [];  // indexes of adjacent vertices
    this.color = white;
  }
}

/** Represents a graph. */
class AdjacencyLists {
  #namesSet;
  /** constructor() Builds array of vertices with given names. credit: Morin 12.2.
   * @param {string[]} names names of all vertices
   */
  constructor(names) {
    this.vertices = [];  // array of Vertex's
    this.#namesSet = new Set(names);

    names = Array.from(this.#namesSet);  // remove any duplicate names
    for (var i = 0; i < names.length; i++) {
      this.vertices.push(new Vertex(names[i], i));
    }
  }

  /** getIndexFromName() get vertex index from name
   * @param {string} vertexName name of vertex to find
   * @returns {number} index of vertex, or -1 if not found
   */
  getIndexFromName(vertexName) {
    var vertex = this.vertices.find(function(a) { return a.name == vertexName; });
    if (vertex == undefined) { return -1; }
    return vertex.index;
  }

  /** addEdgeByIndex() credit: Morin 12.2.
   * @param {number} vertexIndex index of vertex to modify
   * @param {number} edgeIndex index of edge to add
   * @returns {boolean} success?
   */
  addEdgeByIndex(vertexIndex, edgeIndex) {
    if ((vertexIndex < 0) || (edgeIndex < 0) ||
        (vertexIndex >= this.vertices.length) || (edgeIndex >= this.vertices.length)) {
      return false;
    }
    this.vertices[vertexIndex].adjacent.push(edgeIndex);
    return true;
  }

  /** addEdgeByName()
   * @param {string} vertexName name of vertex to modify
   * @param {string} edgeName name of edge to add
   * @returns {boolean} success?
   */
  addEdgeByName(vertexName, edgeName) {
    var vertexIndex = this.getIndexFromName(vertexName);
    var edgeIndex = this.getIndexFromName(edgeName);
    return this.addEdgeByIndex(vertexIndex, edgeIndex);
  }

  /** outEdgesByIndex() credit: Morin 12.2.
   * @param {number} vertexIndex index of vertex to search
   * @returns {number[]} indexes of out edges, or undefined if no such vertex
   */
  outEdgesByIndex(vertexIndex) {
    if ((vertexIndex < 0) || (vertexIndex >= this.vertices.length)) {
      return undefined;
    }
    return this.vertices[vertexIndex].adjacent;
  }

  /** outEdgesByName()
   * @param {string} vertexName name of vertex to search
   * @returns {string[]} names of out edges, or undefined if no such vertex
   */
  outEdgesByName(vertexName) {
    var indexes = this.outEdgesByIndex(this.getIndexFromName(vertexName));
    if (indexes == undefined) { return undefined; }
    var names = [];
    for (var i = 0; i < indexes.length; i++) {
      names.push(this.vertices[indexes[i]].name);
    }
    return names;
  }

  /** inEdgesByIndex() credit: Morin 12.2.
   * @param {number} vertexIndex index of vertex to search
   * @returns {number[]} indexes of in edges, or undefined if no such vertex
   */
  inEdgesByIndex(vertexIndex) {
    if ((vertexIndex < 0) || (vertexIndex >= this.vertices.length)) {
      return undefined;
    }
    var edgeIndexes = [];  // array of number's
    for (var i = 0; i < this.vertices.length; i++) {
      if (this.vertices[i].adjacent.findIndex(function(a) { return a == vertexIndex; }) != -1) {
        edgeIndexes.push(i);
      }
    }
    return edgeIndexes;
  }

  /** inEdgesByName()
   * @param {string} vertexName name of vertex to search
   * @returns {string[]} names of in edges, or undefined if no such vertex
   */
  inEdgesByName(vertexName) {
    var indexes = this.inEdgesByIndex(this.getIndexFromName(vertexName));
    if (indexes == undefined) { return undefined; }
    var names = [];
    for (var i = 0; i < indexes.length; i++) {
      names.push(this.vertices[indexes[i]].name);
    }
    return names;
  }

  /** unvisited() makes all vertices undiscovered */
  unvisited() {
    for (var i = 0; i < this.vertices.length; i++) {
      this.vertices[i].color = white;
    }
  }

  /** #dfsPrePostInner() Inner depth-first search. credit: Morin 12.3.2.
   * @param {number} vertexIndex index of vertex to visit
   * @param {boolean} flag if true, pre-order vertices, else reverse post-order
   * @param {Vertex[]} if flag, pre-ordering of discovered vertices, else reverse post-ordering
   */
  #dfsPrePostInner(vertexIndex, flag, dfsVertices) {
    var vertex = this.vertices[vertexIndex];
    if (flag) { dfsVertices.push(vertex); }
    vertex.color = grey;
    var edgeIndexes = this.outEdgesByIndex(vertexIndex);
    for (var i = 0; i < edgeIndexes.length; i++) {
      var edge = this.vertices[edgeIndexes[i]];
      if (edge.color == white) {
        edge.color = grey;
        this.#dfsPrePostInner(edgeIndexes[i], flag, dfsVertices);
      }
    }
    if (!flag) { dfsVertices.unshift(vertex); }
    vertex.color = black;
  }

  /** dfsPrePost() Depth-first search. credit: Morin 12.3.2.
   * @param {number} startIndex index of vertex to start at
   * @param {boolean} flag if true, pre-order vertices, else reverse post-order
   * @returns {Vertex[]} if flag, pre-ordering of discovered vertices, else reverse post-ordering
   */
  dfsPrePost(startIndex, flag) {
    var dfsVertices = [];  // array of Vertex's

    this.#dfsPrePostInner(startIndex, flag, dfsVertices);
    this.unvisited();
    return dfsVertices;
  }

  /** dfs2Pre() Depth-first search. credit: Morin 12.3.2.
   * @param {number} startIndex index of vertex to start at
   * @returns {Vertex[]} pre-ordering of discovered vertices
   */
  dfs2Pre(startIndex) {
    var dfsVertices = [];  // array of Vertex's
    var stack = [];   // stack of indexes into this.vertices

    var vertexIndex = startIndex;
    var vertex = this.vertices[vertexIndex];
    stack.push(vertexIndex);
    while (stack.length > 0) {
      vertexIndex = stack.pop();
      vertex = this.vertices[vertexIndex];
      if (vertex.color == white) {
        vertex.color = grey;
        dfsVertices.push(vertex);
        var edgeIndexes = this.outEdgesByIndex(vertexIndex);
        for (var i = 0; i < edgeIndexes.length; i++) {  // push edge index
          stack.push(edgeIndexes[i]);
        }
      }
    }
    this.unvisited();
    return dfsVertices;
  }

  /** dfs2Post() Depth-first search.
   * @param {number} startIndex index of vertex to start at
   * @returns {Vertex[]} reverse post-ordering of discovered vertices
   */
  dfs2Post(startIndex) {
    var dfsVertices = [];  // array of Vertex's
    var stack = [];   // stack of indexes into this.vertices

    var vertexIndex = startIndex;
    var vertex = this.vertices[vertexIndex];
    stack.push(vertexIndex);
    while (stack.length > 0) {
        // peek at top of stack
      vertexIndex = stack[stack.length - 1];
      vertex = this.vertices[vertexIndex];
      if (vertex.color == white || vertex.color == offwhite) {
        vertex.color = grey;
        var edgeIndexes = this.outEdgesByIndex(vertexIndex);
        for (var i = 0; i < edgeIndexes.length; i++) {
          var edge = this.vertices[edgeIndexes[i]];
          if (edge.color == white) {  // push edge index
            stack.push(edge.index);
            edge.color = offwhite;
          }
        }
      } else {  // vertex.color == grey
        dfsVertices.unshift(vertex);
        stack.pop();
        vertex.color = black;
      }
    }
    this.unvisited();
    return dfsVertices;
  }
}

/** formatVertices()
 * @param {Vertex[]} vertices vertices to format as list
 * @returns {string} vertex names formatted as list
 */
function formatVertices(vertices) {
  var names = "";
  for (var i = 0; i < vertices.length; i++) {
    names += vertices[i].name;
    if (i < vertices.length - 1) { names += ", "; }
  }
  return "\n " + names;
}


/** names of all vertices */
var vertexNames = ["adams", "boston", "chicago", "denver", "easy", "frank", "george", "henry"];
// create vertices
var graph = new AdjacencyLists(vertexNames);
/** edges in the form [vertex][array of edge names]. */
var edges = [ ["boston"],
              ["chicago", "easy", "denver"],
              ["frank"],
              ["george"],
              ["frank", "george"],
              [],
              [],
              [] ];
// add edges
for (var i = 0; i < edges.length; i++) {
  for (var j = 0; j < edges[i].length; j++) {
    graph.addEdgeByName(vertexNames[i], edges[i][j]);
  }
}
// dfs pre-ordering
var vertices = graph.dfsPrePost(0, true);
console.log("dfs pre-ordering" + formatVertices(vertices));
// dfs reverse post-ordering
vertices = graph.dfsPrePost(0, false);
console.log("dfs reverse post-ordering" + formatVertices(vertices));
// dfs #2 pre-ordering
vertices = graph.dfs2Pre(0);
console.log("dfs #2 pre-ordering" + formatVertices(vertices));
// dfs #2 reverse post-ordering
vertices = graph.dfs2Post(0);
console.log("dfs #2 reverse post-ordering" + formatVertices(vertices));
// add two edges
graph.addEdgeByIndex(graph.getIndexFromName("george"), graph.getIndexFromName("henry"));
console.log("--added edge from george to henry--");
graph.addEdgeByName("henry", "denver");
console.log("--added edge from henry to denver--");
// edges
console.log("vertex george out edges: " + graph.outEdgesByName("george"));
console.log("vertex denver in edges: " + graph.inEdgesByName("denver"));
// dfs pre-ordering
vertices = graph.dfsPrePost(0, true);
console.log("dfs pre-ordering" + formatVertices(vertices));
// dfs reverse post-ordering
vertices = graph.dfsPrePost(0, false);
console.log("dfs reverse post-ordering" + formatVertices(vertices));
// dfs #2 pre-ordering
vertices = graph.dfs2Pre(0);
console.log("dfs #2 pre-ordering" + formatVertices(vertices));
// dfs #2 reverse post-ordering
vertices = graph.dfs2Post(0);
console.log("dfs #2 reverse post-ordering" + formatVertices(vertices));

/** @version 1.0 */