Merge pull request mgechev#10 from AndreyGeonya/first-docs

mgechev · mgechev · commit 3371243b6e8b · 2015-01-09T21:21:50.000+02:00
add first docs, fix readme
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,2 @@
+node_modules
+npm-debug.log
diff --git a/gulpfile.js b/gulpfile.js
@@ -3,6 +3,6 @@ var jsdoc = require('gulp-jsdoc'),
     gulp = require('gulp');
 
 gulp.task('jsdoc', function () {
-  gulp.src('./src/**/*.js')
+  gulp.src(['./src/**/*.js', "readme.md"])
     .pipe(jsdoc('../javascript-algorithms-docs'));
 });
diff --git a/readme.md b/readme.md
@@ -1,15 +1,34 @@
-## Note
+## About
 
-Note that not all algorithms are well tested so bugs are quite possible.
+This repository contains JavaScript implementations of different famous Computer Science algorithms.
 
-## About
+API reference with usage examples available <a href="https://mgechev.github.io/javascript-algorithms/" target="_blank">here</a>.
+
+*Note: not all algorithms are well tested so bugs are quite possible.*
+
+## Development
+
+To install all dev dependencies use:
+
+```Bash
+npm install
+```
+
+To setup documentation repository:
+
+* go to the parent directory of the root of `javascript-algorithms`;
+* clone `javascript-algorithms` to directory called `javascript-algorithms-docs` (`git clone git@github.com:mgechev/javascript-algorithms.git javascript-algorithms-docs`);
+* change current branch in `javascript-algorithms-docs` to `gh-pages` (`git checkout gh-pages`).
+
+To generate documentation call:
+
+`gulp jsdocs` inside `javascript-algorithms` folder. Content of the `javascript-algorithms-docs` will be updated and you will be able to look it in your browser.
 
-This repository contains different famous Computer Science algorithms implemented in JavaScript
 
-In order to run the tests use:
+To run tests use:
 
 ```Bash
-jasmine-node test/
+./node_modules/jasmine-node/bin/jasmine-node test/
 ```
 
 and all `*.spec.js` files will be executed.
@@ -25,4 +44,4 @@ Initiate the PR.
 
 ## License
 
