graphs/others/topological-sort.js

  1. (function (exports) {
  2. 'use strict';
  3. var topologicalSort = (function () {
  4. function topologicalSortHelper(node, visited, temp, graph, result) {
  5. temp[node] = true;
  6. var neighbors = graph[node];
  7. for (var i = 0; i < neighbors.length; i += 1) {
  8. var n = neighbors[i];
  9. if (temp[n]) {
  10. throw new Error('The graph is not a DAG');
  11. }
  12. if (!visited[n]) {
  13. topologicalSortHelper(n, visited, temp, graph, result);
  14. }
  15. }
  16. temp[node] = false;
  17. visited[node] = true;
  18. result.push(node);
  19. }
  20. /**
  21. * Topological sort algorithm of a directed acyclic graph.<br><br>
  22. * Time complexity: O(|E| + |V|) where E is a number of edges
  23. * and |V| is the number of nodes.
  24. *
  25. * @public
  26. * @module graphs/others/topological-sort
  27. * @param {Array} graph Adjacency list, which represents the graph.
  28. * @returns {Array} Ordered vertices.
  29. *
  30. * @example
  31. * var topsort =
  32. * require('path-to-algorithms/src/graphs/' +
  33. * 'others/topological-sort').topologicalSort;
  34. * var graph = {
  35. * v1: ['v2', 'v5'],
  36. * v2: [],
  37. * v3: ['v1', 'v2', 'v4', 'v5'],
  38. * v4: [],
  39. * v5: []
  40. * };
  41. * var vertices = topsort(graph); // ['v3', 'v4', 'v1', 'v5', 'v2']
  42. */
  43. return function (graph) {
  44. var result = [];
  45. var visited = [];
  46. var temp = [];
  47. for (var node in graph) {
  48. if (!visited[node] && !temp[node]) {
  49. topologicalSortHelper(node, visited, temp, graph, result);
  50. }
  51. }
  52. return result.reverse();
  53. };
  54. }());
  55. exports.topologicalSort = topologicalSort;
  56. }(typeof exports === 'undefined' ? window : exports));