Graph traversal with open content

/* Data structures and methods for graph traversal. Ported from Open Data Structures
 * by Pat Morin, with improvements to make them more user-friendly. Includes a short
 * demonstration of their use.
 */

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

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;
    this.level = 1;
    this.parentName = "NULL";
    this.parentIndex = -1;
  }
}

/** 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));
    }
  }

  /** getVertexFromName() get vertex ref from name
   * @param {string} vertexName name of vertex to find
   * @returns {Vertex} the vertex, or undefined if not found
   */
  getVertexFromName(vertexName) {
    return this.vertices.find(function(a) { return a.name == vertexName; });
  }

  /** 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.getVertexFromName(vertexName);
    if (vertex == undefined) { return -1; }
    return vertex.index;
  }

  /** addVertex() ...simple, yes?
   * @param {string} vertexName name of vertex to add
   * @returns {boolean} success?
   */
  addVertex(vertexName) {
    var sizePrev = this.#namesSet.size;
    this.#namesSet.add(vertexName);
    if (this.#namesSet.size == sizePrev) { return false; }
    this.vertices.push(new Vertex(vertexName, this.vertices.length));
    return true;
  }

  /** removeVertex() ...should you need it.
   * @param {number} vertexIndex index of vertex to remove
   * @returns {boolean} success?
   */
  removeVertex(vertexIndex) {
    if ((vertexIndex < 0) || (vertexIndex >= this.vertices.length)) {
      return false;
    }
    var vertexName = this.vertices[vertexIndex].name;
    this.#namesSet.delete(vertexName);
    var bLast = false;  // removing last vertex?
    if (vertexIndex == this.vertices.length - 1) { bLast = true; }

    // remove vertex in edges and parent relationships
    for (var i = 0; i < this.vertices.length; i++) {
      var vertex = this.vertices[i];
      if (vertex.index != vertexIndex) {
        vertex.adjacent = vertex.adjacent.filter(function(a) { return a != vertexIndex; });
        if (vertex.parentIndex == vertexIndex) {
          vertex.parentName = "NULL";
          vertex.parentIndex = -1;
        }
      }
    }
    // remove the vertex
    this.vertices = this.vertices.slice(0, vertexIndex).concat(this.vertices.slice(vertexIndex + 1));
    // decrement indexes where needed
    if (!bLast) {
      for (var i = 0; i < this.vertices.length; i++) {
        var vertex = this.vertices[i];
        if (vertex.index > vertexIndex) { vertex.index--; }
        if (vertex.parentIndex > vertexIndex) { vertex.parentIndex--; }
        for (var j = 0; j < vertex.adjacent.length; j++) {
          if (vertex.adjacent[j] > vertexIndex) { vertex.adjacent[j]--; }
        }
      }
    }
    return true;
  }

  /** 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);
  }

  /** removeEdgeByIndex() credit: Morin 12.2.
   * @param {number} vertexIndex index of vertex to modify
   * @param {number} edgeIndex index of edge to remove
   * @returns {boolean} success?
   */
  removeEdgeByIndex(vertexIndex, edgeIndex) {
    if ((vertexIndex < 0) || (vertexIndex >= this.vertices.length)) {
      return false;
    }
    var vertex = this.vertices[vertexIndex];
    var index = vertex.adjacent.findIndex(function(a) { return a == edgeIndex; });
    if (index == -1) { return false; }
    vertex.adjacent = vertex.adjacent.slice(0, index).concat(vertex.adjacent.slice(index + 1));
    return true;
  }

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

  /** hasEdgeByIndex() credit: Morin 12.2.
   * @param {number} vertexIndex index of vertex to search
   * @param {number} edgeIndex index of edge to find
   * @returns {boolean} true if edge found
   */
  hasEdgeByIndex(vertexIndex, edgeIndex) {
    if ((vertexIndex < 0) || (vertexIndex >= this.vertices.length)) {
      return false;
    }
    var index = this.vertices[vertexIndex].adjacent.findIndex(function(a) { return a == edgeIndex; });
    if (index == -1) { return false; }
    return true;
  }

  /** hasEdgeByName()
   * @param {string} vertexName name of vertex to search
   * @param {string} edgeName name of edge to find
   * @returns {boolean} true if edge found
   */
  hasEdgeByName(vertexName, edgeName) {
    var vertexIndex = this.getIndexFromName(vertexName);
    var edgeIndex = this.getIndexFromName(edgeName);
    return this.hasEdgeByIndex(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;
  }

  /** flat() makes all vertices have depth of 1 and no parent */
  flat() {
    for (var i = 0; i < this.vertices.length; i++) {
      this.vertices[i].level = 1;
      this.vertices[i].parentName = "NULL";
      this.vertices[i].parentIndex = -1;
    }
  }

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

  /** bfs() Breadth-first search. The original method obtains neither vertex parent nor vertex
   *  level, and neither is obtained here. credit: Morin 12.3.1.
   * @param {number} startIndex index of vertex to start at
   * @returns {Vertex[]} discovered vertices
   */
  bfs(startIndex) {
    var bfsVertices = [];  // array of Vertex's
    var queue = [];   // queue of indexes into this.vertices

    this.flat();
    var vertexIndex = startIndex;
    var vertex = this.vertices[vertexIndex];
    queue.push(vertexIndex);
    vertex.color = grey;
    while (queue.length > 0) {
      vertexIndex = queue.shift();
      bfsVertices.push(this.vertices[vertexIndex]);
      var edgeIndexes = this.outEdgesByIndex(vertexIndex);
      for (var i = 0; i < edgeIndexes.length; i++) {
        var edge = this.vertices[edgeIndexes[i]];
        if (edge.color == white) {
          queue.push(edgeIndexes[i]);
          edge.color = grey;
        }
      }
    }
    this.unvisited();
    return bfsVertices;
  }

  /** #dfsInner() Inner depth-first search. credit: Morin 12.3.2.
   * @param {number} vertexIndex index of vertex to visit
   * @param {Vertex[]} dfsVertices discovered vertices
   */
  #dfsInner(vertexIndex, dfsVertices) {
    var vertex = this.vertices[vertexIndex];
    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.#dfsInner(edgeIndexes[i], dfsVertices);
      }
    }
    dfsVertices.unshift(vertex);
    vertex.color = black;
  }

  /** dfs() Depth-first search. The original method obtains neither vertex parent nor vertex
   *  level, and neither is obtained here. credit: Morin 12.3.2.
   * @param {number} startIndex index of vertex to start at
   * @returns {Vertex[]} discovered vertices
   */
  dfs(startIndex) {
    var dfsVertices = [];  // array of Vertex's

    this.flat();
    this.#dfsInner(startIndex, dfsVertices);
    this.unvisited();
    return dfsVertices;
  }

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

    this.flat();
    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;
  }

  /** bfsoTraverse() Traverse given breadth-first search order vertices to obtain their parents and
   *  levels. There are a couple inefficiencies.
   * --You could create the spanning tree by starting a graph with the same vertices and adding the
   * same edge between vertices when they are found to be adjacent.
   * @param {Vertex[]} bfsVertices vertices in breadth-first search order where first vertex is root
   */
  bfsoTraverse(bfsVertices) {
    var cur = 1;   // index into bfsVertices

    if (bfsVertices.length < 2) { return; }
    var level = bfsVertices[cur].level;
    do {
      var bAdjacent = false;
      for (var i = 0; i < cur && !bAdjacent; i++) {
        if (bfsVertices[i].color == white &&
              this.hasEdgeByIndex(bfsVertices[i].index, bfsVertices[cur].index)) {
          var levelPrev = level;
          bfsVertices[cur].level = bfsVertices[i].level + 1;
          bfsVertices[cur].parentName = bfsVertices[i].name;
          bfsVertices[cur].parentIndex = bfsVertices[i].index;
          level = bfsVertices[cur].level;
          bAdjacent = true;
          if (level != levelPrev) {  // level change
            for (var j = 0; j < i; j++) {
              if (bfsVertices[j].level < level - 1) {
                bfsVertices[j].color = grey;
              }
            }
          }
        }
      }
      cur++;
    } while (cur < bfsVertices.length);
    this.unvisited();
  }

  /** dfsoTraverse() Traverse given depth-first search order vertices to obtain their parents and
   *  levels. There are a couple inefficiencies.
   * --You could create the spanning tree by starting a graph with the same vertices and adding the
   * same edge between vertices when they are found to be adjacent.
   * @param {Vertex[]} dfsVertices vertices in depth-first search order where first vertex is root
   */
  dfsoTraverse(dfsVertices) {
    var prev = 0, cur = 1;   // indexes into dfsVertices

    if (dfsVertices.length < 2) { return; }
    do {
      if (this.hasEdgeByIndex(dfsVertices[prev].index, dfsVertices[cur].index)) {
        dfsVertices[cur].level = dfsVertices[prev].level + 1;
        dfsVertices[cur].parentName = dfsVertices[prev].name;
        dfsVertices[cur].parentIndex = dfsVertices[prev].index;
      } else {
        var bAdjacent = false;
        for (var i = 0; i < prev && !bAdjacent; i++) {
          if (dfsVertices[i].color == white &&
                this.hasEdgeByIndex(dfsVertices[i].index, dfsVertices[cur].index)) {
            dfsVertices[cur].level = dfsVertices[i].level + 1;
            dfsVertices[cur].parentName = dfsVertices[i].name;
            dfsVertices[cur].parentIndex = dfsVertices[i].index;
            for (var j = i + 1; j <= prev; j++) {
              dfsVertices[j].color = grey;
            }
            bAdjacent = true;
          }
        }
      }
      prev = cur++;
    } while (cur < dfsVertices.length);
    this.unvisited();
  }
}

