class GraphInterface
1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: /** An interface for the ADT undirected, connected graph.
5: Listing 20-1.
6: @file GraphInterface.h */
8: #ifndef _GRAPH_INTERFACE
9: #define _GRAPH_INTERFACE
11: template<class LabelType>
12: class GraphInterface
13: {
14: public:
15: /** Gets the number of vertices in this graph.
16: @pre None.
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: @pre None.
22: @return The number of edges in the graph. */
23: virtual int getNumEdges() const = 0;
24:
25: /** Creates an undirected edge in this graph between two vertices
26: that have the given labels. If such vertices do not exist, creates
27: them and adds them to the graph before creating the edge.
28: @param start A label for the first vertex.
29: @param end A label for the second vertex.
30: @param edgeWeight The integer weight of the edge.
31: @return True if the edge is created, or false otherwise. */
32: virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0;
33:
34: /** Removes an edge from this graph. If a vertex has no other edges,
35: it is removed from the graph since this is a connected graph.
36: @pre None.
37: @param start A label for the first vertex.
38: @param end A label for the second vertex.
39: @return True if the edge is removed, or false otherwise. */
40: virtual bool remove(LabelType start, LabelType end) = 0;
41:
42: /** Gets the weight of an edge in this graph.
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 first 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 first 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: }; // end GraphInterface
61: #endif