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.