/** formatVertices()
 * --You could append the parent name.
 * @param {Vertex[]} vertices vertices to format as tree
 * @returns {string} vertex names formatted as tree
 */
function formatVertices(vertices) {
  var retVertices = "";
  for (var i = 0; i < vertices.length; i++) {
    retVertices += '\n' + " ".repeat(vertices[i].level) + vertices[i].name;
  }
  return retVertices;
}


/** names of all vertices */
var vertexNames = ["zero", "one", "two", "three", "four", "five",
                  "six", "seven", "eight", "nine", "ten", "eleven"];
// create vertices
var graph = new AdjacencyLists(vertexNames);
/** edges in the form [vertex][array of edge indexes].
  * This is the example graph in Morin Figure 12.3.
  */
var edges = [ [1, 4],
              [0, 2, 6, 5],
              [1, 3, 6],
              [2, 7],
              [0, 5, 8],
              [1, 2, 6, 9, 4],
              [5, 2, 7, 10],
              [6, 3, 11],
              [4, 9],
              [8, 5, 10],
              [9, 6, 11],
              [10, 7] ];
// add edges
for (var i = 0; i < edges.length; i++) {
  for (var j = 0; j < edges[i].length; j++) {
    graph.addEdgeByName(vertexNames[i], vertexNames[edges[i][j]]);
  }
}
// breadth-first search
var vertices = graph.bfs(0);
graph.bfsoTraverse(vertices);
console.log("breadth-first search" + formatVertices(vertices));
// depth-first search
vertices = graph.dfs(0);
graph.dfsoTraverse(vertices);
console.log("depth-first search" + formatVertices(vertices));
// depth-first search #2
vertices = graph.dfs2(0);
graph.dfsoTraverse(vertices);
console.log("depth-first search #2" + formatVertices(vertices));
// breadth-first search starting at vertex one
vertices = graph.bfs(graph.getIndexFromName("one"));
graph.bfsoTraverse(vertices);
console.log("breadth-first search starting at vertex one" + formatVertices(vertices));
// remove a pair of edges
console.log("vertex one out edges: " + graph.outEdgesByName("one"));
console.log("vertex two in edges: " + graph.inEdgesByName("two"));
graph.removeEdgeByName("one", "two");
graph.removeEdgeByIndex(2, 1);
console.log("--removed edges between vertices one and two--");
console.log("vertex one out edges (by index): " + graph.outEdgesByIndex(1));
console.log("vertex two in edges (by index): " + graph.inEdgesByIndex(2));
// depth-first search
vertices = graph.dfs(0);
graph.dfsoTraverse(vertices);
console.log("depth-first search" + formatVertices(vertices));
// restore edges
graph.addEdgeByIndex(1, 2);
graph.addEdgeByName ("two", "one");
console.log("--restored edges between vertices one and two--");
// remove a vertex
graph.removeVertex(graph.getIndexFromName("eleven"));
console.log("--removed vertex eleven--");
// depth-first search
vertices = graph.dfs(0);
graph.dfsoTraverse(vertices);
console.log("depth-first search" + formatVertices(vertices));

/** @version 1.0f */