Example of Test Driven Development with C++ and Google Test
To develop a software based on “Test Driven Development” one should follow the following steps:
1 2 3 4 |
1)Write enough failing Test Code (include compile time and run time failures) 2)Write Production code to pass the failing tests. 3)Refactor the production code and verify the same with existing test. 4)Go to step 1 |
so let say we want to develop a binary search tree, here I’m using Google Test. Step 1, Write enough failing Test Code so the first step would be something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class testingTree: public ::testing::Test { protected: testingTree(){} ~testingTree(){} void SetUp(){} void TearDown(){} }; TEST_F(testingTree,makeTree) { std::shared_ptr<Tree> tree=makeTree(); EXPECT_NE(tree.get(),nullptr); } int main(int argc, char ** argv) { testing::InitGoogleTest(&argc, argv); return RUN_ALL_TESTS(); } |
Step 2, Write Production code to …
Example of Test Driven Development with C++ and Google Test Read More »
Dijkstra’s algorithm with C++
Dijkstra’s algorithm is an algorithm for finding the shortest path in a graph. First drawing the graph:
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 |
import networkx as nx import matplotlib.pyplot as plt from networkx.drawing.nx_agraph import write_dot, graphviz_layout def coloring_tree(G): visited_list=[] for i in G.nodes(): visited_list.append( g.nodes[i]['visited'] ) graph_color_map=[] for i in visited_list: graph_color_map.append('red') pos =graphviz_layout(G, prog='dot') labels = nx.get_edge_attributes(G,'weight') nx.draw(G,pos,with_labels=True, arrows=True, node_color = graph_color_map) nx.draw_networkx_edge_labels(G, pos,edge_labels=labels) plt.show() return g=nx.DiGraph() g.add_node('a',visited=False) g.add_node('b',visited=False) g.add_node('c',visited=False) g.add_node('d',visited=False) g.add_node('e',visited=False) g.add_node('f',visited=False) g.add_node('g',visited=False) g.add_node('h',visited=False) g.add_node('i',visited=False) g.add_edge('a','b',weight=4) g.add_edge('a','h',weight=8) g.add_edge('b','a',weight=4) g.add_edge('b','c',weight=8) g.add_edge('b','h',weight=11) g.add_edge('c','b',weight=8) g.add_edge('c','d',weight=7) g.add_edge('c','f',weight=4) g.add_edge('c','i',weight=2) g.add_edge('d','d',weight=7) g.add_edge('d','e',weight=9) g.add_edge('d','f',weight=14) g.add_edge('e','d',weight=9) g.add_edge('e','f',weight=10) g.add_edge('f','c',weight=4) g.add_edge('f','d',weight=14) g.add_edge('f','e',weight=10) g.add_edge('f','g',weight=2) g.add_edge('g','f',weight=2) g.add_edge('g','h',weight=1) g.add_edge('g','i',weight=6) g.add_edge('h','a',weight=8) g.add_edge('g','b',weight=11) g.add_edge('h','g',weight=1) g.add_edge('h','i',weight=7) g.add_edge('i','c',weight=2) g.add_edge('i','g',weight=6) g.add_edge('i','h',weight=7) coloring_tree(g) |
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include <iostream> #include <vector> #include <string> #include <list> #include <limits> // for numeric_limits #include <set> #include <utility> // for pair #include <algorithm> #include <iterator> typedef int vertex_t; typedef double weight_t; const weight_t max_weight = std::numeric_limits<double>::infinity(); struct neighbor { vertex_t target; weight_t weight; neighbor(vertex_t arg_target, weight_t arg_weight) : target(arg_target), weight(arg_weight) { } }; typedef std::vector<std::vector<neighbor> > adjacency_list_t; void DijkstraComputePaths(vertex_t source, const adjacency_list_t &adjacency_list, std::vector<weight_t> &min_distance, std::vector<vertex_t> &previous) { int n = adjacency_list.size(); min_distance.clear(); min_distance.resize(n, max_weight); min_distance[source] = 0; previous.clear(); previous.resize(n, -1); std::set<std::pair<weight_t, vertex_t> > vertex_queue; vertex_queue.insert(std::make_pair(min_distance[source], source)); while (!vertex_queue.empty()) { weight_t dist = vertex_queue.begin()->first; vertex_t u = vertex_queue.begin()->second; vertex_queue.erase(vertex_queue.begin()); // Visit each edge exiting u const std::vector<neighbor> &neighbors = adjacency_list[u]; for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin(); neighbor_iter != neighbors.end(); neighbor_iter++) { vertex_t v = neighbor_iter->target; weight_t weight = neighbor_iter->weight; weight_t distance_through_u = dist + weight; if (distance_through_u < min_distance[v]) { vertex_queue.erase(std::make_pair(min_distance[v], v)); min_distance[v] = distance_through_u; previous[v] = u; vertex_queue.insert(std::make_pair(min_distance[v], v)); } } } } std::list<vertex_t> DijkstraGetShortestPathTo( vertex_t vertex, const std::vector<vertex_t> &previous) { std::list<vertex_t> path; for ( ; vertex != -1; vertex = previous[vertex]) path.push_front(vertex); return path; } int main() { adjacency_list_t adjacency_list(9); adjacency_list[0].push_back(neighbor(1, 4)); adjacency_list[0].push_back(neighbor(7, 8)); adjacency_list[1].push_back(neighbor(0, 4)); adjacency_list[1].push_back(neighbor(2, 8)); adjacency_list[1].push_back(neighbor(7, 11)); adjacency_list[2].push_back(neighbor(1, 8)); adjacency_list[2].push_back(neighbor(3, 7)); adjacency_list[2].push_back(neighbor(5, 4)); adjacency_list[2].push_back(neighbor(8, 2)); adjacency_list[3].push_back(neighbor(3, 7)); adjacency_list[3].push_back(neighbor(4, 9)); adjacency_list[3].push_back(neighbor(5, 14)); adjacency_list[4].push_back(neighbor(3, 9)); adjacency_list[4].push_back(neighbor(5, 10)); adjacency_list[5].push_back(neighbor(2, 4)); adjacency_list[5].push_back(neighbor(3, 14)); adjacency_list[5].push_back(neighbor(4, 10)); adjacency_list[5].push_back(neighbor(6, 2)); adjacency_list[6].push_back(neighbor(5, 2)); adjacency_list[6].push_back(neighbor(7, 1)); adjacency_list[6].push_back(neighbor(8, 6)); adjacency_list[7].push_back(neighbor(0, 9)); adjacency_list[7].push_back(neighbor(1, 9)); adjacency_list[7].push_back(neighbor(6, 9)); adjacency_list[7].push_back(neighbor(8, 9)); adjacency_list[8].push_back(neighbor(2, 2)); adjacency_list[8].push_back(neighbor(6, 6)); adjacency_list[8].push_back(neighbor(7, 7)); std::vector<weight_t> min_distance; std::vector<vertex_t> previous; DijkstraComputePaths(0, adjacency_list, min_distance, previous); std::cout << "Distance from 0 to 5: " << min_distance[5] << std::endl; std::list<vertex_t> path = DijkstraGetShortestPathTo(5, previous); std::cout << "Path : "; std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " ")); std::cout << std::endl; return 0; } |
1 2 |
Distance from 0 to 5: 16 Path : 0 1 2 5 |
ref [1]