0%

Bellman-Ford Algorithm is slower than Dijkstra. But it can handle graph contains a negative cycle.

Time Complexity: E * V

  • E is the number of edges
  • V is the number of vertexs

Implementation

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#!/usr/local/bin/python3

import math
from typing import List
from collections import defaultdict

def bellman_ford(vertexs: int, edges: List[List[int]], origin: int, destination: int):
'''
print shortest path from origin to destination
Args:
vertexs: number of vertexs. First vertex is 0.
edges: list of (start, end, weight)
origin: -
destination: -
Raise:
ValueError: if destination is not reachable from origin
or a negative cycle is found
'''
# prepare data
dist, prev = defaultdict(lambda: math.inf), [None] * vertexs
dist[origin] = 0
# relex edges
for _ in range(vertexs):
upd = 0
for u, v, w in edges:
# find a shorter path
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
upd += 1
if upd == 0: # quick exit
break
# check for negative cycle
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError('Negative cycle is found')
# build path
path, cur = [], destination
while cur != origin and prev[cur] is not None:
path.append(cur)
cur = prev[cur]
if cur != origin:
raise ValueError(f'{destination} is not reachable from {origin}')
path = [origin] + path[::-1]
print('->'.join([str(vertex) for vertex in path]))

# regular graph with negative weight
bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, -1]], 0, 4)
# negative cycle
bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, -1], [2, 4, 10], [3, 4, -1], [4, 1, -1]], 0, 4)
1
2
3
4

<!-- more -->

## Test Case

regular graph with negative weight

+-+                  +-+

+-2—–>+1| |4+<–+
| +++ +++ |
+++ | +-+ ^ |
|0| +–3—–>+3+—(-1)-+ |
+++ +-+ |
| +-+ |
+–5—->+2+—————-10——+
+-+

negative cycle

+-+                  +-+

+-2—–>+1+<——-(-1)——+4+<–+
| +++ +++ |
+++ | +-+ ^ |
|0| +-(-1)—>+3+—(-1)-+ |
+++ +-+ |
| +-+ |
+–5—->+2+—————-10——+
+-+

