1  #ifndef GRAPH_H
  2  #define GRAPH_H
  3  
  4  #include "Edge.h" // Defined in Listing 26.1
  5  #include "Tree.h" // Defined in Listing 26.4
  6  #include <vector>
  7  #include <queue> // For implementing BFS
  8  #include <stdexcept>
  9  #include <sstream> // For converting a number to a string
 10  
 11  using namespace std;
 12  
 13  template<typename V>
 14  class Graph
 15  {
 16  public:
 17    // Construct an empty graph 
 18    Graph();
 19  
 20    // Construct a graph from vertices in a vector and
 21    //  edges in 2-D array 
 22    Graph(vector<V>& vertices, int edges[][2], int numberOfEdges);
 23  
 24    // Construct a graph with vertices 0, 1, ..., n-1 and
 25    // edges in 2-D array 
 26    Graph(int numberOfVertices, int edges[][2], int numberOfEdges);
 27  
 28    // Construct a graph from vertices and edges objects 
 29    Graph(vector<V>& vertices, vector<Edge>& edges);
 30  
 31    // Construct a graph with vertices 0, 1, ..., n-1 and
 32    // edges in a vector 
 33    Graph(int numberOfVertices, vector<Edge>& edges);
 34  
 35    // Return the number of vertices in the graph 
 36    int getSize() const;
 37  
 38    // Return the degree for a specified vertex 
 39    int getDegree(int v) const;
 40  
 41    // Return the vertex for the specified index 
 42    V getVertex(int index) const;
 43  
 44    // Return the index for the specified vertex 
 45    int getIndex(V v) const;
 46  
 47    // Return the vertices in the graph 
 48    vector<V> getVertices() const;
 49  
 50    // Return the neighbors of vertex v 
 51    vector<int> getNeighbors(int v) const;
 52  
 53    // Print the edges 
 54    void printEdges() const;
 55  
 56    // Print the adjacency matrix 
 57    void printAdjacencyMatrix() const;
 58  
 59    // Clear the graph
 60    void clear();
 61  
 62    // Adds a vertex to the graph
 63    virtual bool addVertex(V v);
 64  
 65    // Adds an edge from u to v to the graph
 66    bool addEdge(int u, int v); 
 67  
 68    // Obtain a depth-first search tree 
 69    // To be discussed in Section 24.6 
 70    Tree dfs(int v) const;
 71  
 72    // Starting bfs search from vertex v 
 73    // To be discussed in Section 24.7 
 74    Tree bfs(int v) const;
 75  
 76  protected:
 77    vector<V> vertices; // Store vertices
 78    vector<vector<Edge*>> neighbors; // Adjacency edge lists
 79    bool createEdge(Edge* e); // Add an edge 
 80  
 81  private:
 82    // Create adjacency lists for each vertex from an edge array 
 83    void createAdjacencyLists(int numberOfVertices, int edges[][2],
 84      int numberOfEdges);
 85  
 86    // Create adjacency lists for each vertex from an Edge vector 
 87    void createAdjacencyLists(int numberOfVertices,
 88      vector<Edge>& edges);
 89  
 90    // Recursive function for DFS search 
 91    void dfs(int v, vector<int>& parent,
 92      vector<int>& searchOrders, vector<bool>& isVisited) const;
 93  };
 94  
 95  template<typename V>
 96  Graph<V>::Graph()
 97  {
 98  }
 99  
