Bellman Ford algorithm implementation

Question

Please review my code and help me to improve it.

#include <iostream>
#include <vector>
#include <limits>
#include <map>
class Graph
{
 int vertex_count;
 enum { INF = std::numeric_limits<int>::max() };
 struct Vertex
 {
 int id;
 int distance;
 Vertex * parent;
 Vertex(int _id) : id(std::move(_id)),
 distance(INF),
 parent(nullptr)
 {}
 };
 std::vector<Vertex> vertices;
 //std::pair<int, int> edge;
 std::map<std::pair<int, int>, int> edge_weight;
 public:
 Graph(int);
 void add_edge(int, int, int); //source, destination, weight
 bool bellman_ford(int); //source
 void distance_from_source();
 private:
 void initialize_single_source(int); //source
 void relax(int, int, int); //source, destination, weight
};
Graph::Graph(int v)
{
 vertex_count = v;
 for (int i = 0; i < vertex_count; i++)
 {
 vertices.push_back(Vertex(i));
 }
}
void Graph::initialize_single_source(int src)
{
 vertices[src].distance = 0;
}
void Graph::add_edge(int src, int dest, int weight)
{
 edge_weight.insert(std::make_pair( std::make_pair(src, dest), weight ));
}
void Graph::relax(int src, int dest, int weight)
{
 auto wt = edge_weight.find(std::make_pair(src, dest));
 if (vertices[dest].distance > (vertices[src].distance + wt->second))
 {
 vertices[dest].distance = (vertices[src].distance + wt->second);
 vertices[dest].parent = &vertices[src];
 }
}
bool Graph::bellman_ford(int src)
{
 initialize_single_source(src);
 for (int i = 0; i < vertex_count - 1; i++)
 {
 for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
 {
 relax(it->first.first, it->first.second, it->second);
 }
 }
 for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
 {
 if (vertices[it->first.second].distance > (vertices[it->first.first].distance + it->second))
 return false;
 }
 return true;
}
void Graph::distance_from_source()
{
 std::cout << "Vertex\t\tDistance from Source\n";
 for (int i = 0; i < vertex_count; i++)
 {
 std::cout << vertices[i].id <<"\t\t" << vertices[i].distance <<"\n";
 }
}
int main()
{
 Graph grp(5);
 grp.add_edge(0, 1, 6);
 grp.add_edge(0, 2, 7);
 grp.add_edge(1, 3, 5);
 grp.add_edge(1, 4, -4);
 grp.add_edge(1, 2, 8);
 grp.add_edge(2, 3, -3);
 grp.add_edge(2, 4, 9);
 grp.add_edge(3, 1, -2);
 grp.add_edge(4, 0, 2);
 grp.add_edge(4, 3, 7);
 bool res = grp.bellman_ford(0);
 if (res == true)
 std::cout << "Graph contains no negative cycle \n";
 else
 std::cout << "Graph conatins negative cycle \n";
 grp.distance_from_source();
}

Answer 1

Vertex class

The INF constant is used only as the initializer for Vertex::distance, so I'd inline the value directly, like this:

struct Vertex
{
 const int id;
 int distance = std::numeric_limits<int>::max();
 Vertex *parent = nullptr;
 Vertex(int id)
 : id(id)
 {}
};

I've inlined the initializers that don't depend on arguments, and I've removed the std::move cast that has no benefit for a primitive type. Since that constructor is now the same as default, we can omit it.

Graph class

The vertex_count member can (and should) be declared const; that also requires it to be initialized (not assigned) in the constructor. That said, there's no need for it, as we can always use vertices.size().

The constructor argument isn't obvious from the class definition - name it and if necessary also add a comment.

Naming: distance_from_source() sounds like it can be used to obtain the results, but it actually prints to standard output. I'd rename it to something like (using #include <iosfwd>):

std::ostream& print_distances(std::ostream&) const;

Constructor

We should tell the vector its final size, so it can reserve capacity and avoid multiple allocations.

We can use emplace_back() to simplify the population of the vector:

Graph::Graph(int v)
 : vertex_count(v)
{
 vertices.reserve(vertex_count);
 for (int i = 0; i < vertex_count; ++i) {
 vertices.emplace_back(i);
 }
}

Adding edges

The add_edge method doesn't check that src and dest are within range, and it does nothing if an edge already exists. We can easily detect these conditions:

void Graph::add_edge(int src, int dest, int weight)
{
 if (src == dest) {
 throw std::logic_error("src==dest");
 }
 if (src < 0 || vertex_count <= src) {
 throw std::out_of_range("src");
 }
 if (dest < 0 || vertex_count <= dest) {
 throw std::out_of_range("dest");
 }
 auto const inserted = edge_weight.insert({ {src, dest}, weight });
 if (!inserted.second) {
 throw std::logic_error("existing edge");
 }
}

I recommend changing the index type from int to an unsigned type (e.g. std::size_t) as negative values are not valid.

Also, the use of std::pair rather than a specific structure makes it hard to follow code full of first and second all meaning different things.

Relaxing weights

It's inefficient to have to re-find() an edge. However, we're passing weight to avoid that, so just re-use it:

void Graph::relax(int src, int dest, int weight)
{
 auto & existing = vertices[dest].distance;
 auto const proposed = vertices[src].distance + weight;
 if (proposed < existing) {
 existing = proposed;
 }
}

I've dropped the update to parent since we never use it.

Bellman-Ford computation