```

Dijkstra Algorithm is the known fastest algorithm to find the shortest path in a graph with unbounded non-negative weights.

Time Complexity: E + V*log(V)

  • E is the number of edges
  • V is the number of vertexs

Implementation

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#!/usr/local/bin/python3

from typing import List
from collections import defaultdict
import heapq
import math

def dijkstra(vertexs: int, edges: List[List[int]], origin: int, destination: int):
'''
print shortest path from origin to destination
Args:
vertexs: number of vertexs. First vertex is 0.
edges: list of (start, end, weight)
origin: -
destination: -
Raise:
ValueError: if destination is not reachable from origin
'''
graph = defaultdict(dict)
# build graph
for u, v, w in edges:
graph[u][v] = w
# prepare data
dist, prev = defaultdict(lambda: math.inf), [None] * vertexs
dist[origin] = 0
heap = [(0, origin)]
# relax edges
while heap:
_, u = heapq.heappop(heap)
for v, w in graph[u].items():
# if neighbor is not reachable or find a shorter path
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# build path
path, cur = [], destination
while cur != origin and prev[cur] is not None:
path.append(cur)
cur = prev[cur]
if cur != origin:
raise ValueError(f'{destination} is not reachable from {origin}')
path = [origin] + path[::-1]
print('->'.join([str(point) for point in path]))

dijkstra(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4)
Read more »

I wrote post Binary_Tree_Traversal around two years ago to help me remember how to traversal binary tree iteratively.
The solution in that post is quite simply. But I still have trouble to remember it since the code pattern is slight different within preorder, inorder, postorder.

Eventually, I rewrite the code using similar pattern in python.

preorder

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def preorderTraversal(self, root):
rst, stack = [], []
cur = root
while cur or stack:
while cur:
rst.append(cur.val)
stack.append(cur.right)
cur = cur.left
cur = stack.pop()
return rst

inorder

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
rst, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
rst.append(cur.val)
cur = cur.right
return rst

postorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
rst, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left or cur.right
cur = stack.pop()
rst.append(cur.val)
if stack and stack[-1].left == cur:
cur = stack[-1].right
else:
cur = None
return rst

Bottom Up Parsing

Source Code

Chapter 7.1

Simple C++ implementation of BFS based bottom up parser

Usage

1
2
3
4
5
6
7
8
9
10
11
12
13
14

» ./bin/buttomUpParser ../data/rules.dat
S
S -> aaa
S -> Sab
S -> aSb

input: aaaab
2 valid solutions found
aaaab --(S -> aaa)-- Sab --(S -> Sab)-- S

aaaab --(S -> aaa)-- aSb --(S -> aSb)-- S

-------------------

Theory

Unger’s Method

Source Code

please find library ascii_tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// unger.h
// Created by Yong Cao at Dec/22/2017
//
//

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <stdio.h>
#include "ascii_tree.h"


using std::string;
using std::vector;
using std::unordered_map;
using AsciiTree::Tree;
using AsciiTree::Node;


class Parser {

public:

Parser(const string& grammar);
bool parse(const string& pattern, const string& input);

void print_grammar() {
printf("-----grammar------\n");
for (auto& rule : grammar_) {
for (auto& right : rule.second) {
printf("%c -> %s\n", rule.first, right.c_str());
}
}
}

private:
bool parse(const string& pattern, const string& input, Node* node);
unordered_map<char, vector<string>> grammar_;
Tree ptree_;
};

class Rule {
public:
char left;
vector<char> right;

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// unger.cpp
// Created by Yong Cao at Dec/22/2017
//
#include "unger.h"
#include <fstream>
#include <queue>

using namespace std;

Parser::Parser(const string& grammar) {

ifstream file(grammar);
string line;

while (getline(file, line)) {
grammar_[line[0]].push_back(line.substr(5));
}

}

bool Parser::parse(const string& pattern, const string& input) {

printf("ROOT:%s\n", pattern.c_str());
printf("input:%s\n", input.c_str());
ptree_.reset();
ptree_.set_root(pattern);
bool rc = parse(pattern, input, ptree_.get_root());
ptree_.print_tree();
return rc;
}

// dfs
bool Parser::parse(const string& pattern, const string& input, Node* node) {

if (pattern == input && pattern.size() == 1) {
//node->children.push_back(make_shared<Node>(pattern));
return true;
}

if (pattern.size() > input.size())
return false;
if (pattern.size() == 1) {
for (auto& input_left : grammar_[pattern[0]]) {
node->children.push_back(make_shared<Node>(input_left));
if (parse(input_left, input, node->children.back().get())) {
return true;
}
node->children.pop_back();
}
return false;
}

for (int len = 1; len < input.size(); len++) {
string pattern_left = pattern.substr(0, 1), pattern_remain = pattern.substr(1);
string input_left = input.substr(0, len), input_remain = input.substr(len);

node->children.push_back(make_shared<Node>(pattern_left));
auto ptr_left = node->children.back().get();
auto ptr_right = node;

if (pattern_remain.size() == 1) {
node->children.push_back(make_shared<Node>(pattern_remain));
ptr_right = node->children.back().get();
}
if (parse(pattern_left, input_left, ptr_left) &&
parse(pattern_remain, input_remain, ptr_right)) {
return true;
}
if (pattern_remain.size() == 1) {
node->children.pop_back();
}
node->children.pop_back();
}


return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// main.cpp
// Created by Yong Cao at Dec/22/2017
//


#include "unger.h"

using namespace std;

int main() {

Parser parser("../data/grammar.dat");

parser.print_grammar();

printf("----parsing process----\n");

string input;
while (true) {
cin >> input;
parser.parse("E", input);
}

return 0;
}

Sample output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
-----grammar------
T -> T*a
T -> a
E -> E+T
E -> T
----parsing process----
a+a*a*a+a+a
ROOT:E
input:a+a*a*a+a+a
(E)
`--(E+T)
`--(E)
| `--(E+T)
| `--(E)
| | `--(E+T)
| | `--(E)
| | | `--(T)
| | | `--[a]
| | `--[+]
| | `--(T)
| | `--(T*a)
| | `--(T)
| | | `--(T*a)
| | | `--(T)
| | | | `--[a]
| | | `--[*]
| | | `--[a]
| | `--[*]
| | `--[a]
| `--[+]
| `--(T)
| `--[a]
`--[+]
`--(T)
`--[a]

Given a formatted log file, find the top 3 most frequency command.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
~/shell » cat input.txt                                                                                                               ubuntu@ip-172-31-17-20
yong ls
hao man
yong cd
yong cd
yong grep
yong ls
yong ls

~/shell » sort -k 2,2 input.txt | cut -d ' ' -f 2 | uniq \
| xargs -I{} sh -c 'echo -n "{}\t"; grep {} -c input.txt' \
| sort -r -k 2,2 | head -3

ls 3
cd 2
man 1

Algorithm R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//
// Algorithm R
//
#include <yong/head.h>

// rand [low, high)
int Rand(int low, int high);

