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