Skip to content

Commit 798fdfd

Browse files
StepfenShawnStepfenShawn
authored
Merge pull request #125 from Nur69/master
Graph Algorithm
2 parents 31cb7fe + 0b411b9 commit 798fdfd

3 files changed

Lines changed: 271 additions & 0 deletions

File tree

‎Sorts/TopologicalSort.js‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
function TopologicalSorter() {
2+
var graph = {},
3+
isVisitedNode,
4+
finishTimeCount,
5+
finishingTimeList,
6+
nextNode;
7+
8+
this.addOrder = function (nodeA, nodeB) {
9+
nodeA = String(nodeA);
10+
nodeB = String(nodeB);
11+
graph[nodeA] = graph[nodeA] || [];
12+
graph[nodeA].push(nodeB);
13+
}
14+
15+
this.sortAndGetOrderedItems = function () {
16+
isVisitedNode = Object.create(null);
17+
finishTimeCount = 0;
18+
finishingTimeList = [];
19+
20+
for (var node in graph) {
21+
if (graph.hasOwnProperty(node) && !isVisitedNode[node]) {
22+
dfsTraverse(node);
23+
}
24+
}
25+
26+
finishingTimeList.sort(function (item1, item2) {
27+
return item1.finishTime > item2.finishTime ? -1 : 1;
28+
});
29+
30+
return finishingTimeList.map(function (value) { return value.node })
31+
}
32+
33+
function dfsTraverse(node) {
34+
isVisitedNode[node] = true;
35+
if (graph[node]) {
36+
for (var i = 0; i < graph[node].length; i++) {
37+
nextNode = graph[node][i];
38+
if (isVisitedNode[nextNode]) continue;
39+
dfsTraverse(nextNode);
40+
}
41+
}
42+
43+
finishingTimeList.push({
44+
node: node,
45+
finishTime: ++finishTimeCount
46+
});
47+
}
48+
}
49+
50+
51+
/* TEST */
52+
var topoSorter = new TopologicalSorter();
53+
topoSorter.addOrder(5, 2);
54+
topoSorter.addOrder(5, 0);
55+
topoSorter.addOrder(4, 0);
56+
topoSorter.addOrder(4, 1);
57+
topoSorter.addOrder(2, 3);
58+
topoSorter.addOrder(3, 1);
59+
console.log(topoSorter.sortAndGetOrderedItems());

‎maths/DijkstraSmallestPath.js‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
// starting at s
2+
function solve(graph, s) {
3+
var solutions = {};
4+
solutions[s] = [];
5+
solutions[s].dist = 0;
6+
7+
while(true) {
8+
var p = null;
9+
var neighbor = null;
10+
var dist = Infinity;
11+
12+
13+
for(var n in solutions) {
14+
if(!solutions[n])
15+
continue
16+
var ndist = solutions[n].dist;
17+
var adj = graph[n];
18+
19+
for(var a in adj) {
20+
21+
if(solutions[a])
22+
continue;
23+
24+
var d = adj[a] + ndist;
25+
if(d < dist) {
26+
27+
p = solutions[n];
28+
neighbor = a;
29+
dist = d;
30+
}
31+
}
32+
}
33+
34+
//no more solutions
35+
if(dist === Infinity) {
36+
break;
37+
}
38+
39+
//extend parent's solution path
40+
solutions[neighbor] = p.concat(neighbor);
41+
//extend parent's cost
42+
solutions[neighbor].dist = dist;
43+
}
44+
45+
return solutions;
46+
}
47+
//create graph
48+
var graph = {};
49+
50+
var layout = {
51+
'R': ['2'],
52+
'2': ['3','4'],
53+
'3': ['4','6','13'],
54+
'4': ['5','8'],
55+
'5': ['7','11'],
56+
'6': ['13','15'],
57+
'7': ['10'],
58+
'8': ['11','13'],
59+
'9': ['14'],
60+
'10': [],
61+
'11': ['12'],
62+
'12': [],
63+
'13': ['14'],
64+
'14': [],
65+
'15': []
66+
}
67+
68+
//convert uni-directional to bi-directional graph
69+
// var graph = {
70+
// a: {e:1, b:1, g:3},
71+
// b: {a:1, c:1},
72+
// c: {b:1, d:1},
73+
// d: {c:1, e:1},
74+
// e: {d:1, a:1},
75+
// f: {g:1, h:1},
76+
// g: {a:3, f:1},
77+
// h: {f:1}
78+
// };
79+
80+
for(var id in layout) {
81+
if(!graph[id])
82+
graph[id] = {};
83+
layout[id].forEach(function(aid) {
84+
graph[id][aid] = 1;
85+
if(!graph[aid])
86+
graph[aid] = {};
87+
graph[aid][id] = 1;
88+
});
89+
}
90+
91+
//choose start node
92+
var start = '10';
93+
//get all solutions
94+
var solutions = solve(graph, start);
95+
96+
console.log("From '"+start+"' to");
97+
//display solutions
98+
for(var s in solutions) {
99+
if(!solutions[s]) continue;
100+
console.log(" -> " + s + ": [" + solutions[s].join(", ") + "] (dist:" + solutions[s].dist + ")");
101+
}
102+
103+
// From '10' to
104+
// -> 2: [7, 5, 4, 2] (dist:4)
105+
// -> 3: [7, 5, 4, 3] (dist:4)
106+
// -> 4: [7, 5, 4] (dist:3)
107+
// -> 5: [7, 5] (dist:2)
108+
// -> 6: [7, 5, 4, 3, 6] (dist:5)
109+
// -> 7: [7] (dist:1)
110+
// -> 8: [7, 5, 4, 8] (dist:4)
111+
// -> 9: [7, 5, 4, 3, 13, 14, 9] (dist:7)
112+
// -> 10: [] (dist:0)
113+
// -> 11: [7, 5, 11] (dist:3)
114+
// -> 12: [7, 5, 11, 12] (dist:4)
115+
// -> 13: [7, 5, 4, 3, 13] (dist:5)
116+
// -> 14: [7, 5, 4, 3, 13, 14] (dist:6)
117+
// -> 15: [7, 5, 4, 3, 6, 15] (dist:6)
118+
// -> R: [7, 5, 4, 2, R] (dist:5)

