4
\$\begingroup\$

I have written this code for bellman-ford algorithm. Please review and suggest improvements: This code takes input graph as an adjacency matrix, and stores it the same way with additional info as a graph object. It then finds the shortest path to all vertices from the vertex at location [0][0] in the adjacency matrix. I still haven't been able to figure out an efficient way to detect negative weight cycle and am open for suggestions.

struct Node {
    long id;
    Node() { }
    explicit Node(long node_id) : id(node_id) { }
    bool operator==(const Node& node) {
        return this->id == node.id;
    }
};

class Graph {
    struct Edge {
        Node start;
        Node end;
        long length;
        explicit Edge(Node n1, Node n2, long len = 0) : start(n1), end(n2), length(len) { }
        bool operator==(const Edge& node) {
            return ((this->start.id == node.start.id) && (this->end.id == node.end.id));
        }
    };
    std::vector<std::vector<int>> matrix;
    std::list<Node> node_list;
    std::list<Edge> edge_list;
    unsigned long count;

    void createGraph() {
        std::cout << "Enter the number of Nodes: ";
        std::cin >> count;
        for (int i = 0; i < count; i++) {
            std::vector<int> v;
            node_list.push_back(Node(i + 1));
            for (int j = 0; j < count; j++) {
                long temp;
                std::cin >> temp;
                v.push_back(temp);
            }
            matrix.push_back(v);
        }
    }
    void createGraph(const int** adj_matrix) {
        for (unsigned long long i = 0; i < *(&adj_matrix + 1) - adj_matrix; i++) {
            std::vector<int> vec;
            node_list.push_back(Node(i + 1));
            for (unsigned long long j = 0; j < *(&adj_matrix + 1) - adj_matrix; j++) {
                int temp = 0;
                std::cin >> temp;
                vec.push_back(temp);
            }
            matrix.push_back(vec);
        }
    }
    void createGraph(const std::vector<std::vector<int>>& graph) {
        int i = 0;
        for (const auto& node : graph) {
            node_list.push_back(Node(i + 1));
            i++;
            std::vector<int> vec;
            for (const auto& neighbour : node) {
                vec.push_back(neighbour);
            }
            matrix.push_back(vec);
        }
    }
    void addEdges() {
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j]) {
                    Node start(i + 1);
                    Node end(j + 1);
                    edge_list.push_back(Edge(start, end, matrix[i][j]));
                }
            }
        }
    }

public:
    Graph() {
        createGraph();
        addEdges();
    }
    explicit Graph(const int** adj_mat) {
        createGraph(adj_mat);
        count = matrix.size();
        addEdges();
    }
    explicit Graph(const std::vector<std::vector<int>>& graph) {
        createGraph(graph);
        count = matrix.size();
        addEdges();
    }
    inline std::list<Node> getNodes() {
        return node_list;
    }
    long edgeLength(const Node& node1, const Node& node2) {
        for (const auto& edge : edge_list) {
            if (edge.start.id == node1.id && edge.end.id == node2.id) {
                return edge.length;
            }
        }
        return 0;
    }
    bool edgeExists(const Node& node1, const Node& node2) {
        if (std::find(edge_list.begin(), edge_list.end(), Edge(node1, node2)) == edge_list.end()) {
            return false;
        }
        return true;
    }
    void printGraph() {
        for (const auto& row : matrix) {
            for (const auto& elem : row) {
                std::cout << elem << " ";
            }
            std::cout << "\n";
        }
    }
};

std::vector<std::pair<Node, long>> bellman_ford(Graph gr) {
    std::list<Node> v_list = gr.getNodes();
    std::vector<long> node_distance(v_list.size());
    std::fill(node_distance.begin() + 1, node_distance.end(), std::numeric_limits<long>::max());
    for (int i = 0; i < v_list.size() - 1; i++) {
        for (auto& u : v_list) {
            for (auto& v : v_list) {
                if (gr.edgeExists(u, v)) {
                    if (node_distance[v.id - 1] == std::numeric_limits<long>::max()) {
                        node_distance[v.id - 1] = node_distance[u.id - 1] + gr.edgeLength(u, v);
                    }
                    else if (node_distance[v.id - 1] > node_distance[u.id - 1] + gr.edgeLength(u, v)) {
                        node_distance[v.id - 1] = node_distance[u.id - 1] + gr.edgeLength(u, v);
                    }
                }
            }
        }
    }
    std::vector<std::pair<Node, long>> shortest_distance(v_list.size());
    auto list_it = v_list.begin();
    auto dist_it = node_distance.begin();
    for (auto& pair : shortest_distance) {
        pair.first.id = list_it->id;
        pair.second = *dist_it;
        std::advance(list_it, 1);
        std::advance(dist_it, 1);
    }
    return shortest_distance;
}
\$\endgroup\$
3
\$\begingroup\$

