Question

A graph consists of nodes and edges. An edge is an (unordered) pair of two distinct nodes in the graph. We create a new empty graph from the class Graph. We use the add_node method to add a single node and the add_nodes method to add multiple nodes. Nodes are identified by unique symbols. We call add_edge with two nodes to add an edge between a pair of nodes belonging to the graph. We can also ask a graph for the number of nodes and edges it contains, and for a list of its nodes and edges. The to_s method returns a string representing the graph's adjacency lists. Methods should not change the graph if called with invalid arguments; e.g., adding an edge that is already in the graph or that references a node that does not already belong to the graph. Your code does not have to generate the exact transcript that follows but it should provide this basic functionality.

>> g = Graph.new
=> <Graph: 0, 0>
>> g.add_node(:a)
=> a

>> g.add_nodes([:b, :c]) => [:b, :c]
>> g
=> <Graph: 3, 0>

>> g.get_nodes
=> [:a, :b, :c]
>> g.nbr_nodes
=> 3

>> g.add_edge(:a, :b) => [a, b]
>> g.add_edge(:b, :c) => [b, c]

>> g
=> <Graph: 3, 2>
>> g.get_edges
=> [[a, b], [b, c]]

>> g.nbr_edges
=> 2
>> puts g
a -> b

b -> a,c
c -> b
=> nil

Answer 1

//C++ implementation for the problem

#include<iostream>
#include<map>
#include<vector>
#include<set>
using namespace std;

class Graph{                                            //Assuming a directed graph
private:
        map<char,vector<char>> edges;       //A map to maintain the edges
        set<char> nodes;                          //A set to maintain nodes, avoiding duplicacy
        int edge_count;                                 //variable to keep track of number of edges
public:
        void add_node(char node) {
                nodes.insert(node);                     //Inserting node to set
        }
        void add_nodes(vector<char> vNodes) {
                for(char node: vNodes)
                        nodes.insert(node);
        }
        bool add_edge(char u, char v) {
                //Checking if both the entered nodes are valid and exists in the set of nodes
                if(nodes.find(u)==nodes.end() || nodes.find(v)==nodes.end())
                        return false;
                edges[u].push_back(v);
                edge_count++;
                return true;
        }
        int nbr_nodes() {
                return (int)nodes.size();
        }
        int nbr_edges() {
                return edge_count;
        }
        string get_nodes() {
                string stringOfNodes;
                for(char node: nodes)
                {
                        stringOfNodes.push_back(node);  //Generating string representation of the set of nodes 
                        stringOfNodes += ",";
                }
                stringOfNodes.pop_back();               //Popping the extra , appened at the end
                return stringOfNodes;
        }
        string get_edges() {
                string stringOfEdges;
                for(auto it: edges) {                   //Iterating through each entry of edges map [Key]
                        for(auto adj: it.second) {      //Iterating through the vector associated with each entry of the map [Value]
                                stringOfEdges += "[";
                                stringOfEdges.push_back(it.first);
                                stringOfEdges += ",";
                                stringOfEdges.push_back(adj);
                                stringOfEdges += "],";
                        }
                }
                stringOfEdges.pop_back();
                return stringOfEdges;
        }
        string to_s() {
                //Generating a string representation of the adjacency lists
                string adjacencyString;
                for(auto it: edges) {
                        adjacencyString.push_back(it.first);
                        adjacencyString += " -> ";
                        for(auto adj: it.second) {
                                adjacencyString.push_back(adj);
                                adjacencyString += ",";
                        }
                        adjacencyString.pop_back();
                        adjacencyString += "\n";
                }
                return adjacencyString;
        }
};

//Code for testing
int main() {
        Graph g = Graph();
        g.add_node('a');
        g.add_nodes({'b','c'});
        cout<<g.get_nodes()<<"\n";
        cout<<g.nbr_nodes()<<"\n";
        g.add_edge('a','b');
        g.add_edge('b','c');
        cout<<g.get_edges()<<"\n";
        cout<<g.nbr_edges()<<"\n";
        cout<<g.to_s();
}