‎maths/graph.js‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
// create a graph class
2+
class Graph {
3+
// defining vertex array and
4+
// adjacent list
5+
constructor(noOfVertices)
6+
{
7+
this.noOfVertices = noOfVertices;
8+
this.AdjList = new Map();
9+
}
10+
11+
// functions to be implemented
12+
13+
// addVertex(v)
14+
// addEdge(v, w)
15+
// printGraph()
16+
17+
// bfs(v)
18+
// dfs(v)
19+
}
20+
21+
// add vertex to the graph
22+
addVertex(v)
23+
{
24+
// initialize the adjacent list with a
25+
// null array
26+
this.AdjList.set(v, []);
27+
}
28+
29+
// add edge to the graph
30+
addEdge(v, w)
31+
{
32+
// get the list for vertex v and put the
33+
// vertex w denoting edge between v and w
34+
this.AdjList.get(v).push(w);
35+
36+
// Since graph is undirected,
37+
// add an edge from w to v also
38+
this.AdjList.get(w).push(v);
39+
}
40+
41+
42+
// Prints the vertex and adjacency list
43+
printGraph()
44+
{
45+
// get all the vertices
46+
var get_keys = this.AdjList.keys();
47+
48+
// iterate over the vertices
49+
for (var i of get_keys)
50+
{
51+
// great the corresponding adjacency list
52+
// for the vertex
53+
var get_values = this.AdjList.get(i);
54+
var conc = "";
55+
56+
// iterate over the adjacency list
57+
// concatenate the values into a string
58+
for (var j of get_values)
59+
conc += j + " ";
60+
61+
// print the vertex and its adjacency list
62+
console.log(i + " -> " + conc);
63+
}
64+
}
65+
66+
67+
// Example
68+
var graph = new Graph(6);
69+
var vertices = [ 'A', 'B', 'C', 'D', 'E', 'F' ];
70+
71+
// adding vertices
72+
for (var i = 0; i < vertices.length; i++) {
73+
g.addVertex(vertices[i]);
74+
}
75+
76+
// adding edges
77+
g.addEdge('A', 'B');
78+
g.addEdge('A', 'D');
79+
g.addEdge('A', 'E');
80+
g.addEdge('B', 'C');
81+
g.addEdge('D', 'E');
82+
g.addEdge('E', 'F');
83+
g.addEdge('E', 'C');
84+
g.addEdge('C', 'F');
85+
86+
// prints all vertex and
87+
// its adjacency list
88+
// A -> B D E
89+
// B -> A C
90+
// C -> B E F
91+
// D -> A E
92+
// E -> A D F C
93+
// F -> E C
94+
g.printGraph();

0 commit comments

Comments
 (0)