# 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 1 and Listing 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 that when we print our Vertex using the `cout <<`

function
we get a list of its connections, instead of an error. This function must be initialized
as a `friend function`

within the class definition, but is required to be defined outside of the class. This is specific to `operator overloading`

in C++.

**Listing 1**

```
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 Figure 4 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 2**

```
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 NULL
Vertex *vpntr = &vertList[n];
return vpntr;
} else {
return NULL;
}
}
}
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 2. 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 2.