diff options
| author | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
|---|---|---|
| committer | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
| commit | c1b6ffe70bd281c6c230fd63fabcaac2aff47514 (patch) | |
| tree | e8af3b1782a7cd0754590ed618fddc1bdb9b7385 /chapter15/graph.h | |
| download | dscode-main.tar.xz dscode-main.zip | |
Diffstat (limited to 'chapter15/graph.h')
| -rw-r--r-- | chapter15/graph.h | 99 |
1 files changed, 99 insertions, 0 deletions
diff --git a/chapter15/graph.h b/chapter15/graph.h new file mode 100644 index 0000000..7bfb1ac --- /dev/null +++ b/chapter15/graph.h @@ -0,0 +1,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
|