admin, Author at Robotics with ROS

Example of Test Driven Development with C++ and Google Test

Leave a Comment / C++, Tutorials / By admin

To develop a software based on “Test Driven Development” one should follow the following steps:

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

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:

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();
}

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++

1 Comment / C++ / By admin

Dijkstra’s algorithm is an algorithm for finding the shortest path in a graph. First drawing the graph:

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)

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)

#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;
}

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;

}

Distance from 0 to 5: 16
Path : 0 1 2 5

1 2	Distance from 0 to 5: 16 Path : 0 1 2 5

ref [1]

Cookie	Duration	Description
cookielawinfo-checbox-analytics	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checbox-functional	11 months	The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checbox-others	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-necessary	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-performance	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy	11 months	The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.

admin

Gauss-Newton algorithm for solving non-linear non-linear explained

Newton’s method Explained

3D Point to 3D Point Pose Estimation Explained

Perspective N Points (PnP) Explained

Understanding the Mathematics behind Gradient Descent

Motion Model for Robots Explained

Bézier Curve Equation Explained

Kinematic Equation for Differential Drive Explained

Example of Test Driven Development with C++ and Google Test

Dijkstra’s algorithm with C++