Skip to content

Instantly share code, notes, and snippets.

@4db

4db/test.js

Last active July 1, 2018 03:48
Show Gist options
  • Save 4db/d9c1229ec6876f3f8675e378c5eb2e76 to your computer and use it in GitHub Desktop.
Save 4db/d9c1229ec6876f3f8675e378c5eb2e76 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. 4db revised this gist Jul 1, 2018. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions test.js
    View file
    Original file line number Diff line number Diff line change
    @@ -58,12 +58,12 @@ function checkCycle(graph) {
    }

    (() => {
    console.log('Starting testing: Detect cycle in a graph');
    console.log('Testing started: Detect cycle in a graph');
    const it = ((description, func) => {
    console.log(' => ' + description + ' => ' + func());
    });

    it('#1 Test single root Node', () => {
    it('#1 Test single Node', () => {
    const input = new Graph(new Node(1));
    const expect = false;
    const response = checkCycle(input);
    @@ -141,7 +141,7 @@ function checkCycle(graph) {
    return 'FAILED; EXPECT:' + expect + ' !== ' + response;
    });

    it('#5 Test graph with cycle in root', () => {
    it('#5 Test graph with cycle in the root', () => {

    // / \
    // 1 -
  2. 4db revised this gist Jul 1, 2018. 1 changed file with 151 additions and 68 deletions.
    219 changes: 151 additions & 68 deletions test.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,77 +1,160 @@
    var hash = {};
    function checkLoop(node, hash) {
    if (node.children.length === 0) {
    return false;
    }
    let res = false;
    hash[node.id] = true;

    for (let i = 0; i < node.children.length; i++) {
    let n = node.children[i];

    if (hash[n.id] === true) {
    return false;
    }
    res = checkLoop(n, hash);
    if (res === false) {
    break;
    }
    }
    return res;
    class Node {
    /**
    * @param {integer|string} id
    */
    constructor(id) {
    this.id = id;
    this.children = [];
    }
    }

    class Graph {
    /**
    * @param {Node} rootNode
    */
    constructor(rootNode) {
    this.root = rootNode;
    }

    function Node(id) {
    let vm = this;
    vm.id = id;
    vm.children = [];
    return vm;
    /**
    * @param {Node} node
    * @param {Node} newNode
    * @return {Node}
    */
    add(node, newNode) {
    if (this.root === null) {
    this.root = node;
    return;
    }
    node.children.push(newNode);
    return node.children[node.children.length - 1];
    }
    }

    function Graph() {
    let vm = this;
    vm.root = null;

    vm.add = function(node) {
    if (vm.root === null) {
    vm.root = node;
    return;
    }
    if (vm.root.children.length === 0) {
    vm.root.children.push(node);
    }
    else {
    //vm.root.children[0].push(node);
    console.log(vm.root.children);
    /**
    * @param {Graph} graph
    * @return {boolean}
    */
    function checkCycle(graph) {
    if (graph.root !== null && graph.root.children.length > 0) {
    let hash = {};
    hash[graph.root.id] = true;
    let fronter = [graph.root];
    while (fronter.length) {
    var next = [];
    for (let i = 0; i < fronter.length; i++) {
    while(fronter[i].children.length) {
    if (hash[fronter[i].children[0].id] === true) {
    return true;
    }
    hash[fronter[i].children[0].id] = true
    next.push(fronter[i].children.shift());
    }
    }
    }
    fronter = next;
    }
    }
    return false;
    }

    // case #1
    var desc = 'Empty Node';
    var graph = new Graph();
    graph.add(new Node(1));
    var input = graph.root;
    var expect = false;
    if (checkLoop(input) !== expect) {
    console.log('FAIL');
    }
    else {
    console.log('PASS');
    }
    (() => {
    console.log('Starting testing: Detect cycle in a graph');
    const it = ((description, func) => {
    console.log(' => ' + description + ' => ' + func());
    });

    // case #4
    var desc = 'Is Loop';
    var graph = new Graph();
    graph.add(new Node(1));
    graph.add(new Node(2));
    graph.add(graph.root);
    console.log(graph);
    var input = graph.root;
    var expect = true;
    if (checkLoop(input) !== expect) {
    console.log('FAIL');
    }
    else {
    console.log('PASS');
    }
    it('#1 Test single root Node', () => {
    const input = new Graph(new Node(1));
    const expect = false;
    const response = checkCycle(input);
    if (expect === response) {
    return 'PASSED';
    }
    return 'FAILED; EXPECT:' + expect + ' !== ' + response;
    });

    it('#2 Test graph without cycles', () => {

    // 1
    // / | \
    // 2 3 4
    // / / \ \
    // 5 6 7 8

    let g = new Graph(new Node(1));

    g.add(g.root, new Node(2));
    g.add(g.root, new Node(3));
    g.add(g.root, new Node(4));

    g.add(g.root.children[0], new Node(5));
    g.add(g.root.children[1], new Node(6));
    g.add(g.root.children[1], new Node(7));
    g.add(g.root.children[1], new Node(8));

    const input = g;
    const expect = false;
    const response = checkCycle(input);
    if (expect === response) {
    return 'PASSED';
    }
    return 'FAILED; EXPECT:' + expect + ' !== ' + response;
    });

    it('#3 Test graph with cycle', () => {

    // 1
    // / / \
    // 2 \ /
    // 3

    let g = new Graph(new Node(1));

    g.add(g.root, new Node(2));
    g.add(g.root, new Node(3));
    g.add(g.root.children[1], g.root);

    const input = g;
    const expect = true;
    const response = checkCycle(input);
    if (expect === response) {
    return 'PASSED';
    }
    return 'FAILED; EXPECT:' + expect + ' !== ' + response;
    });

    it('#4 Test graph with cycle in children', () => {

    // / \
    // 1 - 2

    let g = new Graph(new Node(1));
    g.add(g.root, new Node(2));
    g.add(g.root.children[0], g.root);

    const input = g;
    const expect = true;
    const response = checkCycle(input);
    if (expect === response) {
    return 'PASSED';
    }
    return 'FAILED; EXPECT:' + expect + ' !== ' + response;
    });

    it('#5 Test graph with cycle in root', () => {

    // / \
    // 1 -

    let g = new Graph(new Node(1));
    g.add(g.root, g.root);

    const input = g;
    const expect = true;
    const response = checkCycle(input);
    if (expect === response) {
    return 'PASSED';
    }
    return 'FAILED; EXPECT:' + expect + ' !== ' + response;
    });
    })();
  3. 4db created this gist Jul 1, 2018.
    77 changes: 77 additions & 0 deletions test.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,77 @@
    var hash = {};
    function checkLoop(node, hash) {
    if (node.children.length === 0) {
    return false;
    }
    let res = false;
    hash[node.id] = true;

    for (let i = 0; i < node.children.length; i++) {
    let n = node.children[i];

    if (hash[n.id] === true) {
    return false;
    }
    res = checkLoop(n, hash);
    if (res === false) {
    break;
    }
    }
    return res;
    }


    function Node(id) {
    let vm = this;
    vm.id = id;
    vm.children = [];
    return vm;
    }

    function Graph() {
    let vm = this;
    vm.root = null;

    vm.add = function(node) {
    if (vm.root === null) {
    vm.root = node;
    return;
    }
    if (vm.root.children.length === 0) {
    vm.root.children.push(node);
    }
    else {
    //vm.root.children[0].push(node);
    console.log(vm.root.children);
    }
    }
    }

    // case #1
    var desc = 'Empty Node';
    var graph = new Graph();
    graph.add(new Node(1));
    var input = graph.root;
    var expect = false;
    if (checkLoop(input) !== expect) {
    console.log('FAIL');
    }
    else {
    console.log('PASS');
    }

    // case #4
    var desc = 'Is Loop';
    var graph = new Graph();
    graph.add(new Node(1));
    graph.add(new Node(2));
    graph.add(graph.root);
    console.log(graph);
    var input = graph.root;
    var expect = true;
    if (checkLoop(input) !== expect) {
    console.log('FAIL');
    }
    else {
    console.log('PASS');
    }