100  template<typename V>
101  Graph<V>::Graph(vector<V>& vertices, int edges[][2],
102    int numberOfEdges)
103  {
104    for (unsigned i = 0; i < vertices.size(); i++)
105      addVertex(vertices[i]);
106  
107    createAdjacencyLists(vertices.size(), edges, numberOfEdges);
108  }
109  
110  template<typename V>
111  Graph<V>::Graph(int numberOfVertices, int edges[][2],
112    int numberOfEdges)
113  {
114    for (int i = 0; i < numberOfVertices; i++)
115      addVertex(i); // vertices is {0, 1, 2, ..., n-1}
116  
117    createAdjacencyLists(numberOfVertices, edges, numberOfEdges);
118  }
119  
120  template<typename V>
121  Graph<V>::Graph(vector<V>& vertices, vector<Edge>& edges)
122  {
123    for (unsigned i = 0; i < vertices.size(); i++)
124      addVertex(vertices[i]);
125  
126    createAdjacencyLists(vertices.size(), edges);
127  }
128  
129  template<typename V>
130  Graph<V>::Graph(int numberOfVertices, vector<Edge>& edges)
131  {
132    for (int i = 0; i < numberOfVertices; i++)
133      addVertex(i); // vertices is {0, 1, 2, ..., n-1}
134  
135    createAdjacencyLists(numberOfVertices, edges);
136  }
137  
138  template<typename V>
139  void Graph<V>::createAdjacencyLists(int numberOfVertices,
140    int edges[][2],  int numberOfEdges)
141  {
142    for (int i = 0; i < numberOfEdges; i++)
143    {
144      int u = edges[i][0];
145      int v = edges[i][1];
146      addEdge(u, v);
147    }
148  }
149  
150  template<typename V>
151  void Graph<V>::createAdjacencyLists(int numberOfVertices,
152    vector<Edge>& edges)
153  {
154    for (unsigned i = 0; i < edges.size(); i++)
155    {
156      int u = edges[i].u;
157      int v = edges[i].v;
158      addEdge(u, v);
159    }
160  }
161  
162  template<typename V>
163  int Graph<V>::getSize() const
164  {
165    return vertices.size();
166  }
167  
168  template<typename V>
169  int Graph<V>::getDegree(int v) const
170  {
171    return neighbors[v].size();
172  }
173  
174  template<typename V>
175  V Graph<V>::getVertex(int index) const
176  {
177    return vertices[index];
178  }
179  
180  template<typename V>
181  int Graph<V>::getIndex(V v) const
182  {
183    for (unsigned i = 0; i < vertices.size(); i++)
184    {
185      if (vertices[i] == v)
186        return i;
187    }
188  
189    return -1; // If vertex is not in the graph
190  }
191  
192  template<typename V>
193  vector<V> Graph<V>::getVertices() const
194  {
195    return vertices;
196  }
197  
198  template<typename V>
199  vector<int> Graph<V>::getNeighbors(int u) const
200  {
201    vector<int> result;
202    for (Edge* e: neighbors[u])
203      result.push_back(e->v);
204    return result;
205  }
206  
207  template<typename V>
208  void Graph<V>::printEdges() const
209  {
210    for (unsigned u = 0; u < neighbors.size(); u++)
211    {
212      cout << "Vertex " << getVertex(u) << "(" << u << "): ";
213      for (Edge* e: neighbors[u])
214      {
215        cout << "(" << getVertex(e->u) << ", " << getVertex(e->v) << ") ";
216      }
217      cout << endl;
218    }
219  }
220  
221  template<typename V>
222  void Graph<V>::printAdjacencyMatrix() const
223  {
224    // Use vector for 2-D array
225    vector<vector<int>> adjacencyMatrix(getSize());
226  
227    // Initialize 2-D array for adjacency matrix
228    for (int i = 0; i < getSize(); i++)
229    {
230      adjacencyMatrix[i] = vector<int>(getSize());
231    }
232  
233    for (unsigned i = 0; i < neighbors.size(); i++)
234    {
235      for (Edge* e: neighbors[i])
236      {
237        adjacencyMatrix[i][e->v] = 1;
238      }
239    }
240  
241    for (unsigned i = 0; i < adjacencyMatrix.size(); i++)
242    {
243      for (unsigned j = 0; j < adjacencyMatrix[i].size(); j++)
244      {
245        cout << adjacencyMatrix[i][j] << " ";
246      }
247  
248      cout << endl;
249    }
250  }
251  
252  template<typename V>
253  void Graph<V>::clear()
254  {
255    vertices.clear();
256    for (int i = 0; i < getSize(); i++)
257      for (Edge* e: neighbors[i])
258        delete e;
259    neighbors.clear();
260  }
261  
262  template<typename V>
263  bool Graph<V>::addVertex(V v)
264  {
265    if (find(vertices.begin(), vertices.end(), v) == vertices.end()) 
266    {
267      vertices.push_back(v);
268      neighbors.push_back(vector<Edge*>(0));
269      return true; 
270    }
271    else
272    {
273      return false; 
274    }
275  }
276  
277  template<typename V>
278  bool Graph<V>::createEdge(Edge* e)
279  {
280    if (e->u < 0 || e->u > getSize() - 1)
281    {
282      stringstream ss;
283      ss << e->u;
284      throw invalid_argument("No such edge: " + ss.str());
285    }
286  
287    if (e->v < 0 || e->v > getSize() - 1)
288    {
289      stringstream ss;
290      ss << e->v;
291      throw invalid_argument("No such edge: " + ss.str());
292    }
293  
294    vector<int> listOfNeighbors = getNeighbors(e->u);
295    if (find(listOfNeighbors.begin(), listOfNeighbors.end(), e->v) 
296      == listOfNeighbors.end()) 
297    { 
298      neighbors[e->u].push_back(e);
299      return true;
300    }
301    else 
302    {
303      return false; 
304    } 
305  }
306  
307  template<typename V>
308  bool Graph<V>::addEdge(int u, int v)
309  {
310    return createEdge(new Edge(u, v));
311  }
312  
313  template<typename V>
314  Tree Graph<V>::dfs(int u) const
315  {
316    vector<int> searchOrders;
317    vector<int> parent(vertices.size());
318    for (unsigned i = 0; i < vertices.size(); i++)
319      parent[i] = -1; // Initialize parent[i] to -1
320  
321    // Mark visited vertices
322    vector<bool> isVisited(vertices.size());
323    for (unsigned i = 0; i < vertices.size(); i++)
324    {
325      isVisited[i] = false;
326    }
327  
328    // Recursively search
329    dfs(u, parent, searchOrders, isVisited);
330  
331    // Return a search tree
332    return Tree(u, parent, searchOrders);
333  }
334  
335  template<typename V>
336  void Graph<V>::dfs(int u, vector<int>& parent,
337    vector<int>& searchOrders, vector<bool>& isVisited) const
338  {
339    // Store the visited vertex
340    searchOrders.push_back(u);
341    isVisited[u] = true; // Vertex v visited
342  
343    for (Edge* e: neighbors[u])
344    {
345      if (!isVisited[e->v]) 
346      {
347        parent[e->v] = u; // The parent of vertex i is v
348        dfs(e->v, parent, searchOrders, isVisited); // Recursive search
349      }
350    }
351  }
352  
353  template<typename V>
354  Tree Graph<V>::bfs(int v) const
355  {
356    vector<int> searchOrders;
357    vector<int> parent(vertices.size());
358    for (int i = 0; i < getSize(); i++)
359      parent[i] = -1; // Initialize parent[i] to -1
360  
361    queue<int> queue; // Stores vertices to be visited
362    vector<bool> isVisited(getSize());
363    queue.push(v); // Enqueue v
364    isVisited[v] = true; // Mark it visited
365  
366    while (!queue.empty()) 
367    {
368      int u = queue.front(); // Get from the front of the queue
369      queue.pop(); // remove the front element
370      searchOrders.push_back(u); // u searched
371      for (Edge* e: neighbors[u])
372      {
373        int w = e->v;
374        if (!isVisited[w]) 
375        {
376          queue.push(w); // Enqueue w
377          parent[w] = u; // The parent of w is u
378          isVisited[w] = true; // Mark it visited
379        }
380      }
381    }
382  
383    return Tree(v, parent, searchOrders);
384  }
385  
386  #endif