How to represent a graph in c++

Question

I would like to write prims and dijkstra algoritms that create a MST. But I do not know what is the best way to represent graph in c++.

I could represent an edge by pair of two ints for example vector 0 to 1 would be pair(0,1);

typedef pair<int, int> Edge;

And then the prims function would take Vector of pairs that consist of an edge and its weight.

void prims(vector<pair<Edge, int>>);

I think that this way is not the best one, could anyone tell me what way would be the best to represent a graph?

Answer 1

I have been implementing Dijkstra some time ago for finding paths in binary images. I represented a graph as a vector of a struct GraphNodes that contained a vector of Connections that contained all the connections of the node to other nodes. Each connection has its distance attribute, which is the weight of the edge. Here are the two structs I used:

//forward declaration
struct GraphNode;
struct Connection {
    Connection() : distance(1) { };
    Connection(GraphNode* ptr, double distance) : ptr(ptr), distance(distance) { };
    bool operator==(const Connection &other) const;
    GraphNode* ptr;
    double distance;
};

struct GraphNode {
    GraphNode() : connections(8), predecessor(NULL), distance(-1) { };
    cv::Point point;
    double distance;
    GraphNode* predecessor;
    std::vector<Connection> connections;
};

bool Connection::operator==(const Connection &other) const {
    return ptr == other.ptr && distance == other.distance;
}

The distance attribute of the GraphNode is the distance it currently has in the Dijkstra algorithm, so the distance of the shortest currently known distance to the start node. At the beginning this is initialized with -1.

I then implemented the Dijkstra algorithm like this:

std::vector<cv::Point> findShortestPathDijkstra(std::vector<GraphNode>& graph, int startNodeIndex, int destNodeIndex) const {
    GraphDistanceSorter sorter(graph);
    std::set<GraphNode*, GraphDistanceSorter> unusedNodes(sorter);
    for (int i = 0; i < graph.size(); ++i) {
        unusedNodes.insert(&graph[i]);
    }

    while (unusedNodes.size() > 0) {

        GraphNode* currentNode = *unusedNodes.begin();
        if (currentNode->distance == -1) {
            return std::vector<cv::Point>();
        }
        if (currentNode == &graph[destNodeIndex]) break;
        unusedNodes.erase(currentNode);
        //update distances of connected nodes
        for (Connection const& con : currentNode->connections) {
            /*here we could check if the element is really in unusedNodes (search, O(log n)), but this would
            actually take longer than calculating the new distance (O(1)), which will in this case always be greater
            than the old one, so the distance is never updated for nodes not in unusedNodes ()*/
            double newDistance = currentNode->distance + con.distance;
            if (newDistance < con.ptr->distance || con.ptr->distance == -1) {
                unusedNodes.erase(con.ptr);
                con.ptr->distance = newDistance;
                con.ptr->predecessor = currentNode;
                unusedNodes.insert(con.ptr);
            }
        }
    }

    //now trace back the path as a list of points
    std::vector<cv::Point> points;
    GraphNode* current = &graph[destNodeIndex];
    points.push_back(current->point);
    while (current != &graph[startNodeIndex]) {
        if (current->predecessor == NULL) return std::vector<cv::Point>();
        current = current->predecessor;
        points.push_back(current->point);
    }

    return points;

}

As you see there is a set unusedNodes that contains all the unused nodes so far. It only contains pointers on graphNodes. The actual graph representation is in the vector. The advantage of having a set is, that it is always sorted according to a certain criterion. I implemented my own sorter GraphDistanceSorter that sorts the GraphNodes according to the distance criterion of the Dijkstra algorithm. This way I just have to pick the first node from the set and know that it's the one with the smallest distance:

struct GraphDistanceSorter {
    bool operator() (const GraphNode* lhs, const GraphNode* rhs) const;
};

bool GraphDistanceSorter::operator() (const GraphNode* lhs, const GraphNode* rhs) const {
    if (lhs->distance == rhs->distance) {
        return lhs < rhs;
    } else {
        if (lhs->distance != -1 && rhs->distance != -1) {
            if (lhs->distance != rhs->distance) {
                return lhs->distance < rhs->distance;
            }
        } else if (lhs->distance != -1 && rhs->distance == -1) {
            return true;
        }
        return false;
    }
}

Answer 2

The two main ways to represent graphs learned in theoretical computer-science are adjacency matrix and adjacency lists.

Adjacency Matrix is as shown in the photo below is an n*n matrix and a[i][j] represents the edge between node i and node j so if it's a weighted graph it can be an integer instead of a boolean value for unweighted graphs.

adjacency matrix (photo source: google)

On the other hand, adjacency lists is a set of linked-lists (n-set to be exact), the i-th set has exactly the nodes i is connected to. in this case you will need some additional way to save edge distance for example you can build your own class Edge as following

