Find center of an undirected graph

Question

Task: implement an algorithm to find graph center \$Z(G)\$ given undirected tree \$G\$.

This is my first time programming in C++ so any (elementary) feedback is appreciated.

The way I did it is:

1. Run BFS from any node \$v_0\$ in \$G\$. Find node \$v_1\$ with \$\max_{v_1\in V(G)} \text{dist} (v_0,v_1)\$.
2. Run BFS from \$v_1\$. Find node \$v_2\$ with \$\max_{v_2\in V(G)} \text{dist} (v_1,v_2)\$.
3. Given tree \$G\$ its center consists of either one or two nodes in the middle of the \$v_1v_2\$ path. Run BFS from both ends of the path and terminate as soon as BFS is halfway through. Save all nodes in the middle of the graph in two vectors \$A,B\$ and take their intersection \$A\cap B\$. Done.

My implementation:

helloworld.cpp

#include <algorithm>
#include <iostream>
#include <chrono>
#include <ctime>   
#include <set>
#include "graph.h"


Graph bfs(Graph g, int nodeId) {
    Graph path(0, Graph::undirected);

    return path;
};

int main(int argc, char* argv[]) {
    int v_0 = 0;
    if (argc > 1) {
        // initialize graph
        Graph g(argv[1], Graph::undirected);
        // start clock
        auto start = std::chrono::system_clock::now();
        // start BFS in random node and find v_1 such that d(v_0, v_1) is maximal
        std::pair<int,int> v_1 = g.farthestNode(v_0);
        // start BFS in v_1 and find v_2 such that d(v_1, v_2) is maximal
        std::pair<int,int> v_2 = g.farthestNode(v_1.first);
        // find nodes in the middle between v_1 and v_2
        std::vector<int> cand1 = g.middleNodes(v_1.first, v_2.first, v_2.second);
        std::vector<int> cand2 = g.middleNodes(v_2.first, v_1.first, v_2.second);
        // find intersection of cand1, cand2
        // sort both cand1 and cand2    
        std::sort(cand1.begin(), cand1.end());
        std::sort(cand2.begin(), cand2.end());
        // intersect cand 1 and cand2
        std::vector<int> cand3(cand1.size()+cand2.size());
        std::vector<int>::iterator it, st;
        it = set_intersection(cand1.begin(), cand1.end(), cand2.begin(), cand2.end(), cand3.begin());
        cand3.resize(distance(cand3.begin(), it));
        // remove duplicates
        std::vector<int>::iterator mt;
        mt = unique(cand3.begin(), cand3.end());
        cand3.resize(distance(cand3.begin(), mt));
        // stop clock
        auto end = std::chrono::system_clock::now();
        std::chrono::duration<double> elapsed_seconds = end-start;
        std::cout << "Elapsed time: " << elapsed_seconds.count() << "s\n";
        std::cout << "Center of a graph G is: \n";
        for (auto i : cand3) 
            std::cout << i << " ";
    } else {
        std::cout << "No instance given.";
    }
}

graph.cpp

#include "graph.h"
#include <bits/stdc++.h>

#include <fstream>  // fstream provides streams for reading/writing files
#include <limits>
#include <sstream>  // sstream provides conversion between strings and streams
#include <stdexcept>

const Graph::NodeId Graph::invalid_node = -1;
const double Graph::infinite_weight = std::numeric_limits<double>::max();

void Graph::add_nodes(NodeId num_new_nodes) {
    // The resize adds num_new_nodes.
    // A std::vector has two sizes: visible size and allocated size s.t. allocaded size >= visible
    // size If the allocated size needs to be extended it is extended by a constant factor, e.g.
    // doubled. Thereby n additions of single nodes takes O(n log n) time in total and possible
    // twice the minimum required space.
    _nodes.resize(num_nodes() + num_new_nodes);
}

Graph::Neighbor::Neighbor(Graph::NodeId n, double w) : _id(n), _edge_weight(w) {}

Graph::Graph(NodeId num, DirType dtype) : dirtype(dtype), _nodes(num) {}

void Graph::add_edge(NodeId tail, NodeId head, double weight) {
    if (tail >= num_nodes() or tail < 0 or head >= num_nodes() or head < 0) {
        throw std::runtime_error("Edge cannot be added due to undefined endpoint.");
    }
    // for digraphs we store only successors for undirected graphs we store all neighbors.
    _nodes[tail].add_neighbor(head, weight);
    if (dirtype == Graph::undirected) {
        _nodes[head].add_neighbor(tail, weight);
    }
}

void Graph::Node::add_neighbor(Graph::NodeId nodeid, double weight) {
    _neighbors.push_back(Graph::Neighbor(nodeid, weight));
}

