class GraphInterface
1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 20-1.
6: /** An interface for the ADT undirected, connected graph.
7: @file GraphInterface.h */
9: #ifndef GRAPH_INTERFACE_
10: #define GRAPH_INTERFACE_
12: template<class LabelType>
13: class GraphInterface
14: {
15: public:
16: /** Gets the number of vertices in this graph.
17: @return The number of vertices in the graph. */
18: virtual int getNumVertices() const = 0;
19:
20: /** Gets the number of edges in this graph.
21: @return The number of edges in the graph. */
22: virtual int getNumEdges() const = 0;
23:
24: /** Creates an undirected edge in this graph between two vertices
25: that have the given labels. If such vertices do not exist, creates
26: them and adds them to the graph before creating the edge.
27: @param start A label for the first vertex.
28: @param end A label for the second vertex.
29: @param edgeWeight The integer weight of the edge.
30: @return True if the edge is created, or false otherwise. */
31: virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0;
32:
33: /** Removes an edge from this graph. If a vertex is left with no other edges,
34: it is removed from the graph since this is a connected graph.
35: @param start A label for the vertex at the beginning of the edge.
36: @param end A label for the vertex at the end of the edge.
37: @return True if the edge is removed, or false otherwise. */
38: virtual bool remove(LabelType start, LabelType end) = 0;
39:
40: /** Gets the weight of an edge in this graph.
41: @param start A label for the vertex at the beginning of the edge.
42: @param end A label for the vertex at the end of the edge.
43: @return The weight of the specified edge.
44: If no such edge exists, returns a negative integer. */
45: virtual int getEdgeWeight(LabelType start, LabelType end) const = 0;
46:
47: /** Performs a depth-first search of this graph beginning at the given
48: vertex and calls a given function once for each vertex visited.
49: @param start A label for the beginning vertex.
50: @param visit A client-defined function that performs an operation on
51: or with each visited vertex. */
52: virtual void depthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;
54: /** Performs a breadth-first search of this graph beginning at the given
55: vertex and calls a given function once for each vertex visited.
56: @param start A label for the beginning vertex.
57: @param visit A client-defined function that performs an operation on
58: or with each visited vertex. */
59: virtual void breadthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;
60:
61: /** Destroys this graph and frees its assigned memory. */
62: virtual ~GraphInterface() { }
63: }; // end GraphInterface
64: #endif