If we want to recalculate with a different origin node, we'll need to reset initial distances to maximum, as well as setting the origin to zero.

---

Modified program

#include <iosfwd>
#include <vector>
#include <map>
class Graph
{
 using index_type = std::size_t;
 using distance_type = int;
 static const distance_type max_distance;
 struct Vertex
 {
 const index_type id;
 distance_type distance = max_distance;
 };
 struct Edge
 {
 index_type from;
 index_type to;
 bool operator<(const Edge& other) const
 {
 return std::tie(from, to) < std::tie(other.from, other.to);
 }
 };
 std::vector<Vertex> vertices = {};
 std::map<Edge,distance_type> edge_weight = {};
public:
 Graph(index_type size);
 void add_edge(index_type from, index_type to, distance_type weight);
 bool bellman_ford(index_type origin); // true if no negative cycles
 std::ostream& print_distances(std::ostream&) const;
private:
 void relax(index_type from, index_type to, distance_type weight);
};

// Implementation
#include <limits>
#include <ostream>
const Graph::distance_type Graph::max_distance
 = std::numeric_limits<distance_type>::max();
Graph::Graph(index_type size)
{
 vertices.reserve(size);
 for (index_type i = 0; i < size; ++i) {
 vertices.push_back(Vertex{i});
 }
}
void Graph::add_edge(index_type src, index_type dest, distance_type weight)
{
 if (src == dest) {
 throw std::logic_error("src==dest");
 }
 if (vertices.size() <= src) {
 throw std::out_of_range("src");
 }
 if (vertices.size() <= dest) {
 throw std::out_of_range("dest");
 }
 auto const inserted = edge_weight.insert({ Edge{src, dest}, weight });
 if (!inserted.second) {
 throw std::logic_error("existing edge");
 }
}
void Graph::relax(index_type src, index_type dest, distance_type weight)
{
 auto& existing = vertices[dest].distance;
 auto const proposed = vertices[src].distance + weight;
 if (proposed < existing) {
 existing = proposed;
 }
}
bool Graph::bellman_ford(index_type src)
{
 // initialise distances
 for (auto& vertex: vertices) {
 vertex.distance = max_distance;
 }
 vertices[src].distance = 0;
 // relax edges
 for (index_type i = 1; i < vertices.size(); ++i) {
 for (auto edge: edge_weight) {
 relax(edge.first.from, edge.first.to, edge.second);
 }
 }
 // check for negative-weight cycles
 for (auto edge: edge_weight) {
 auto const& from_vertex = vertices[edge.first.from];
 auto const& to_vertex = vertices[edge.first.to];
 if (to_vertex.distance > from_vertex.distance + edge.second) {
 return false;
 }
 }
 // success!
 return true;
}
std::ostream& Graph::print_distances(std::ostream& os) const
{
 os << "Vertex\t\tDistance from Source\n";
 for (auto vertex: vertices) {
 os << vertex.id << "\t\t" << vertex.distance << "\n";
 }
 return os;
}

// Test program
#include <iostream>
int main()
{
 Graph grp(5);
 grp.add_edge(0, 1, 6);
 grp.add_edge(0, 2, 7);
 grp.add_edge(1, 3, 5);
 grp.add_edge(1, 4, -4);
 grp.add_edge(1, 2, 8);
 grp.add_edge(2, 3, -3);
 grp.add_edge(2, 4, 9);
 grp.add_edge(3, 1, -2);
 grp.add_edge(4, 0, 2);
 grp.add_edge(4, 3, 7);
 if (grp.bellman_ford(0))
 std::cout << "Graph contains no negative cycle \n";
 else
 std::cout << "Graph conatins negative cycle \n";
 grp.print_distances(std::cout);
}

• JNS: I'm all for useful type aliases, but is replacing int with one really necessary and/or wise in this case? And the standard library uses size_t already for indices, so why do we need to rename it index_type?
• Toby Speight: Perhaps not so useful for index_type, where std::size_t could certainly be used throughout, but the distance_type could save a lot of pain if you later want to use long or double instead of int.
• coder: @TobySpeight Why we have overloaded operator < in struct Edge {...} ?
• Toby Speight: You need an operator< for anything you want to use as a key in std::map. BTW, it's not overloaded at all; just defined.

Answer 2

By not using using namespace std you're already ahead of the curve, well done.

• Why is part of your class outside of your private/public scope? In this case it will be private by default so you should move it to avoid confusion.

• Use compiler warnings. You have an unused parameter (weight) in your relax function. Turning on -Weffc++ will bring up another valid point. You're using a member initializer list for your Vertex struct so why not use it for your Graph class as well?

• Why are you omitting parameter names and then adding them as comments? Just add parameter names to your class interface and get rid of the comments instead.

• Why do you have a single line function (initialize_single_source) that is called only once?

• I don't know which compiler/standard you're using but if possible you should consider using some of the new features (scoped enums, smart pointers, range based for loops).

• Toby Speight: std::move() implies at least C++11, where all those features are available. (The move is unnecessary and unhelpful for a plain int, but it's there)
• yuri: @TobySpeight good catch, all the more reason to ask why they are not utilized.
• coder: @TobySpeight how do I know when to use std::move ?
• Toby Speight: Good question. It wasn't doing any harm where it was, other than adding clutter, which slows understanding. A good rule is to use it when your initializer needs a copy of an object that manages some sort of resource (e.g. a smart pointer, or a collection).