From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001
From: Fuwn <contact@fuwn.me>
Date: Sun, 7 Apr 2024 23:18:32 -0700
Subject: feat: initial commit

---
 chapter15/graph.h | 99 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 99 insertions(+)
 create mode 100644 chapter15/graph.h

(limited to 'chapter15/graph.h')

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
-- 
cgit v1.2.3