/** the first const refers to the reference to the vector, which thereby cannot be modified by the
 * caller. The second const refers to the current object, which must not be modified by this method.
 * It is required if the member function is called from a const reference to the current object,
 * i.e. if we a variable such as const Graph::Node& node;
 */
const std::vector<Graph::Neighbor>& Graph::Node::adjacent_nodes() const { return _neighbors; }

Graph::NodeId Graph::num_nodes() const { return _nodes.size(); }

const Graph::Node& Graph::get_node(NodeId node) const {
    if (node < 0 or node >= static_cast<int>(_nodes.size())) {
        throw std::runtime_error("Invalid nodeid in Graph::get_node.");
    }
    return _nodes[node];
}

Graph::NodeId Graph::Neighbor::id() const { return _id; }

double Graph::Neighbor::edge_weight() const { return _edge_weight; }

void Graph::print() const {
    if (dirtype == Graph::directed) {
        std::cout << "Digraph ";
    } else {
        std::cout << "Undirected graph ";
    }
    std::cout << "with " << num_nodes() << " vertices, numbered 0,...," << num_nodes() - 1 << ".\n";

    /** The type "auto" automatically substitutes to the type defined
        by the type or return-type of the function right of the '=', here int.
     */
    for (auto nodeid = 0; nodeid < num_nodes(); ++nodeid) {
        std::cout << "The following edges are ";
        if (dirtype == Graph::directed) {
            std::cout << "leaving";
        } else {
            std::cout << "incident to";
        }
        std::cout << " vertex " << nodeid << ":\n";

        /** Here auto resolves to a vector iterator of 'const std::vector<Neighbor> &'
         *  The ':' stands for iterating through the elements of the vector from start to end.
         *  The following line is equivalent to (but much shorter and better readable than):
         *  for (auto neighbor = _nodes[nodeid].adjacent_nodes().begin(); neighor !=
         * _nodes[nodeid].adjacent_nodes().end(); neighbor++) {
         */
        for (auto neighbor : _nodes[nodeid].adjacent_nodes()) {
            std::cout << nodeid << " - " << neighbor.id() << " weight = " << neighbor.edge_weight()
                      << "\n";
        }
    }
}

Graph::Graph(char const* filename, DirType dtype) : dirtype(dtype) {
    std::ifstream file(filename);  // open file
    // file is implicitly a pointer to an underlying file object, if it's creation failed it will be
    // '0' (= NULL).
    if (not file) {
        throw std::runtime_error("Cannot open file.");
    }

    Graph::NodeId num = 0;
    std::string line;
    std::getline(file, line);    // get first line of file
    std::stringstream ss(line);  // convert line to a stringstream
    ss >> num;                   // for which we can use >>
    if (not ss) {
        throw std::runtime_error("Invalid file format.");
    }
    add_nodes(num);
    //  read the lines until there is no more line.
    while (std::getline(file, line)) {
        std::stringstream ss(line);
        Graph::NodeId head, tail;
        ss >> tail >> head;
        /** The operator! (not operator) of std::stringstream
            returns true if an error had occured.
         */
        if (not ss) {
            throw std::runtime_error("Invalid file format.");
        }
        double weight = 1.0;
        ss >> weight;
        if (tail != head) {
            add_edge(tail, head, weight);
        } else {
            throw std::runtime_error("Invalid file format: loops not allowed.");
        }
    }
}

Graph Graph::max_simple_graph() const {
    // Check if graph is undirected
    if (dirtype == Graph::directed) {
        throw std::runtime_error("Wrong graph type.");
    }

    Graph maxSimpleGraph(num_nodes(), undirected);
    double minEdgeWeight;
    Graph::Node currentNode;
    std::vector<Neighbor> neighbors;

    // loop over all nodes
    for (auto nodeId = 0; nodeId < num_nodes(); nodeId++) {
        std::vector<NodeId> uniqueIds(1, -1);
        currentNode = get_node(nodeId);
        neighbors = currentNode.adjacent_nodes();
        std::cout << "Node ID: " << nodeId << "\n";

        // loop over all neighbors of a node
        for (auto neighbor : currentNode.adjacent_nodes()) {
            // guard variable
            bool u = 0;
            std::cout << "Neighbor ID: " << neighbor.id() << "\n";

            // loop over all neighbors (second loop) and find min weight
            for (auto neighbor2 : neighbors) {
                if (neighbor2.id() == neighbor.id()) {
                    minEdgeWeight = std::min(neighbor2.edge_weight(), neighbor.edge_weight());
                }
            }

            // check if such neighbor already exists
            for (auto id : uniqueIds) {
                std::cout << "Check: " << id << " " << neighbor.id() << "\n";
                u = (id == neighbor.id()) ? 1 : 0;
                std::cout << u << "\n";
            }

            // if no such neighbor exists, create one
            if (!u) {
                std::cout << "Neighbor " << neighbor.id() << " added \n";
                maxSimpleGraph._nodes[nodeId].add_neighbor(neighbor.id(), minEdgeWeight);
                uniqueIds.push_back(neighbor.id());
            }
            std::cout << "u = " << u << "\n";
            std::cout << "Minimum weight: " << minEdgeWeight << "\n";
        }
    }
    return maxSimpleGraph;
}