-The code in this repository is distributed under the terms of the MIT license.
+The code in this repository is distributed under the terms of the MIT license.
diff --git a/src/graphs/others/topological-sort.js b/src/graphs/others/topological-sort.js
@@ -1,10 +1,6 @@
 (function (exports) {
   'use strict';
 
-  /**
-   * Complexity O(|E|), where E is the set
-   * which contains all edges and |E| is their count.
-   */
   var topologicalSort = (function () {
 
     function topologicalSortHelper(node, visited, temp, graph, result) {
@@ -25,11 +21,24 @@
     }
 
     /**
-     * Implements the topological sort algorithm.
+     * Topological sort algorithm of a directed acyclic graph.<br><br>
+     * Time complexity: O(|E|) where E is a number of edges.
      *
      * @public
-     * @param {object} graph A graph represented with list of neighbors
-     * @return {array} The list containing all nodes in topological sorted order
+     * @module graphs/others/topological-sort
+     * @param {Array} graph Adjacency list, which represents the graph.
+     * @returns {Array} Ordered vertices.
+     *
+     * @example
+     * var topsort = require('path-to-algorithms/src/graphs/others/topological-sort').topologicalSort;
+     * var graph = {
+     *     v1: ['v2', 'v5'],
+     *     v2: [],
+     *     v3: ['v1', 'v2', 'v4', 'v5'],
+     *     v4: [],
+     *     v5: []
+     * };
+     * var vertices = topsort(graph); // ['v3', 'v4', 'v1', 'v5', 'v2']
      */
     return function (graph) {
       var result = [],
@@ -46,5 +55,4 @@
 
   exports.topologicalSort = topologicalSort;
 
-}(typeof exports === 'undefined' ? window : exports));
-
+}(typeof exports === 'undefined' ? window : exports));
diff --git a/src/graphs/searching/bfs.js b/src/graphs/searching/bfs.js
@@ -14,16 +14,12 @@
 
     /**
      * Breath-First graph searching algorithm.
-     * Returns the shortest path between startNode and targetNode.
-     * Time complexity O(|V|*|V|).
+     * Returns the shortest path between startNode and targetNode.<br><br>
+     * Time complexity: O(|V|^2).
      *
-     * @module graphs/searching
      * @public
-     * @param {array} graph The adjust matrix, which represents the graph
-     * @param {number} startNode The start node
-     * @param {number} targetNode The target, which should be reached
+     * @module graphs/searching/bfs
      * @param {Array} graph Adjacency matrix, which represents the graph.
-     * @returns {array} The shortest path from startNode to targetNode
      * @param {Number} startNode Start node.
      * @param {Number} targetNode Target, which should be reached.
      * @returns {Array} Shortest path from startNode to targetNode.
@@ -65,4 +61,4 @@
 
   exports.bfs = bfs;
 
-}((typeof window === 'undefined') ? module.exports : window));
+}((typeof window === 'undefined') ? module.exports : window));
diff --git a/src/graphs/searching/dfs.js b/src/graphs/searching/dfs.js
@@ -1,18 +1,8 @@
-/**
- * Depth-First Search graph searching algorithm.
- * Finds out whether there's a path between
- * two nodes - start node and a target.
- */
-
 (function (exports) {
   'use strict';
 
   var dfs = (function () {
 
-    /**
-     * Implements an iterative DFS.
-     * Complexity O(|V|^2), since it uses adjust matrix.
-     */
     function hasPath(graph, current, goal) {
       var stack = [],
           visited = [],
@@ -35,14 +25,26 @@
     }
 
     /**
-     * Returns whether there's a path between two nodes
-     * in a graph represented with adjust matrix.
+     * Depth-First graph searching algorithm.
+     * Returns whether there's a path between two nodes in a graph.<br><br>
+     * Time complexity: O(|V|^2).
      *
+     * @module graphs/searching/dfs
      * @public
-     * @param {array} graph Adjust matrix representation of a graph
-     * @param {number} start A start node
-     * @param {number} goal The target node
-     * @return {boolean} Returns whether there's a path between start and goal
+     * @param {Array} graph Adjacency matrix, which represents the graph.
+     * @param {Number} start Start node.
+     * @param {Number} goal Target node.
+     * @return {Boolean} Returns true if path between two nodes exists.
+     *
+     * @example
+     * var dfs = require('../src/graphs/searching/dfs').dfs;
+     * var graph = [[1, 1, 0, 0, 1, 0],
+     *              [1, 0, 1, 0, 1, 0],
+     *              [0, 1, 0, 1, 0, 0],
+     *              [0, 0, 1, 0, 1, 1],
+     *              [1, 1, 0, 1, 0, 0],
+     *              [0, 0, 0, 1, 0, 0]];
+     * var pathExists = dfs(graph, 1, 5); // true
      */
     return function (graph, start, goal) {
       return hasPath(graph, start, goal);
@@ -51,4 +53,4 @@
 
   exports.dfs = dfs;
 
-}(typeof exports === 'undefined' ? window : exports));
+}(typeof exports === 'undefined' ? window : exports));
diff --git a/src/graphs/shortest-path/bellman-ford.js b/src/graphs/shortest-path/bellman-ford.js
@@ -7,7 +7,42 @@
     this.weight = weight;
   }
 
-  // Complexity O(|V||E|)
+  /**
+   * Bellman–Ford algorithm computes shortest paths from a single source
+   * vertex to all of the other vertices in a weighted digraph (negative weights allowed).<br><br>
+   * Time complexity: O(|V||E|) where V and E are the number of vertices and edges respectively.
+   *
+   * @public
+   * @module graphs/shortest-path/bellman-ford
+   * @param {Array} vertexes Vertices of the graph.
+   * @param {Array} edges Edges of the graph.
+   * @param {Number} source Start vertex.
+   * @returns {Object} Object with two arrays (parents and distances) with shortest-path information.
+   *
+   * @example
+   * require('path-to-algorithms/src/graphs/shortest-path/bellman-ford');
+   * 
+   * var glob = (typeof window === 'undefined') ? global : window;
+   * var Edge = glob.Edge;
+   * var bellmanFord = glob.bellmanFord;
+   * var edges = [];
+   * var vertexes = [0, 1, 2, 3, 4];
+   * 
+   * edges.push(new Edge(0, 1, -1));
+   * edges.push(new Edge(0, 2, 4));
+   * edges.push(new Edge(1, 2, 3));
+   * edges.push(new Edge(1, 3, 2));
+   * edges.push(new Edge(3, 1, 1));
+   * edges.push(new Edge(4, 3, -3));
+   * edges.push(new Edge(1, 4, 2));
+   * edges.push(new Edge(3, 2, 5));
+   *
+   * // { 
+   * //   parents:   { '0': null, '1':  0, '2': 1, '3':  4, '4': 1 },
+   * //   distances: { '0': 0,    '1': -1, '2': 2, '3': -2, '4': 1 }
+   * // }
+   * var pathInfo = bellmanFord(vertexes, edges, 0);
+   */
   function bellmanFord(vertexes, edges, source) {
     var distances = {}, parents = {}, c;
     for (var i = 0; i < vertexes.length; i += 1) {
@@ -38,20 +73,4 @@
   global.Edge = Edge;
   global.bellmanFord = bellmanFord;
 
-}((typeof window === 'undefined') ? global : window));
-
-// var glob = (typeof window === 'undefined') ? global : window;
-// var Edge = glob.Edge;
-// var bellmanFord = glob.bellmanFord;
-// var edges = [];
-// var vertexes = [0, 1, 2, 3, 4];
-// edges.push(new Edge(0, 1, -1));
-// edges.push(new Edge(0, 2, 4));
-// edges.push(new Edge(1, 2, 3));
-// edges.push(new Edge(1, 3, 2));
-// edges.push(new Edge(3, 1, 1));
-// edges.push(new Edge(4, 3, -3));
-// edges.push(new Edge(1, 4, 2));
-// edges.push(new Edge(3, 2, 5));
-// 
-// console.log(bellmanFord(vertexes, edges, 0));
+}((typeof window === 'undefined') ? global : window));
diff --git a/src/graphs/shortest-path/dijkstra.js b/src/graphs/shortest-path/dijkstra.js
diff --git a/src/graphs/shortest-path/floyd-warshall.js b/src/graphs/shortest-path/floyd-warshall.js
diff --git a/src/graphs/shortest-path/floyd.js b/src/graphs/shortest-path/floyd.js