class Edge
{
     int destination, length;
     Edge* next = 0;
}

and use it for your linked-list. How ever I am used to std::vector<std::pair<int, int>> a[N] to define a list of pairs and a[i][j].first would be the j-th neighbor of nod i and a[i][j].second the length of the edge between them. For undirected graph your can add i to j neighbors as well. So it's also a flexible way to represent graphs.

adjacency lists (image source: google photos)

So now let's talk complexity, I will try to keep it as simple as possible:

We habe n lists, each has the #(edges going out of node i) so the total number is sum of this numbers which is the total number of edges E. That means place complexity is O(E) which is at most 5 * n in a sparse-graph in comparison to O(N^2) in adjacency matrix. (We need a linear factor of E to represent it). Now let's consider visiting all neighbors of a nod x: in adjacency matrix we will go through the whole x-th line and if it's not 0 there's an edge there which is O(N). In adjacency lists it's again exactly the number of neighbors of x which can though reach O(N). But if we are visiting all neighbors of all Nodes (which is the case in Dijkstra when updating dis array), you will need to visit n elements n times in adjacency lists which is also O(N^2) time complexity while in adjacency lists it's exactly the sum of the number of neighbors - again E. which means we need also O(E) to visit all neighbors of all edges. And sind all edges are given usually in the input O(E) would pass as calculation time, but O(N^2) would be a high complexity for constraints of N <= 10^6 for example. At the end I will leave you with my usual implementation of diffreent variants of graphs using adjacency lists (vector as a list):

#include<iostream>
#include<vector>
int main(){
    const int N = 5;
    int n, e;
    std::vector<std::pair<int, int>> graph[N], inverse[N];
    std::vector<int> unweighted[N], undirectedUnweighted[N];
    std::cin >> n >> e;
    for(int i = 0; i < e; i++)
    {
        int x, y, z;//z is length of edge
        std::cin >> x >> y >> z;
        //substitute 1 from x, y if they starts from 1
        graph[x].push_back(std::make_pair(y, z));
        inverse[y].push_back(std::make_pair(x, z));
        unweighted[x].push_back(y);
        undirectedUnweighted[x].push_back(y);
        undirectedUnweighted[y].push_back(x);
    }
    return 0;
}

Answer 3

Simple form for representing graph (finding neighbors and degrees for vertices)

#include<iostream>

/** Representing graphs in c++ programming language */

using namespace std;

int main() {

    cout << "\033[1;33mNote: if there are no neighbourhood between vertices write '-' symbol!\033[0m\n"<<endl;

    int number_of_vertices;
    cout<<"\033[1;32mPlease enter number of vertices: \033[0m";
    cin>>number_of_vertices;

    int max_num_of_neighbours;
    cout<<"\033[1;32mPlease enter maximum number of neighbours: \033[0m";
    cin>>max_num_of_neighbours;

    char array[number_of_vertices][max_num_of_neighbours];

    char vertices[number_of_vertices];

    cout<<"\033[1;33mPlease sign vertices with lowercase alphabet letters: \033[0m"<<endl;

    for(int i = 0; i < number_of_vertices; i ++) {

        cout<<(i+1)<<" = ";
        cin>>vertices[i];

    }

    for(int i = 0; i < number_of_vertices; cout<<endl, i ++) {

        cout<<"\033[1;32mPlease enter neighbours for \033[0m"<<vertices[i]<<" --> ";

        for(int j = 0; j < max_num_of_neighbours; j ++) {

            cin>>array[i][j];

        }

    }


    for(int i = 0; i < number_of_vertices; cout<<endl, i ++) {

        cout<<"\033[1;34mNeighbours for \033[0m"<<"\033[1;35m"<<vertices[i]<<"\033[0m"<<" --> ";

        int deg = 0;

        for(int j = 0; j < max_num_of_neighbours; j ++) {

            if(array[i][j] != '-') {
                deg ++;
            }

            if(array[i][j] == '-') {
                cout<<"\033[1;31m"<<array[i][j]<<"\033[0m"<<"\t";
            } else {
                cout<<"\033[1;32m"<<array[i][j]<<"\033[0m"<<"\t";
            }

        }

        cout<<"\033[1;36m"<<"deg["<<"\033[0m"<<"\033[1;35m"<<vertices[i]<<"\033[0m"<<"\033[1;36m"<<"] = "<<"\033[0m"<<deg;

    }

    cout<<endl<<"\033[1;33mRemember that '\033[1;31m-\033[0m\033[1;33m' shows when two vertices aren't adjacent!\033[0m"<<endl;


}

For adding interactivity I used How do I output coloured text to a Linux terminal? for changing color of text