Topological sort of directed graph

/* Data structures and methods for topological sort of directed graph. Includes
 * a short demonstration.
 * Sources:
 * 1. Open Data Structures by Pat Morin.
 * 2. Communications of the ACM, "Topological sorting of large networks" by
 *    Arthur Kahn.
 */

class Vertex {
  /** constructor() credit: Morin 12.2, 12.3.1.
   * @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.inEdges;    // edges in the form [(index | -1 if discovered)*]
    this.bSeen = false;
  }
}

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

  /** outDegreeByIndex() credit: Morin AdjacencyLists.java.
   * @param {number} vertexIndex index of vertex to search
   * @returns {number} out degree of vertex, or -1 if no such vertex
   */
  outDegreeByIndex(vertexIndex) {
    if ((vertexIndex < 0) || (vertexIndex >= this.vertices.length)) {
      return -1;
    }
    return this.vertices[vertexIndex].adjacent.length;
  }

  /** outDegreeByName()
   * @param {string} vertexName name of vertex to search
   * @returns {number} out degree of vertex, or -1 if no such vertex
   */
  outDegreeByName(vertexName) {
    return this.outDegreeByIndex(this.getIndexFromName(vertexName));
  }

  /** inDegreeByIndex() credit: Morin AdjacencyLists.java.
   * @param {number} vertexIndex index of vertex to search
   * @returns {number} in degree of vertex, or -1 if no such vertex
   */
  inDegreeByIndex(vertexIndex) {
    if ((vertexIndex < 0) || (vertexIndex >= this.vertices.length)) {
      return -1;
    }
    var count = 0;
    for (var i = 0; i < this.vertices.length; i++) {
      if (this.vertices[i].adjacent.findIndex(function(a) { return a == vertexIndex; }) != -1) {
        count++;
      }
    }
    return count;
  }

  /** inDegreeByName()
   * @param {string} vertexName name of vertex to search
   * @returns {number} in degree of vertex, or -1 if no such vertex
   */
  inDegreeByName(vertexName) {
    return this.inDegreeByIndex(this.getIndexFromName(vertexName));
  }