std::pair<int,int> Graph::farthestNode(int NodeId) {
    // initialize all distances with -1
    std::vector<int> dist(num_nodes(), -1);
    std::fill(std::begin(dist),std::end(dist), -1);
    // create queue and push first node into it
    std::queue<int> q;
    q.push(NodeId);
    // set initial distance to first node as 0
    dist[NodeId] = 0;

    while (!q.empty()) {
        int currentNodeId = q.front();
        // std::cout << "Current node ID: " << currentNodeId << "\n";
        q.pop();
        Graph::Node currentNode = get_node(currentNodeId);
        // loop through all neighbors
        for (auto neighbor : currentNode.adjacent_nodes()) {
            // std::cout << "Neighbor of " << currentNodeId << " is " << neighbor.id() << "\n";
            // if the neighbor wasn't yet visited 
            if (dist[neighbor.id()] == -1) {
                // add to queue + add distance from the root
                q.push(neighbor.id());
                dist[neighbor.id()] = dist[currentNodeId] + 1;
            }
        }
    }

    // find maximum distance
    int maxDist = 0;
    int NodeId2;
    for (int i = 0; i < num_nodes(); i++) {
        if (dist[i] > maxDist) {
            maxDist = dist[i];
            NodeId2 = i;
        }
    }
    std::cout << "Farthest node is " << NodeId2 << " with distance of " << maxDist << "\n\n\n";
    return std::make_pair(NodeId2, maxDist);
}

