Skip to content

Instantly share code, notes, and snippets.

@pawohl

pawohl/findpath.js

Created January 7, 2016 07:10
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save pawohl/8fd146e033439d5772fc to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save pawohl/8fd146e033439d5772fc to your computer and use it in GitHub Desktop.
Download ZIP
Trees and Graphs
Raw
findpath.js
// ES 5.1, ES 6
'use strict';
function Node( index ) {
this.index = index;
this.children = [];
this.parents = [];
}
Node.prototype.index = undefined;
Node.prototype.parents = [];
Node.prototype.children = [];
Node.prototype.addParent = function( node ) {
if ( !( node instanceof Node ) ) {
throw new Error(
'Only node parents accepted.' );
}
this.parents.push( node );
};
Node.prototype.addChild = function( node ) {
if ( !( node instanceof Node ) ) {
throw new Error(
'Only node children accepted.' );
}
this.children.push( node );
};
Node.prototype.toString = function() {
return this.index;
};
function graph( nodes, edges ) {
edges.forEach( function( e ) {
var from = nodes[ e[ 0 ] ],
to = nodes[ e[ 1 ] ];
if ( !from || !to ) {
console.error( [ e, from, to ] );
throw new Error(
'Not a graph: ' +
'Node specified in edge ' +
'does not exist.' );
}
from.addChild( to );
to.addParent( from );
} );
}
var nodes = {};
var nodeCount = 0;
var edges = [];
var assignment = [
'Bernburg - Köthen - Bitterfeld - Delitzsch - Leipzig',
'Köthen - Dessau - Wolfen - Bitterfeld - Halle',
'Könnern - Bitterfeld',
'Bernburg - Könnern - Halle - Merseburg',
'Halle - Leipzig',
'Querfurt - Eisleben - HalleNeustadt - Halle',
'Leipzig - Merseburg - Querfurt - HalleNeustadt'
];
var roadWorks = [
['Bernburg', 'Köthen'],
['Könnern', 'Bernburg'],
['Querfurt', 'Eisleben'],
['HalleNeustadt', 'Querfurt'],
['Halle', 'Könnern'],
['Bitterfeld', 'Halle'],
['Delitzsch', 'Leipzig'],
['Merseburg', 'Leipzig'],
['Merseburg', 'Querfurt'],
['Halle', 'Merseburg']
];
function pushEdge( e1, e2, filter ) {
var push1 = true,
push2 = true,
i;
for ( i = edges.length - 1; i > -1; i-- ) {
if ( edges[ i ][ 0 ] === e1 && edges[ i ][ 1 ] === e2 ) {
push1 = false;
}
if ( edges[ i ][ 0 ] === e2 && edges[ i ][ 1 ] === e1 ) {
push2 = false;
}
}
if ( filter ) {
for ( i = roadWorks.length - 1; i > -1; i-- ) {
if ( roadWorks[ i ][ 0 ] === e1 && roadWorks[ i ][ 1 ] === e2 ) {
push1 = false;
}
if( roadWorks[ i ][ 0 ] === e2 && roadWorks[ i ][ 1 ] === e1 ) {
push2 = false;
}
}
}
if ( push1 ) {
edges.push( [ e1, e2 ] );
}
if ( push2 ) {
edges.push( [ e2, e1 ] );
}
}
function prepare( filter ) {
nodes = {};
nodeCount = 0;
edges = [];
assignment.forEach( function( rounte ) {
var cities = rounte.split( /\-/ ),
i, city, prevCity;
for ( i = 0; i < cities.length; i++ ) {
city = cities[ i ].trim();
if ( !nodes[ city ] ) {
nodes[ city ] = new Node( city );
nodeCount++;
}
if ( prevCity ) {
pushEdge( city, prevCity, filter );
}
prevCity = city;
}
} );
}
function findPath( start, destination, visited, results ) {
start.children.forEach( function( child ) {
if ( visited.indexOf( child ) === -1 ) {
var visitedNew = visited.slice();
visitedNew.push( child );
findPath( child, destination, visitedNew, results );
} else if ( visited.length === nodeCount && child === destination ) {
var visitedNew = visited.slice();
visitedNew.push( child );
results.push( visitedNew );
}
} );
return results;
}
function pathToString( visited ) {
return visited.join( ' > ' );
}
prepare( false );
graph( nodes, edges );
var results = findPath( nodes[ 'Dessau' ], nodes[ 'Dessau' ], [ nodes[ 'Dessau' ] ], [] );
results.forEach( function( result ) {
console.log( 'Dessau -> Dessau' );
console.log( pathToString( result ) );
} );
prepare( true );
graph( nodes, edges );
var results = findPath( nodes[ 'Dessau' ], nodes[ 'Merseburg' ], [ nodes[ 'Dessau' ] ], [] );
results.forEach( function( result ) {
console.log( 'Dessau -> Merseburg (Baustelle)' );
console.log( pathToString( result ) );
} );
prepare( true );
graph( nodes, edges );
var results = findPath( nodes[ 'Halle' ], nodes[ 'Halle' ], [ nodes[ 'Halle' ] ], [] );
results.forEach( function( result ) {
console.log( 'Halle -> Halle (Baustelle)' );
console.log( pathToString( result ) );
} );
roadWorks.forEach( function( roadWork ) {
prepare( true );
pushEdge( roadWork[0], roadWork[1] );
graph( nodes, edges );
var results = findPath( nodes[ 'Halle' ], nodes[ 'Halle' ], [ nodes[ 'Halle' ] ], [] );
results.forEach( function( result ) {
console.log( 'Halle -> Halle (Baustellendurchfahrt)' );
console.log( pathToString( result ) );
} );
} );
Raw
verifytree.js
// ES 5.1, ES 6
'use strict';
function Node( index ) {
this.index = index;
this.children = [];
}
Node.prototype.index = undefined;
Node.prototype.parent = undefined;
Node.prototype.children = [];
Node.prototype.setParent = function( node ) {
if ( !( node instanceof Node ) ) {
throw new Error(
'Only node parents accepted.' );
}
if ( this.parent ) {
console.error( [ node, this.parent ] );
throw new Error(
'Not a tree, not even a forest. ' +
'Multiple parents.' );
}
this.parent = node;
};
Node.prototype.addChild = function( node ) {
if ( !( node instanceof Node ) ) {
throw new Error(
'Only node children accepted.' );
}
this.children.push( node );
};
Node.prototype.getRoot = function( visited ) {
if ( !visited ) {
visited = {};
}
if ( visited[ this.index ] ) {
throw new Error( 'Not a tree. Not acyclic. ' +
'Loop (cycle) detected: ' + this.index );
}
if ( this.parent ) {
visited[ this.index ] = true;
return this.parent.getRoot( visited );
} else {
return this;
}
};
function buildTree( nodes, edges ) {
edges.forEach( function( e ) {
var from = nodes[ e[ 0 ] ],
to = nodes[ e[ 1 ] ];
if ( !from || !to ) {
console.error( [ e, from, to ] );
throw new Error(
'Not a tree, not even a graph: ' +
'Node specified in edge ' +
'does not exist.' );
}
from.addChild( to );
to.setParent( from );
} );
}
function verifyTree( nodes ) {
var root = null,
count = 0,
index, node, newRoot;
for ( index in nodes ) {
node = nodes[ index ];
if ( node ) {
newRoot = node.getRoot();
count++;
if ( !root ) {
root = newRoot;
} else if ( root !== newRoot ) {
console.error( [ root, newRoot ] );
throw new Error(
'Tree has multiple roots' );
}
}
}
console.log(
'Compared ' + count + ' roots. ' +
'All of them are the same.', root );
}
// Begin testing code
var nodes = {};
var edges = [
[ 1, 6 ],
[ 1, 7 ],
[ 1, 8 ],
[ 2, 1 ],
[ 2, 9 ],
[ 2, 12 ],
[ 3, 2 ],
[ 3, 15 ],
[ 3, 19 ],
[ 4, 3 ],
[ 4, 25 ],
[ 4, 31 ],
[ 5, 4 ],
[ 9, 10 ],
[ 9, 11 ],
[ 12, 13 ],
[ 12, 14 ],
[ 15, 16 ],
[ 15, 17 ],
[ 15, 18 ],
[ 19, 20 ],
[ 19, 21 ],
[ 19, 22 ],
[ 21, 23 ],
[ 21, 24 ],
[ 25, 26 ],
[ 25, 27 ],
[ 25, 28 ],
[ 27, 29 ],
[ 27, 30 ],
[ 31, 32 ],
[ 31, 33 ],
[ 33, 34 ],
[ 33, 35 ]
];
for ( var i = 1; i <= 35; i++ ) {
nodes[ i ] = new Node( i );
}
buildTree( nodes, edges );
verifyTree( nodes );
console.log( 'It\'s a tree!' );
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment