Skip to content

Commit ec53128

Browse files
openarunopenarun
authored
Merge branch 'master' into master
2 parents 39b77f0 + d0af94c commit ec53128

12 files changed

Lines changed: 826 additions & 5 deletions

File tree

‎BestFirstSearch/Ruby/BestFirstSearch.rb‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
require 'bfsearch'
2+
3+
class BFsearchTest < Minitest::Unit::TestCase
4+
def test_smallest_tree
5+
tree = {
6+
name: :a,
7+
next: [
8+
{
9+
name: :b,
10+
next: [
11+
{
12+
name: :goal,
13+
next: []
14+
}
15+
]
16+
},
17+
{
18+
name: :c,
19+
next: []
20+
}
21+
]
22+
}
23+
24+
distance = ->(n, m) { 1.0 }
25+
heuristic = ->(node) { 1.0 }
26+
neighbors = ->(node) { node[:next] }
27+
28+
path = BFsearch.find_path(tree, tree[:next][0][:next][0],
29+
distance, neighbors, heuristic)
30+
assert_equal 3, path.length
31+
assert_equal :goal, path[-1][:name]
32+
end
33+
34+
def test_parallel_paths
35+
tree = {
36+
sb: {
37+
i: :sb,
38+
h: 222,
39+
n: { kl: 70, ka: 145 }
40+
},
41+
wu: {
42+
i: :wu,
43+
h: 0,
44+
n: {}
45+
},
46+
kl: {
47+
i: :kl,
48+
h: 158,
49+
n: { f: 103, lu: 53 }
50+
},
51+
hn: {
52+
i: :hn,
53+
h: 87,
54+
n: { wu: 102 }
55+
},
56+
ka: {
57+
i: :ka,
58+
h: 140,
59+
n: { hn: 84 }
60+
},
61+
f: {
62+
i: :f,
63+
h: 96,
64+
n: { wu: 116 }
65+
},
66+
lu: {
67+
i: :lu,
68+
h: 108,
69+
n: { wu: 183 }
70+
}
71+
}
72+
73+
distance = ->(n, m) { n[:n][m[:i]] || 1000.0 }
74+
heuristic = ->(node) { node[:h] }
75+
neighbors = ->(node) { node[:n].keys.map { |k| tree[k] } }
76+
77+
path = BFsearch.find_path(tree[:sb], tree[:wu],
78+
distance, neighbors, heuristic)
79+
assert_equal 4, path.length
80+
assert_equal :sb, path[0][:i]
81+
assert_equal :kl, path[1][:i]
82+
assert_equal :f, path[2][:i]
83+
assert_equal :wu, path[3][:i]
84+
end
85+
86+
def test_map
87+
map = "########" +
88+
"# X #" +
89+
"# #" +
90+
"# ## #" +
91+
"# # #" +
92+
"# #" +
93+
"# S #" +
94+
"########"
95+
end
96+
end

‎CONTRIBUTING.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -129,4 +129,5 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
129129
- [mekisiel](https://github.com/mekisiel)
130130
- [tushar-dtu](https://github.com/tushar-dtu)
131131
- [AymanASamyM](https://github.com/AymanASamyM)
132-
- [arunpyasi](https://github.com/arunpyasi)
132+
- [arunpyasi](https://github.com/arunpyasi)
133+
- [Akos Kovacs](https://github.com/plaidshirtakos)

‎DepthFirstSearch/JavaScript/DFS.js‎

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
// Fully runnable code with tests at https://codepen.io/sniper6/pen/QqzYEa
2+
3+
const DFS = (graph, source, target = -1) => {
4+
// Some error handling
5+
if (typeof graph.getNeighbors !== "function") {
6+
throw "Graph should implement a getNeighbors function";
7+
}
8+
if (typeof source !== "number") {
9+
throw "source should be a number";
10+
}
11+
12+
const stack = [], // The stack that will be used
13+
order = [], // Array to hold the order of visit. Mainly for unit testing
14+
visited = {}; // Keep track of visited vertices
15+
16+
let found = false;
17+
stack.push(source);
18+
visited[source] = true;
19+
while (stack.length !== 0) {
20+
const currentVertex = stack.pop();
21+
order.push(currentVertex);
22+
const neighbors = graph.getNeighbors(currentVertex);
23+
for (const neighbor of neighbors) {
24+
if (!visited[neighbor]) {
25+
stack.push(neighbor);
26+
visited[neighbor] = true;
27+
if (neighbor === target) {
28+
found = true;
29+
}
30+
}
31+
}
32+
}
33+
return { order, found };
34+
};
35+
36+
const GraphFactory = (() => {
37+
const GraphTemplate = {
38+
init() {
39+
this._graph = [];
40+
},
41+
getNeighbors(vertex) {
42+
return this._graph[vertex] || [];
43+
},
44+
addEdge(source, target, biDirectional = true) {
45+
this._addEdge(source, target);
46+
if (biDirectional) {
47+
this._addEdge(target, source);
48+
}
49+
},
50+
_addEdge(source, target) {
51+
this._graph[source] = this._graph[source] || [];
52+
this._graph[source].push(target);
53+
},
54+
printGraph() {
55+
console.log(JSON.stringify(this._graph, null, 2));
56+
}
57+
};
58+
59+
return {
60+
getGraph() {
61+
const Graph = Object.assign({}, GraphTemplate);
62+
Graph.init();
63+
return Graph;
64+
}
65+
};
66+
})();
67+
68+
describe("DFS", () => {
69+
let graph = null;
70+
71+
beforeEach(() => {
72+
graph = GraphFactory.getGraph();
73+
});
74+
75+
it("should throw error on bad graph", () => {
76+
expect(() => {
77+
DFS({});
78+
}).toThrow("Graph should implement a getNeighbors function");
79+
});
80+
81+
it("should throw error on no source vertex", () => {
82+
expect(() => {
83+
DFS(graph);
84+
}).toThrow("source should be a number");
85+
});
86+
87+
it("simple bi-directional graph where target is reachable", () => {
88+
graph.addEdge(0, 1);
89+
graph.addEdge(0, 3);
90+
graph.addEdge(1, 2);
91+
expect(DFS(graph, 0, 3)).toEqual({
92+
order: [0, 3, 1, 2],
93+
found: true
94+
});
95+
});
96+
97+
it("complex bi-directional graph where target is reachable", () => {
98+
graph.addEdge(0, 1);
99+
graph.addEdge(0, 2);
100+
graph.addEdge(1, 3);
101+
graph.addEdge(3, 4);
102+
graph.addEdge(4, 2);
103+
expect(DFS(graph, 0, 3)).toEqual({
104+
order: [0, 2, 4, 3, 1],
105+
found: true
106+
});
107+
});
108+
109+
it("complex uni-directional graph where target is reachable", () => {
110+
graph.addEdge(0, 1, false);
111+
graph.addEdge(0, 2, false);
112+
graph.addEdge(1, 3, false);
113+
graph.addEdge(3, 4, false);
114+
graph.addEdge(4, 2, false);
115+
expect(DFS(graph, 0, 3)).toEqual({
116+
order: [0, 2, 1, 3, 4],
117+
found: true
118+
});
119+
});
120+
121+
it("simple bi-directional graph where target is not present", () => {
122+
graph.addEdge(0, 1);
123+
graph.addEdge(0, 3);
124+
graph.addEdge(1, 2);
125+
expect(DFS(graph, 0, 5)).toEqual({
126+
order: [0, 3, 1, 2],
127+
found: false
128+
});
129+
});
130+
});

Dijkstra's /C++/Dijkstras.cpp renamed to Dijkstra's/C++/Dijkstras.cpp

File renamed without changes.

‎Dijkstra's/Go/Dijkstra.go‎

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
package main
2+
3+
import (
4+
"bufio"
5+
"fmt"
6+
"log"
7+
"os"
8+
"strconv"
9+
"strings"
10+
)
11+
12+
type graph struct {
13+
edges map[int][]*edge
14+
nodes map[int]struct{}
15+
}
16+
17+
type edge struct {
18+
head int
19+
length int
20+
}
21+
22+
var shortestPaths = make(map[int]int)
23+
24+
func (g *graph) load(filename string) error {
25+
file, err := os.Open(filename)
26+
27+
if err != nil {
28+
log.Fatal(err)
29+
}
30+
defer file.Close()
31+
32+
scanner := bufio.NewScanner(file)
33+
for scanner.Scan() {
34+
edges := strings.Split(strings.TrimSpace(scanner.Text()), "\t")
35+
36+
// Convert tail vertex to number
37+
tail, err := strconv.Atoi(edges[0])
38+
if err != nil {
39+
log.Fatal(err)
40+
}
41+
42+
g.nodes[tail] = struct{}{}
43+
44+
for i := 1; i < len(edges); i++ {
45+
data := strings.Split(edges[i], ",")
46+
47+
// Convert adjacent vertex to number
48+
head, err := strconv.Atoi(data[0])
49+
if err != nil {
50+
log.Fatal(err)
51+
}
52+
53+
// Convert length to number
54+
length, err := strconv.Atoi(data[1])
55+
if err != nil {
56+
log.Fatal(err)
57+
}
58+
59+
g.nodes[head] = struct{}{}
60+
g.edges[tail] = append(g.edges[tail], &edge{head: head, length: length})
61+
}
62+
}
63+
64+
return scanner.Err()
65+
}
66+
67+
func (g *graph) dijkstra(source int) map[int]int {
68+
69+
// Create map to track distances from source vertex
70+
var u int
71+
dist := make(map[int]int)
72+
73+
// Distance from source to source is zero
74+
dist[source] = 0
75+
76+
// Initalize all distances to maximum
77+
for index := range g.nodes {
78+
if index != source {
79+
dist[index] = 32767
80+
}
81+
}
82+
83+
// Iterate over all vertices
84+
for {
85+
86+
// Check if we have nodes left
87+
if len(g.nodes) == 0 {
88+
break
89+
}
90+
91+
// Find vertex with minimum distance
92+
min := 32767
93+
for index := range g.nodes {
94+
if dist[index] < min {
95+
min = dist[index]
96+
u = index
97+
}
98+
}
99+
100+
// Remove minimum vertex
101+
delete(g.nodes, u)
102+
103+
// Calculate minimum edgde distance
104+
for _, edge := range g.edges[u] {
105+
if dist[u]+edge.length < dist[edge.head] {
106+
dist[edge.head] = dist[u] + edge.length
107+
}
108+
}
109+
}
110+
111+
return dist
112+
}
113+
114+
func main() {
115+
116+
g := &graph{}
117+
g.edges = make(map[int][]*edge)
118+
g.nodes = make(map[int]struct{})
119+
120+
log.Println("Loading graph...")
121+
g.load("dijkstraData.txt")
122+
123+
distances := g.dijkstra(1)
124+
125+
fmt.Printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n", distances[7], distances[37], distances[59], distances[82], distances[99], distances[115], distances[133], distances[165], distances[188], distances[197])
126+
}

Dijkstra's /Java/Dijkstra.java renamed to Dijkstra's/Java/Dijkstra.java

File renamed without changes.

Dijkstra's /JavaScript/Dijkstras.js renamed to Dijkstra's/JavaScript/Dijkstras.js

File renamed without changes.

Dijkstra's /Python/Dijakstra.py renamed to Dijkstra's/Python/Dijakstra.py

File renamed without changes.

0 commit comments

Comments
 (0)