Skip to main content

Section 9.6 Implementation

Using a map, or dictionaries in Python, it is easy to implement the adjacency list. In our implementation of the Graph abstract data type we will create two classes (see Listing 9.6.1 and Listing 9.6.2), Graph, which holds the master list of vertices, and Vertex, which will represent each vertex in the graph.
Each Vertex uses a map to keep track of the vertices to which it is connected, and the weight of each edge. This map is called connectedTo. The listing below shows the code for the Vertex class. The constructor simply initializes the id, which will be an integer, and the connectedTo map. The addNeighbor method is used add a connection from this vertex to another. The getConnections method returns all of the vertices in the adjacency list, as represented by the connectedTo instance variable. The getWeight method returns the weight of the edge from this vertex to the vertex passed as a parameter.
We use operator overloading so we can print our Vertex using the cout << function.
The operator << function uses operator-overloading syntax rather than a regular function syntax. Of course, the & after ostream means the function returns a reference to the output stream. Returning the stream by reference allows chaining, such as cout << vertex << endl, because each call returns the same stream for the next output operation. The operator << token is the overloaded operator name, so this function defines how << behaves when used to output a Vertex object.
This overload is usually written as a non-member function so that the left operand can be ostream. It may be declared as a friend of Vertex when direct access to private data is needed. The parameters are passed by reference to avoid unnecessary copying, and the object parameter is typically const (for example, const Vertex& vert) to indicate that output should not modify the object.
Listing 9.6.1. Vertex Class
class Vertex {
    public:
        int id;
        map<int, int> connectedTo;

        Vertex() {
        }

        Vertex(int key) {
            id = key;
        }

        void addNeighbor(int nbr, int weight = 0) {
            connectedTo[nbr] = weight;
        }

        vector<int> getConnections() {
            vector<int> keys;
            // Use of iterator to find all keys
            for (map<int, int>::iterator it = connectedTo.begin();
                it != connectedTo.end();
                ++it) {
                keys.push_back(it->first);
            }
            return keys;
        }

        int getId() {
            return id;
        }

        int getWeight(int nbr) {
            return connectedTo[nbr];
        }

        friend ostream &operator<<(ostream &, Vertex &);
};

ostream &operator<<(ostream &stream, Vertex &vert) {
    vector<int> connects = vert.getConnections();
    for (unsigned int i = 0; i < connects.size(); i++) {
        stream << "( " << vert.id << " , " << connects[i] << " ) \n";
    }

    return stream;
}
The Graph class, shown in the next listing, contains a map that maps vertex names (int) to vertex objects (Vertex). In Section 9.5 this map object is represented by the shaded gray box. Graph also provides methods for adding vertices to a graph and connecting one vertex to another. The getVertices method returns the names of all of the vertices in the graph.
Listing 9.6.2. Graph Class
class Graph {
    public:
        map<int, Vertex> vertList;
        int numVertices;

        Graph() {
            numVertices = 0;
        }

        Vertex addVertex(int key) {
            numVertices++;
            Vertex newVertex = Vertex(key);
            this->vertList[key] = newVertex;
            return newVertex;
        }

        Vertex *getVertex(int n) {
            for (map<int, Vertex>::iterator it = vertList.begin(); it != vertList.end(); ++it) {
                if (it->first == n) {
                    // Forced to use pntr due to possibility of returning nullptr
                    Vertex *vpntr = &vertList[n];
                    return vpntr;
                } else {
                    return nullptr;
                }
            }
        }

        bool contains(int n) {
            for (map<int, Vertex>::iterator it = vertList.begin(); it != vertList.end(); ++it) {
                if (it->first == n) {
                    return true;
                }
            }
            return false;
        }

        void addEdge(int f, int t, int cost = 0) {
            if (!this->contains(f)) {
                cout << f << " was not found, adding!" << endl;
                this->addVertex(f);
            }
            if (!this->contains(t)) {
                cout << t << " was not found, adding!" << endl;
            }
            vertList[f].addNeighbor(t, cost);
        }

        vector<int> getVertices() {
            vector<int> verts;

            for (map<int, Vertex>::iterator it = vertList.begin(); it != vertList.end();  ++it) {
                verts.push_back(it->first);
            }
            return verts;
        }

        friend ostream &operator<<(ostream &, Graph &);
};

ostream &operator<<(ostream &stream, Graph &grph) {
    for (unsigned int i = 0; i < grph.vertList.size(); i++) {
        stream << grph.vertList[i];
    }

    return stream;
}
Using the Graph and Vertex classes just defined, the following Python session creates the graph in Figure 9.2.1. First we create six vertices numbered 0 through 5. Then we display the vertex dictionary. Notice that for each key 0 through 5 we have created an instance of a Vertex. Next, we add the edges that connect the vertices together. Finally, a nested loop verifies that each edge in the graph is properly stored. You should check the output of the edge list at the end of this session against Figure 9.2.1.

Exploration 9.6.1. Directed Graph Implementation.

(a) C++ Implementation.

(b) Python Implementation.

You have attempted of activities on this page.
PrevTopNext