  /** #getEdgeCount() Get number of undiscovered edges.
   * @param {number[]} edges indexes to search
   * @returns {number} edge count
   */
  #getEdgeCount(edges) {
    var count = 0;
    for (var i = 0; i < edges.length; i++) {
      if (edges[i] != -1) { count++; }
    }
    return count;
  }

  /** #removeEdge() Mark edge as discovered.
   * @param {number[]} edges indexes to search
   * @param {number} edge index into this.vertices
   */
  #removeEdge(edges, edge) {
    var index = edges.findIndex(function(a) { return a == edge; });
    edges[index] = -1;
  }

  /** unseen() makes all vertices undiscovered */
  unseen() {
    for (var i = 0; i < this.vertices.length; i++) {
      this.vertices[i].inEdges = undefined;
      this.vertices[i].bSeen = false;
    }
  }

  /** bfTopo() Breadth-first topological sort. credit: Kahn.
   * @returns {Vertex[]} sorted vertices, or undefined if graph is cyclic
   */
  bfTopo() {
    var bfVertices = [];  // array of Vertex's
    var queue = [];   // indexes of vertices with in degree zero

    this.unseen();
    for (var i = 0; i < this.vertices.length; i++) {
      var res = this.inEdgesByIndex(i);
      this.vertices[i].inEdges = res;
      if (this.#getEdgeCount(res) == 0) {
        queue.push(i);
        this.vertices[i].bSeen = true;
      }
    }
    if (queue.length == 0) { return undefined; }
    while (queue.length > 0) {
      var vertexIndex = queue.shift();
      bfVertices.push(this.vertices[vertexIndex]);
      var edgeIndexes = this.outEdgesByIndex(vertexIndex);
      for (var i = 0; i < edgeIndexes.length; i++) {
        var edge = this.vertices[edgeIndexes[i]];
        this.#removeEdge(edge.inEdges, vertexIndex);
        if (this.#getEdgeCount(edge.inEdges) == 0) {
          queue.push(edge.index);
          edge.bSeen = true;
        }
      }
    }
    for (var i = 0; i < this.vertices.length; i++) {
      if (this.#getEdgeCount(this.vertices[i].inEdges) > 0) { return undefined; }
    }
    return bfVertices;
  }

  /** #topoInner() Inner depth-first topological sort. credit: Kahn.
   * @param {number} vertexIndex index of vertex to visit
   * @param {Vertex[]} dfVertices sorted vertices
   */
  #topoInner(vertexIndex , dfVertices) {
    var vertex = this.vertices[vertexIndex];
    vertex.bSeen = true;
    var edgeIndexes = this.outEdgesByIndex(vertexIndex);
    for (var i = 0; i < edgeIndexes.length; i++) {
      var edge = this.vertices[edgeIndexes[i]];
      this.#removeEdge(edge.inEdges, vertexIndex);
      edge.bSeen = true;
      if (this.#getEdgeCount(edge.inEdges) == 0) {
        this.#topoInner(edge.index, dfVertices);
      }
    }
    dfVertices.unshift(vertex);
  }

  /** topo() Depth-first topological sort. credit: Kahn.
   * @returns {Vertex[]} sorted vertices, or undefined if graph is cyclic
   */
  topo() {
    var dfVertices = [];  // array of Vertex's
    var stack = [];   // indexes of vertices with in degree zero

    this.unseen();
    for (var i = 0; i < this.vertices.length; i++) {
      var res = this.inEdgesByIndex(i);
      this.vertices[i].inEdges = res;
      if (this.#getEdgeCount(res) == 0) { stack.push(i); }
    }
    if (stack.length == 0) { return undefined; }
    while (stack.length > 0) {
      var vertexIndex = stack.pop();
      this.#topoInner(vertexIndex, dfVertices);
    }
    for (var i = 0; i < this.vertices.length; i++) {
      if (this.#getEdgeCount(this.vertices[i].inEdges) > 0) { return undefined; }
    }
    return dfVertices;
  }

  /** topo2() Depth-first topological sort. credit: Kahn.
   * @returns {Vertex[]} sorted vertices, or undefined if graph is cyclic
   */
  topo2() {
    var dfVertices = [];  // array of Vertex's
    var stack = [];   // indexes of vertices with in degree zero

    this.unseen();
    for (var i = 0; i < this.vertices.length; i++) {
      var res = this.inEdgesByIndex(i);
      this.vertices[i].inEdges = res;
      if (this.#getEdgeCount(res) == 0) { stack.push(i); }
    }
    if (stack.length == 0) { return undefined; }
    while (stack.length > 0) {
      var vertexIndex = stack.pop();
      var vertex = this.vertices[vertexIndex];
      dfVertices.push(vertex);
      if (!vertex.bSeen) {
        vertex.bSeen = true;
        var edgeIndexes = this.outEdgesByIndex(vertexIndex);
        for (var i = 0; i < edgeIndexes.length; i++) {
          var edge = this.vertices[edgeIndexes[i]];
          this.#removeEdge(edge.inEdges, vertexIndex);
          if (this.#getEdgeCount(edge.inEdges) == 0) {
            stack.push(edge.index);
          }
        }
      }
    }
    for (var i = 0; i < this.vertices.length; i++) {
      if (this.#getEdgeCount(this.vertices[i].inEdges) > 0) { return undefined; }
    }
    return dfVertices;
  }

  /** formatVertices()
   * @param {Vertex[]} vertices vertices in this graph to format as list,
   *                   or undefined if graph is cyclic
   * @returns {string} vertex names (start vertices followed by asterisk) formatted as list
   */
  formatVertices(vertices) {
    if (vertices == undefined) { return "\n error: graph is cyclic"; }
    var names = "";
    for (var i = 0; i < vertices.length; i++) {
      names += vertices[i].name;
      if (this.inDegreeByIndex(vertices[i].index) == 0) { names += "*"; }
      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]);
  }
}
// edges and degrees
console.log("out degree of george = " + graph.outDegreeByIndex(graph.getIndexFromName("george")));
console.log("vertex frank in edges: " + graph.inEdgesByName("frank"));
console.log("in degree of frank = " + graph.inDegreeByName("frank"));
// bf sort
var vertices = graph.bfTopo();
console.log("bf sort" + graph.formatVertices(vertices));
// df sort
vertices = graph.topo();
console.log("df sort" + graph.formatVertices(vertices));
// df sort #2
vertices = graph.topo2();
console.log("df sort #2" + graph.formatVertices(vertices));
// add an edge
graph.addEdgeByName("george", "frank");
console.log("--added edge from george to frank--");
// edges and degrees
console.log("vertex george out edges: " + graph.outEdgesByName("george"));
console.log("out degree of george = " + graph.outDegreeByName("george"));
console.log("in degree of frank = " + graph.inDegreeByIndex(graph.getIndexFromName("frank")));
// bf sort
vertices = graph.bfTopo();
console.log("bf sort" + graph.formatVertices(vertices));
// df sort
vertices = graph.topo();
console.log("df sort" + graph.formatVertices(vertices));
// add another edge
graph.addEdgeByName("chicago", "adams");
console.log("--added edge from chicago to adams, creating a cycle--");
// degrees
console.log("out degree of chicago = " + graph.outDegreeByName("chicago"));
console.log("in degree of adams = " + graph.inDegreeByName("adams"));
// bf sort
vertices = graph.bfTopo();
console.log("bf sort" + graph.formatVertices(vertices));
// df sort
vertices = graph.topo();
console.log("df sort" + graph.formatVertices(vertices));

/** @version 1.0a */