std::vector<int> Graph::middleNodes(int start, int end, int maxDist) {
    // input: start node, end node, distance between them
    // (1) divides max distance by 2 
    // (2) runs BFS halfway through 
    // (3) returns all nodes that are (max distance / 2) away from Node ID
    // output: vector<int> Candidates

    // (1) dind max distance divided by 2
    // input: integer n
    // output: (k,k) if n=2k, (k,k+1) if n=2k+1  
    std::cout << "Start searching for nodes in the middle between " << start << " and " << end << "\n";
    std::pair<int,int> maxDistDivBy2;
    if (ceilf(maxDist / 2.0)==(maxDist / 2.0)) {
        maxDistDivBy2 = std::make_pair(ceilf(maxDist / 2.0), ceilf(maxDist / 2.0));
    } else {
        maxDistDivBy2 = std::make_pair(ceilf(maxDist / 2.0), floorf(maxDist / 2.0));
    }
    std::cout << "Max distance " << maxDist << " divided by 2: " << maxDistDivBy2.first << ", " << maxDistDivBy2.second << "\n";
    
    // (2) run BFS
    // initialize vector for candidate nodes
    std::vector<int> candidates;
    // initialize all distances with -1
    std::vector<int> dist(num_nodes(), -1);
    std::fill(std::begin(dist),std::end(dist), -1);
    // create queue and push first node into it
    std::queue<int> q;
    q.push(start);
    // set initial distance to first node as 0
    dist[start] = 0;
    // start greedy search
    while (!q.empty()) {
        int currentNodeId = q.front();
        // std::cout << "Current node ID: " << currentNodeId << "\n";
        q.pop();
        Graph::Node currentNode = get_node(currentNodeId);
        // loop through all neighbors
        for (auto neighbor : currentNode.adjacent_nodes()) {
            // std::cout << "Neighbor of " << currentNodeId << " is " << neighbor.id() << "\n";
            // if the neighbor wasn't yet visited 
            if (dist[neighbor.id()] == -1) {
                // add to queue + add distance from the root
                q.push(neighbor.id());
                dist[neighbor.id()] = dist[currentNodeId] + 1;
            } else if (dist[neighbor.id()] == maxDistDivBy2.first || dist[neighbor.id()] == maxDistDivBy2.second) {
                candidates.push_back(neighbor.id());
                // std::cout << "Found node " << neighbor.id() << "!\n";
            } else if (dist[neighbor.id()] > maxDistDivBy2.first && dist[neighbor.id()] > maxDistDivBy2.second) {
                break;
            }
        }
    }
    /*for (auto i: candidates) {
        std::cout << i << ' ';
    }
    std::cout << "\n";*/

    return candidates;
}```

Answer 1

Don't use <bits/stdc++.h>

The header file <bits/stdc++.h> is not part of the C++ standard, and there is no guarantee it exists, or if it does that it will exist in the future. Never use this header file, instead just #include the standard header files you need.

Missing error handling

If an error happens while reading from a file, the while-loop in Graph::Graph() will exit, but that's not distinguishable from reaching the end of the file. So to check that you did succesfully read the whole file, check that file.eof() == true, and if that is not the case, throw an error.

Create a function for finding the center

Just like you have other functions that operate on a graph, like farthestNode(), it would be nice to create a function that given a graph, returns the center node(s). This will clean up your main() function.

Optimize finding the middle nodes

When you are performing a BFS from a given starting point, you can keep track of the "parent" node of each node you visit, i.e. the node from which direction you came. When you then find the farthest node, of which you should know the distance, you can simply walk back along the chain of parent nodes until you are halfway. So consider creating a farthestNodeChain() that returns a std::vector<int> containing that chain, and then it's just picking the one or two middle elements from it. That will also greatly simplify your code.

Inconsistent use of Graph::NodeId and Graph::invalid_node

It looks like you created a type or type alias Graph::NodeId, but farthestNode() and middleNodes() use int directly. Make sure you are consistent. Consider what would happen if you decided to change Graph::NodeId.

I also see you created a constant Graph::invalid_node, but you never seem to use it anywhere else.

Unnecessary use of floating points

Your use of floating point numbers in middleNodes() is unnecessary. If you start with integer numbers and have to end up with integer numbers, avoid having floating points in the middle; it's usually unnecessary, it's less efficient, and if you are not aware of all the subtle issues (like the fact that not all integers can be represented correctly by a floating point number of the same size) it's easy to introduce bugs. Consider:

if (maxDist % 2 == 0) {
    maxDistDivBy2 = {maxDist / 2, maxDist / 2};
} else {
    maxDistDivBy2 = {maxDist / 2 + 1, maxDist / 2};
}

You can avoid the if-statement entirely by adding 1 before dividing by 2:

std::pair<int, int> maxDistDivBy2 = {(maxDist + 1) / 2, maxDist / 2};

Use more auto

You already use auto in some cases, but you can reduce a lot of explicit, long type names by using more auto:

auto v_1 = g.farthestNode(v_0);
auto v_2 = g.farthestNode(v_1);
auto cand1 = g.middleNodes(v1.first, v2.first, v2.second);
⋮
auto it = set_intersection(cand1.begin(), cand1.end(), cand2.begin(), cand2.end(), cand3.begin());
⋮
auto mt = std::unique(cand3.begin(), cand3.end());

Use more STL algorithms

The standard library comes with many algorithms that take care of common tasks for you. For example, to find the node with the maximum distance, you can use std::max_element():

auto it = std::max_element(dist.begin(), dist.end());
NodeId farthestNodeId = std::distance(dist.begin(), it);

Double initialization of dist

In both farthestNode() and middleNodes() you construct a vector filled with -1, and then call std::fill() to fill it with -1 again. The calls to std::fill() are unnecessary.

Use of comments

You have added a lot of comments to your code. Since this is your first time programming C++, it's probably a good excercise to describe in normal English what you are trying to accomplish, as this might help your learning process.

That said, if this wasn't just a learning project, then I would say that you have many unnecessary comments. Basically, everything that the average C++ programmer would understand just by looking at the code itself does not need to documented. This includes things like:

// initialize graph
Graph g(argv[1], Graph::undirected);
⋮
// start clock
auto start = std::chrono::system_clock::now();
⋮
#include <fstream>  // fstream provides streams for reading/writing files

There are examples of comments that are helpful though, for example:

// for digraphs we store only successors for undirected graphs we store all neighbors.
⋮
// check if such neighbor already exists
⋮
// if no such neighbor exists, create one

That said, if you have a number of lines of code whose meaning would not be immediately clear for an average programmer, then instead of adding a comment above it, you could instead also put those lines in their own function. With a properly chosen name for the function, the meaning of the code would become much clearer without having to use a comment.

This is also a reason to use algorithms and other functions from the standard library when possible; their names say what they do, and most C++ programmers already have a good knowledge of what the standard functions do.

Lastly, consider using the Doxygen format to document the classes and functions in your code. The doxygen tool can then generate HTML and PDF files containing that documentation in a nicer to read, cross-referenced format, and it can warn if you forgot to document parts of your code.