class Solution {
public:
vector<int> func(vector<int>& vec, int k) {
vector<int> ret(k);
// fill reservior array
for (int i = 0; i < k; i++)
ret[i] = vec[i];

// replace element with gradually decreasing probability
for (int i = k, n = vec.size(); i < n; i++) {
int val = Rand(0, i);
if (val < k) {
ret[val] = vec[i];
}
}
return ret;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <yong/head.h>

class Solution {
int Badness(int page_width, vector<string>& words, int start, int end) {
int width = accumulate(words.begin() + start, words.begin() + end, 0, [](int a, string& b) {
return a + b.size() + 1;
});
// not fit
if (width > page_width)
return numeric_limits<int>::max();
//
return pow(page_width - width, 3);
}

int helper(vector<string>& words, vector<int>& split_points, vector<int>& memo, int start, int page_width) {
if (memo[start] != -1)
return memo[start];
if (start >= words.size())
return 0;
int badness = numeric_limits<int>::max(), split_point = 0;
for (int j = start + 1; j <= words.size(); j++) {
// avoid overflow
int badness_j = Badness(page_width, words, start, j),
badness_suffix = helper(words, split_points, memo, j, page_width);
if (numeric_limits<int>::max() - badness_j >= badness_suffix) {
badness_j += badness_suffix;
} else {
badness_j = numeric_limits<int>::max();
}

// better split point
if (badness_j < badness) {
split_point = j;
badness = badness_j;
}
}
split_points[start] = split_point;
return memo[start] = badness;
}
public:
vector<vector<string>> Justification(vector<string>& words, int page_width) {
vector<int> memo(words.size(), -1);
vector<int> split_points(words.size());

helper(words, split_points, memo, 0, page_width);

// build lines
vector<vector<string>> lines;
int split = 0;
while (split != words.size()) {
vector<string> line(words.begin() + split, words.begin() + split_points[split]);
lines.push_back(move(line));
split = split_points[split];
}

return lines;
}

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Time: E + V * log(V)
#include <yong/head.h>

class Graph {
public:
Graph(vector<pair<string, string>>& edges, vector<int>& weights) {
for (int i = 0, n = edges.size(); i < n; i++) {
vertexs_.insert(edges[i].first);
vertexs_.insert(edges[i].second);

edges_[edges[i].first][edges[i].second] = weights[i];
edges_[edges[i].second][edges[i].first] = weights[i];
}
}

vector<pair<string, int>> FindPath(const string& source, const string& destination) {
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
unordered_map<string, int> dist;
unordered_map<string, string> prev;

pq.push({0, source});
dist[source] = 0;

while (!pq.empty()) {
string u = pq.top().second;

pq.pop();

// update dist of vertex u 's neighbor
for (auto iter = edges_[u].begin(); iter != edges_[u].end(); iter++) {
string v = iter->first;
int weight = iter->second;

if (dist.find(v) == dist.end() || dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
prev[v] = u;
pq.push({dist[v], v});
}
}
}

// generate path
vector<pair<string, int>> path;
string cur = destination;
while (cur != source) {
int dis = edges_[cur][prev[cur]];
path.emplace_back(make_pair(cur, dis));
cur = prev[cur];
}
reverse(path.begin(), path.end());

// print
cout << source;
for (auto ele : path) {
cout << "--(" << ele.second << ")-->" << ele.first;
}
cout << endl;
return path;
}
private:
unordered_map<string, unordered_map<string, int>> edges_;
unordered_set<string> vertexs_;
};

/*

int main() {
vector<pair<string, string>> edges = {{"1", "3"}, {"1", "6"}, {"1", "2"},
{"6", "5"}, {"6", "3"}, {"5", "4"}, {"3", "4"}, {"3", "2"}, {"2", "4"}};
vector<int> weights = {9, 14, 7, 9, 2, 6, 11, 10, 15};

Graph g(edges, weights);
auto path = g.FindPath("1", "5");
return 0;
}

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 
# Author: <gfxcc_stevens@outlook.com>
# created: 2017-06-07

cmake_minimum_required(VERSION 2.8.11)

# In-source builds are disabled.
if (${CMAKE_SOURCE_DIR} STREQUAL ${CMAKE_BINARY_DIR})
message(FATAL_ERROR
"CMake generation is not possible within the source directory!"
"\n Remove the CMakeCache.txt file and try again from another folder, e.g.:"
"\n "
"\n rm CMakeCache.txt"
"\n mkdir build"
"\n cd build"
"\n cmake .."
)
endif()


PROJECT(analyze)

MESSAGE(STATUS "Project: ${PROJECT_NAME}")

file(GLOB_RECURSE header ${analyze_SOURCE_DIR}/src/*.h)
file(GLOB_RECURSE source ${analyze_SOURCE_DIR}/src/*.cc)
#list(REMOVE_ITEM source ${iShare_SOURCE_DIR}/MMGAPN/feedback.cpp ${iShare_SOURCE_DIR}/MMGAPN/main.cpp)

SET(CMAKE_BUILD_TYPE "Debug")
SET(CMAKE_CXX_FLAGS "-std=c++11")
SET(CMAKE_CXX_FLAGS_DEBUG "$ENV{CXXFLAGS} -Wall -g -ggdb")
SET(CMAKE_CXX_FLAGS_RELEASE "$ENV{CXXFLAGS} -O3 -Wall")
SET(CMAKE_C_COMPILER /usr/bin/clang)
SET(CMAKE_CXX_COMPILER /usr/bin/clang++)

include_directories(
/usr/include/cppconn/
/usr/local/include/
)

add_executable(analyze ${source})


target_link_libraries(analyze
mysqlcppconn
)