From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter15/graph.h | 99 +++++++++++++++++++++++++++++++++++++++++++ chapter15/graph.template | 100 ++++++++++++++++++++++++++++++++++++++++++++ chapter15/searches.h | 48 +++++++++++++++++++++ chapter15/searches.template | 93 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 340 insertions(+) create mode 100644 chapter15/graph.h create mode 100644 chapter15/graph.template create mode 100644 chapter15/searches.h create mode 100644 chapter15/searches.template (limited to 'chapter15') 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 (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 template class: +// static const size_t MAXIMUM = ______ +// graph::MAXIMUM is the maximum number of vertices that a graph can have. +// +// CONSTRUCTOR for the graph template class: +// graph( ) +// Postcondition: The graph has been initialized with no vertices and no edges. +// +// MODIFICATION MEMBER FUNCTIONS for the graph 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 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 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 template class: +// Assignments and the copy constructor may be used with graph objects. + +#ifndef MAIN_SAVITCH_GRAPH_H +#define MAIN_SAVITCH_GRAPH_H +#include // Provides size_t +#include // Provides set + +namespace main_savitch_15 +{ + template + 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 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 (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 // Provides assert +#include // Provides size_t +#include // Provides set + +namespace main_savitch_15 +{ + template + const std::size_t graph::MAXIMUM; + + template + void graph::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 + void graph::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 + bool graph::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 + Item& graph::operator[ ] (std::size_t vertex) + // Library facilities used: cassert, cstdlib + { + assert(vertex < size( )); + return labels[vertex]; // Returns a reference to the label + } + + template + Item graph::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 + std::set graph::neighbors(std::size_t vertex) const + // Library facilities used: cassert, cstdlib, set + { + std::set answer; + std::size_t i; + + assert(vertex < size( )); + + for (i = 0; i < size( ); ++i) + { + if (edges[vertex][i]) + answer.insert(i); + } + return answer; + } + + template + void graph::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 +// void rec_dfs(Process f, graph& 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 +// void depth_first(Process f, graph& 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 +// void breadth_first(Process f, graph& 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 + void rec_dfs(Process f, graph& g, SizeType v, bool marked[]); + + template + void depth_first(Process f, graph& g, SizeType start); + + template + void breadth_first(Process f, graph& 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 +#include +#include +#include +#include +#include "graph.h" + +namespace main_savitch_15 +{ + template + void rec_dfs(Process f, graph& 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 connections = g.neighbors(v); + std::set::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 + void depth_first(Process f, graph& 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 + void breadth_first(Process f, graph& 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 connections; + std::set::iterator it; + std::queue 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( )); + } +} -- cgit v1.2.3