Node struct

  1. Node attribute id is public so it can be changed after node has been created. Is it a supported scenario? id should be private attribute.
  2. Operator overload for == should be const. Equality check can't change object state.

Graph class

  1. Node lifetime management: More than one copy of same node is in memory. Graph is keeping list of node and then edge is keeping separate copy as start and end node. One possibility is let Graph manage node lifetime and edges can work with reference/pointers. There are other models possible to avoid multiple copies of nodes in memory.

  2. Start and end of edge are public members. Either make them private or if you want to support case where edge can change endpoint post creation, provide start/end node setters and update adjacency accordingly. Cleaner solution will to make edge immutable with respect to end nodes.

  3. Edge == operator should be marked const

  4. Graph construction: There can be two approaches for graph construction. First, incremental mode. Create an empty graph and the go through sequence of addnode and addedge (In many cases only addedge might be sufficient) to reach desired adjacency. Second, bulk mode. Nodes and edges are read from some structured stream desired adjacency is created. In this case graph constructor (or actually loader, because it is loading existing graph from stream into memory) should take structured stream as input. Doing cin/out based I/O in construction is not good design.

  5. get_nodes is returning copy of list of nodes. It will be memory heavy operation. Any graph algorithm or traversal will call get_nodes multiple times, every time creating copy of all nodes s not good idea. get_nodes should get const reference of node list managed by graph. get_nodes should be marked const.

  6. edgeExist is iterating over all edges and trying to match start/end node. Better way will be iterate over source node adjacency and check for edge. Give edge also an id to make edge lookup faster. Edge lookup map will be handy as adjacency queries are very common in graph algorithms. One possibility is to keep edge id in adjacency structure(something like >)

  7. const auto& in loops in BellmanFord for loops for nodes

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks a lot for one of the most detailed and to the point answers 👏. Will you please elaborate more on what other models you had in mind with reference to point #3 \$\endgroup\$ – cpplover Apr 18 at 12:59
0
\$\begingroup\$

Const operators

bool operator==(const Node& node) {

should be

bool operator==(const Node& node) const {

Likewise for long edgeLength(const Node& node1, const Node& node2), edgeExists, printGraph, etc.

Construction

This function:

void createGraph() {
    std::cout << "Enter the number of Nodes: ";
    std::cin >> count;
    for (int i = 0; i < count; i++) {
        std::vector<int> v;
        node_list.push_back(Node(i + 1));
        for (int j = 0; j < count; j++) {
            long temp;
            std::cin >> temp;
            v.push_back(temp);
        }
        matrix.push_back(v);
    }
}

is mostly code that belongs in a constructor. The constructor in this case would accept an istream& and would not cout; that could be done by the caller. The advantage of this approach is that

  1. it is more flexible - you could deserialize from a file, for example;
  2. it is more decoupled.

I realize that createGraph is a private which is called by the existing constructor, which is fine; but I would stop short of baking in cout/cin.

Pointer madness

This:

*(&adj_matrix + 1)

will not do what you want. Have you tried executing this method? Based on the link you gave me, it seems you were attempting to do a hack that requires that you have a reference to an array with defined size, but you do not - you only have bare pointers.

Just pass in integral matrix dimensions.

Boolean expressions

    if (std::find(edge_list.begin(), edge_list.end(), Edge(node1, node2)) == edge_list.end()) {
        return false;
    }
    return true;

can be

    return std::find(edge_list.begin(), edge_list.end(), Edge(node1, node2)) != edge_list.end();
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. Please take a look at geeksforgeeks.org/… \$\endgroup\$ – cpplover Apr 14 at 15:56
  • \$\begingroup\$ adding const after paranthesis? Is that different from adding one behind paranthesis? I have never seen this syntax. How is it used? \$\endgroup\$ – cpplover Apr 14 at 15:58
  • \$\begingroup\$ Re. the pointer-hack sizing - that only works if you have a reference to the sized array, which you do not. You have a pointer which - in your method's scope - has no idea how big that array is. \$\endgroup\$ – Reinderien Apr 14 at 15:59
  • \$\begingroup\$ By sized array, did you mean std::array? \$\endgroup\$ – cpplover Apr 14 at 16:01
  • \$\begingroup\$ Whatever you're passing to the Graph() constructor. \$\endgroup\$ – Reinderien Apr 14 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.