C++ : Adjacency list implementation for storing graph

Storing graph as an adjacency list using a list of the lists in C++

Below is a simple example of a graph where each node has a number that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list can be implemented as a list of lists in C++.

Example : In the below adjacency list we can see
a) Node 0 has a list storing adjacent nodes 1 and 2.
b) Node 1 has a list storing adjacent nodes 0, 3 and 4.


Storing graph using list of lists

C++: Storing graph in an adjacency list. Implemented using list of lists in C++14

#include<iostream>
#include<list>

using namespace std;

class Graph {

    private:

        int nodes;
        list<int> *adjlist;

    public:

        Graph() {
        }

        Graph (int nodes) { // Allocate resources
            adjlist = new list<int> [nodes];
            this->nodes = nodes;
        }

        ~Graph () { // Free allocated resources
            delete [] adjlist;
        }

        void AddEdge (int src, int dst) {
            adjlist[src].push_back(dst);
            adjlist[dst].push_back(src);
        }

        void Iterate (int src) {
            cout <<  src << " : ";
            for (auto& adj_node : adjlist[src]) {
                 cout << adj_node << " ";
            } cout << endl;
        }
};


int main()
{
    Graph g(7);

    g.AddEdge(0,1);
    g.AddEdge(0,2);
    g.AddEdge(1,3);
    g.AddEdge(1,4);
    g.AddEdge(2,3);
    g.AddEdge(3,5);
    g.AddEdge(4,6);
    g.AddEdge(5,6);

    cout << "Adjacency list implementation for graph" << endl;

    g.Iterate(0);
    g.Iterate(1);
    g.Iterate(4);

    return 0;
}

Output

Adjacency list implementation for graph
0 : 1 2
1 : 0 3 4
4 : 1 6

Storing graph as an adjacency list using a map of node and list of nodes in C++


Below is an example of a graph where each node has a name (string) and an id (number) that uniquely identifies it and differentiates it from other nodes in the graph. Such a graph can be stored in an adjacency list where each node has a list of all the adjacent nodes that it is connected to.
An adjacency list for such a graph can be implemented as a map of node and list of nodes in C++.

Example : In the below adjacency list we can see
a) Node ( Alfa, 1 ) has a list storing adjacent nodes ( Cod, 2 ), ( Pi, 3 ) and ( Ram , 4)

Note : Node is defined as a custom class hence we need to overload < (less than) operator so that it works with map other option is to use a compare class that overloads () operator.

Storing graph using map

C++: Storing graph in an adjacency list. Implemented using map of Node and a list of Node(s) in C++11.
        Operator < (less than) is overloaded.

#include<list>
#include<map>

using namespace std;

class Node {

    private:

    string name;
    int id;

    public:

    Node(string arg_name, int arg_id): name(arg_name), id(arg_id) {
    }

    bool operator < (const Node& n) const {
        if (n.name < this->name) {
            return true;
        }
        return false;
    }

    void Display () const {
        cout << "(" << name << " , " << id << ") ";
    }
};

class Graph {

    private:

    map<Node, list<Node>> adjlist;

    public:

    Graph() {
    }

    void Add_Adjacent_Nodes (Node& src, list<Node>& adj_nodes) {
        adjlist.insert( { src, adj_nodes } );
    }

    void Iterate (Node src) {

        src.Display(); cout << " : ";

        for (const auto& node : adjlist[src]) {
             node.Display();
        } cout << endl;
    }
};

int main()
{
    Node n1("Alfa", 1);
    Node n2("Cod", 2);
    Node n3("Pi", 3);
    Node n4("Ram", 4);
    Node n5("Yo", 5);

    list<Node> n1_list = { n2, n3, n4 };
    list<Node> n2_list = { n1, n4 };
    list<Node> n3_list = { n1, n4, n5 };
    list<Node> n4_list = { n1, n2, n3, n5 };
    list<Node> n5_list = { n3, n4 };

    cout << "Adjacency list implementation for graph" << endl;

    Graph g;
    g.Add_Adjacent_Nodes (n1, n1_list);
    g.Add_Adjacent_Nodes (n2, n2_list);
    g.Add_Adjacent_Nodes (n3, n3_list);
    g.Add_Adjacent_Nodes (n4, n4_list);
    g.Add_Adjacent_Nodes (n5, n5_list);

    g.Iterate(n1);
    g.Iterate(n2);
    g.Iterate(n3);
    g.Iterate(n4);

    return 0;
}

Output

Adjacency list implementation for graph
(Alfa , 1)  : (Cod , 2) (Pi , 3) (Ram , 4)
(Cod , 2)  : (Alfa , 1) (Ram , 4)
(Pi , 3)  : (Alfa , 1) (Ram , 4) (Yo , 5)
(Ram , 4)  : (Alfa , 1) (Cod , 2) (Pi , 3) (Yo , 5)

C++: Storing graph in an adjacency list. Implemented using map of Node and a list of Node(s) in C++11.
        Creating a map using a Compare Class with operator () overloaded.

#include<iostream>
#include<list>
#include<map>

using namespace std;

class Node {

    private:

    string name;
    int id;

    public:

    Node(string arg_name, int arg_id): name(arg_name), id(arg_id) {
    }

    void Display () const {
        cout << "(" << name << " , " << id << ") ";
    }

    int GetId() const {
        return id;
    }
};

class Compare {

    public:
    bool operator () (const Node& a, const Node& b) const {
        return (a.GetId() < b.GetId());
    }
};

class Graph {

    private:

    map<Node, list<Node>, Compare> adjlist;

    public:

    Graph() {
    }

    void Add_Adjacent_Nodes (Node& src, list<Node>& adj_nodes) {
        adjlist.insert( { src, adj_nodes } );
    }

    void Iterate (Node src) {

        src.Display(); cout << " : ";

        for (auto& node : adjlist[src]) {
             node.Display();
        } cout << endl;
    }
};

int main()
{
    Node n1("Alfa", 1);
    Node n2("Cod", 2);
    Node n3("Pi", 3);
    Node n4("Ram", 4);
    Node n5("Yo", 5);

    list<Node> n1_list = { n2, n3, n4 };
    list<Node> n2_list = { n1, n4 };
    list<Node> n3_list = { n1, n4, n5 };
    list<Node> n4_list = { n1, n2, n3, n5 };
    list<Node> n5_list = { n3, n4 };

    cout << "Adjacency list implementation for graph" << endl;

    Graph g;
    g.Add_Adjacent_Nodes (n1, n1_list);
    g.Add_Adjacent_Nodes (n2, n2_list);
    g.Add_Adjacent_Nodes (n3, n3_list);
    g.Add_Adjacent_Nodes (n4, n4_list);
    g.Add_Adjacent_Nodes (n5, n5_list);

    g.Iterate(n1);
    g.Iterate(n2);
    g.Iterate(n3);
    g.Iterate(n4);

    return 0;
}

Output

Adjacency list implementation for graph
(Alfa , 1)  : (Cod , 2) (Pi , 3) (Ram , 4) 
(Cod , 2)  : (Alfa , 1) (Ram , 4) 
(Pi , 3)  : (Alfa , 1) (Ram , 4) (Yo , 5) 
(Ram , 4)  : (Alfa , 1) (Cod , 2) (Pi , 3) (Yo , 5) 

Copyright (c) 2019-2020, Algotree.org.
All rights reserved.