feat: initial commitHEADmain

4 files changed, 340 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

diff --git a/chapter15/graph.template b/chapter15/graph.template
new file mode 100644
index 0000000..781568a
--- /dev/null
+++ b/chapter15/graph.template
@@ -0,0 +1,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;

+    }

+}

+	

+    

diff --git a/chapter15/searches.h b/chapter15/searches.h
new file mode 100644
index 0000000..1570a1f
--- /dev/null
+++ b/chapter15/searches.h
@@ -0,0 +1,48 @@
+// FILE: searches.h (part of namespace main_savitch_15)
+// This file provides three template functions for searching graphs
+// from the graph template class of graph.h
+//
+// template <class Process, class Item, class SizeType>
+// void rec_dfs(Process f, graph<Item>& g, SizeType v, bool marked[])
+//   Precondition: g is a labeled graph that is being traversed by a
+//   depth-first search. For each vertex x, marked[x] is true if x has
+//   already been visited by this search, otherwise marked[x] is false.
+//   The vertex v is an unmakred vertex that the search has just arrived at.
+//   Postcondition: the depth-first search of g has been continued
+//   through vertex v and beyond to all the vertices that can be reached
+//   from v via a path of unmarked vertices.  The function f has been
+//   applied to the labe of each vertex visited by the search, and each
+//   such vertex x has also been marked by setting marked[x] to true.
+//
+// template <class Process, class Item, class SizeType>
+// void depth_first(Process f, graph<Item>& g, SizeType start)
+//   Precondion: start is a vertex number of the labeled graph g.
+//   Postcondition: A depth-first search of g has been executed,
+//   starting at the start vertex.  The function f has been applied to the
+//   label of each vertex visited by the search.
+//
+// template <class Process, class Item, class SizeType>
+// void breadth_first(Process f, graph<Item>& g, SizeType start)
+//   Precondition: start is a vertex number of the labeled graph g.
+//   Postcondition: A breadth-first search of g has been executed,
+//   starting at the start vertex. The function f has been applied to the
+//   label of each vertex visited by the search.
+
+#ifndef SEARCHES_H
+#define SEARCHES_H
+#include "graph.h"
+
+namespace main_savitch_15
+{
+    template <class Process, class Item, class SizeType>
+    void rec_dfs(Process f, graph<Item>& g, SizeType v, bool marked[]);
+ 
+    template <class Process, class Item, class SizeType>
+    void depth_first(Process f, graph<Item>& g, SizeType start);
+
+    template <class Process, class Item, class SizeType>
+    void breadth_first(Process f, graph<Item>& g, SizeType start);
+}
+
+#include "searches.template" // Include the implementation.
+#endif
diff --git a/chapter15/searches.template b/chapter15/searches.template
new file mode 100644
index 0000000..536ba27
--- /dev/null
+++ b/chapter15/searches.template
@@ -0,0 +1,93 @@
+// FILE: searches.template
+// TEMPLATE FUNCTIONS IMPLEMENTED: rec_dfs, depth_first, and breadth_first.
+// Please see searches.h for documentation of these functions.
+// This file is included at the bottom of searches.h, and should not be
+// separately compiled.
+
+#include <algorithm>
+#include <cassert>
+#include <cstdlib>
+#include <queue>
+#include <set>
+#include "graph.h"
+
+namespace main_savitch_15
+{
+    template <class Process, class Item, class SizeType>
+    void rec_dfs(Process f, graph<Item>& g, SizeType v, bool marked[])
+    // Precondition: g is a labeled graph that is being traversed by a
+    // depth-first search. For each vertex x, marked[x] is true if x has
+    // already been visited by this search, otherwise marked[x] is false.
+    // The vertex v is an unmakred vertex that the search has just arrived at.
+    // Postcondition: the depth-first search of g has been continued
+    // through vertex v and beyond to all the vertices that can be reached
+    // from v via a path of unmarked vertices.  The function f has been
+    // applied to the labe of each vertex visited by the search, and each
+    // such vertex x has also been marked by setting marked[x] to true.
+    // Library facilities used: cstdlib, graph.h, set
+    {
+	std::set<std::size_t> connections = g.neighbors(v);
+	std::set<std::size_t>::iterator it;
+   
+	marked[v] = true;  // Mark vertex v
+	f(g[v]);           // Process the label of vertex v with the function f
+    
+	// Traverse all the neighbors, looking for unmarked vertices:
+	for (it = connections.begin( ); it != connections.end( ); ++it)
+	{
+	    if (!marked[*it])
+		rec_dfs(f, g, *it, marked);
+	}
+    }
+    
+    template <class Process, class Item, class SizeType>
+    void depth_first(Process f, graph<Item>& g, SizeType start)
+    // Precondion: start is a vertex number of the labeled graph g.
+    // Postcondition: A depth-first search of g has been executed,
+    // starting at the start vertex.  The function f has been applied to the
+    // label of each vertex visited by the search.
+    // Library facilities used: algorithm, cassert, graph.h
+    {
+	bool marked[g.MAXIMUM];
+
+	assert(start < g.size( ));
+	std::fill_n(marked, g.size( ), false);
+	rec_dfs(f, g, start, marked);
+    }
+
+    template <class Process, class Item, class SizeType>
+    void breadth_first(Process f, graph<Item>& g, SizeType start)
+    // Precondition: start is a vertex number of the labeled graph g.
+    // Postcondition: A breadth-first search of g has been executed,
+    // starting at the start vertex. The function f has been applied to the
+    // label of each vertex visited by the search.
+    // Library facilities used: algorithm, cassert, cstdlib, graph.h, queue
+    {
+	bool marked[g.MAXIMUM];
+	std::set<std::size_t> connections;
+	std::set<std::size_t>::iterator it;
+	std::queue<std::size_t> vertex_queue;       
+	assert(start < g.size( ));
+	std::fill_n(marked, g.size( ), false);
+	marked[start] = true;
+	f(g[start]);
+	vertex_queue.push(start);
+	do
+	{
+	    connections = g.neighbors(vertex_queue.front( ));
+	    vertex_queue.pop( );
+	    // Mark and process the unmarked neighbors,
+	    // and place them in the queue.
+	    for (it = connections.begin( ); it != connections.end( ); ++it)
+	    {
+		if (!marked[*it])
+		{
+		    marked[*it] = true;
+		    f(g[*it]);
+		    vertex_queue.push(*it);
+		}
+	    }
+	}   
+	while (!vertex_queue.empty( ));
+    }
+}