1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
// FILE: graph.h (part of the namespace main_savitch_15)
// TEMPLATE CLASS PROVIDED: graph<Item> (a class for labeled graphs)
// The vertices of an n-vertex graph are numbered from zero to n-1. Each vertex
// has a label of type Item. It may be any of the C++ built-in types (int,
// char, etc.), or any class with a default constructor and an assignment
// operator. The graph may not have multiple edges.
//
// MEMBER CONSTANTS for the graph<Item> template class:
// static const size_t MAXIMUM = ______
// graph::MAXIMUM is the maximum number of vertices that a graph can have.
//
// CONSTRUCTOR for the graph<Item> template class:
// graph( )
// Postcondition: The graph has been initialized with no vertices and no edges.
//
// MODIFICATION MEMBER FUNCTIONS for the graph<Item> template class:
// void add_vertex(const Item& label)
// Precondition: size( ) < MAXIMUM.
// Postcondition: The size of the graph has been increased by adding one new
// vertex. This new vertex has the specified label and no edges.
//
// void add_edge(size_t source, size_t target)
// Precondition: (source < size( )) and (target < size( )).
// Postcondition: The graph has all the edges that it originally had, and it
// also has another edge from the specified source to the specified target.
// (If this edge was already present, then the graph is unchanged.)
//
// void remove_edge(size_t soure, size_t target)
// Precondition: (source < size( )) and (target < size( )).
// Postcondition: The graph has all the edges that it originally had except
// for the edge from the specified source to the specified target. (If this
// edge was not originally present, then the graph is unchanged.)
//
// Item& operator [ ] (size_t vertex)
// Precondition: vertex < size( ).
// Postcondition: The return value is a reference to the label of the
// specified vertex.
//
// CONSTANT MEMBER FUNCTIONS for the graph<Item> template class:
// size_t size( ) const
// Postcondition: The return value is the number of vertices in the graph.
//
// bool is_edge(size_t source, size_t target) const
// Precondition: (source < size( )) and (target < size( )).
// Postcondition: The return value is true if the graph has an edge from
// source to target. Otherwise the return value is false.
//
// set<size_t> neighbors(size_t vertex) const
// Precondition: (vertex < size( )).
// Postcondition: The return value is a set that contains all the vertex
// numbers of vertices that are the target of an edge whose source is at
// the specified vertex.
//
// Item operator [ ] (size_t vertex) const
// Precondition: vertex < size( ).
// Postcondition: The return value is a reference to the label of the
// specified vertex.
// NOTE: This function differs from the other operator [ ] because its
// return value is simply a copy of the Item (rather than a reference of
// type Item&). Since this function returns only a copy of the Item, it is
// a const member function.
//
// VALUE SEMANTICS for the graph<Item> template class:
// Assignments and the copy constructor may be used with graph<Item> objects.
#ifndef MAIN_SAVITCH_GRAPH_H
#define MAIN_SAVITCH_GRAPH_H
#include <cstdlib> // Provides size_t
#include <set> // Provides set
namespace main_savitch_15
{
template <class Item>
class graph
{
public:
// MEMBER CONSTANTS
static const std::size_t MAXIMUM = 20;
// CONSTRUCTOR
graph( ) { many_vertices = 0; }
// MODIFICATION MEMBER FUNCTIONS
void add_vertex(const Item& label);
void add_edge(std::size_t source, std::size_t target);
void remove_edge(std::size_t source, std::size_t target);
Item& operator [ ] (std::size_t vertex);
// CONSTANT MEMBER FUNCTIONS
std::size_t size( ) const { return many_vertices; }
bool is_edge(std::size_t source, std::size_t target) const;
std::set<std::size_t> neighbors(std::size_t vertex) const;
Item operator[ ] (std::size_t vertex) const;
private:
bool edges[MAXIMUM][MAXIMUM];
Item labels[MAXIMUM];
std::size_t many_vertices;
};
}
#include "graph.template" // Include the implementation.
#endif
|