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
100
|
// FILE: graph.template (part of the namespace main_savitch_15)
// TEMPLATE CLASS IMPLEMENTED: graph<Item> (See graph.h for documentation.)
// This file is included in the header file and not compiled separately.
// INVARIANT for the graph class:
// 1. The number of vertices in the graph is stored in the member variable
// many_vertices.
// 1. These vertices are numbered from 0 to many_vertices-1.
// 2. edges is the adjacency matrix for the graph (with true in edges[i][j]
// to indicate an edge from vertex i to vertex j).
// 3. For each i < many_vertices, labels[i] is the label of vertex i.
#include <cassert> // Provides assert
#include <cstdlib> // Provides size_t
#include <set> // Provides set
namespace main_savitch_15
{
template <class Item>
const std::size_t graph<Item>::MAXIMUM;
template <class Item>
void graph<Item>::add_edge(std::size_t source, std::size_t target)
// Library facilities used: cassert, cstdlib
{
assert(source < size( ));
assert(target < size( ));
edges[source][target] = true;
}
template <class Item>
void graph<Item>::add_vertex(const Item& label)
// Library facilities used: cassert, cstdlib
{
std::size_t new_vertex_number;
std::size_t other_number;
assert(size( ) < MAXIMUM);
new_vertex_number = many_vertices;
many_vertices++;
for (other_number = 0; other_number < many_vertices; ++other_number)
{
edges[other_number][new_vertex_number] = false;
edges[new_vertex_number][other_number] = false;
}
labels[new_vertex_number] = label;
}
template <class Item>
bool graph<Item>::is_edge(std::size_t source, std::size_t target) const
// Library facilities used: cassert, cstdlib
{
assert(source < size( ));
assert(target < size( ));
return edges[source][target];
}
template <class Item>
Item& graph<Item>::operator[ ] (std::size_t vertex)
// Library facilities used: cassert, cstdlib
{
assert(vertex < size( ));
return labels[vertex]; // Returns a reference to the label
}
template <class Item>
Item graph<Item>::operator[ ] (std::size_t vertex) const
// Library facilities used: cassert, cstdlib
{
assert(vertex < size( ));
return labels[vertex]; // Returns only a copy of the label
}
template <class Item>
std::set<std::size_t> graph<Item>::neighbors(std::size_t vertex) const
// Library facilities used: cassert, cstdlib, set
{
std::set<std::size_t> answer;
std::size_t i;
assert(vertex < size( ));
for (i = 0; i < size( ); ++i)
{
if (edges[vertex][i])
answer.insert(i);
}
return answer;
}
template <class Item>
void graph<Item>::remove_edge(std::size_t source, std::size_t target)
// Library facilities used: cassert, cstdlib
{
assert(source < size( ));
assert(target < size( ));
edges[source][target] = false;
}
}
|