cpp // Main.cpp // Driver code for the Graph program. // Handles user interaction and calls Graph class methods. // External Resources: // - C++ Standard Library documentation (iostream, vector, list, algorithm, set, utility) // (https://en.cppreference.com/w/) #include #include #include #include // Required for numeric_limits #include // Required for std::min/max #include // Required for tracking visited edges/vertices #include // Required for std::pair #include "Graph.h" // Function to get non-negative integer input from the user int getNonNegativeIntInput(const std::string& prompt) { int value; while (true) { std::cout << prompt; std::cin >> value; if (std::cin.fail() || value < 0) { std::cout << "Invalid input. Please enter a non-negative integer." << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); } else { std::cin.ignore(std::numeric_limits::max(), '\n'); // Clear the rest of the line return value; } } } // Function to get vertex input (non-negative or -1) int getVertexInput(const std::string& prompt) { int value; while (true) { std::cout << prompt; std::cin >> value; if (std::cin.fail() || (value < -1)) { std::cout << "Invalid input. Please enter a non-negative integer or -1." << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); } else { std::cin.ignore(std::numeric_limits::max(), '\n'); // Clear the rest of the line return value; } } } // Section 1: Create Adjacency List from User Input void buildGraphFromUserInput(Graph& graph) { int numVertices = getNonNegativeIntInput("How many Vertices are in this Graph? (Non-Negative Values)\n"); graph.buildFromInput(numVertices); } // Section 2: Print the Adjacency List void printGraphAdjacencyList(const Graph& graph) { std::cout << "\nAdjacency List:" << std::endl; graph.printAdjacencyList(); } // Section 3: Prompt user for a walk and validate std::vector getWalkFromUserInput(int numVertices) { std::vector walk; std::cout << "\nInput walk sequence of alternating vertices that starts and ends with a vertex: (-1 stops input)\n"; int vertex; while (true) { vertex = getVertexInput(""); if (vertex == -1) { break; } if (vertex < 0 || vertex >= numVertices) { std::cout << "Invalid vertex: " << vertex << ". Vertex must be between 0 and " << numVertices - 1 << "." << std::endl; // Don't add invalid vertex to walk } else { walk.push_back(vertex); } } return walk; } void validateAndAnalyzeWalk(const Graph& graph) { if (graph.getNumVertices() == 0) { std::cout << "\nCannot validate walk: Graph is empty." << std::endl; return; } std::vector walk = getWalkFromUserInput(graph.getNumVertices()); if (walk.empty()) { std::cout << "No walk sequence entered." << std::endl; return; } // Section 3: Validate Walk if (graph.isValidWalk(walk)) { std::cout << "WALK IS VALID!" << std::endl; // Section 4: Test and Prompt valid Walk Sequence Properties std::cout << "\nThe Walk Sequence <"; for (size_t i = 0; i < walk.size(); ++i) { std::cout << walk[i] << (i == walk.size() - 1 ? "" : ", "); } std::cout << "> has the following properties:" << std::endl; graph.getWalkProperties(walk); } else { std::cout << "WALK NOT VALID!" << std::endl; } } int main() { Graph graph; // Section 1: Create Adjacency List from User Input buildGraphFromUserInput(graph); // Section 2: Print the Adjacency List printGraphAdjacencyList(graph); // Section 3 & 4: Validate and Analyze Walk (Extra Credit) validateAndAnalyzeWalk(graph); return 0; } ```cpp // Graph.h // Defines the Graph class using an adjacency list. // External Resources: // - C++ Standard Library documentation (vector, list, algorithm, set, utility) // (https://en.cppreference.com/w/) #ifndef GRAPH_H #define GRAPH_H #include #include #include // Required for std::string #include // Required for std::set #include // Required for std::pair class Graph { private: std::vector> adjList; int numVertices; public: // Constructor Graph(); // Section 1: Create Adjacency List from User Input void buildFromInput(int n); // Section 2: Print the Adjacency List void printAdjacencyList() const; // Helper function to check if an edge exists bool hasEdge(int u, int v) const; // Section 3: Validate if a sequence is a valid walk bool isValidWalk(const std::vector& walk) const; // Section 4: Get properties of a valid walk void getWalkProperties(const std::vector& walk) const; // Getter for number of vertices int getNumVertices() const; }; #endif // GRAPH_H ``` ```cpp // Graph.cpp // Implements the Graph class methods. // External Resources: // - C++ Standard Library documentation (iostream, vector, list, algorithm, set, utility) // (https://en.cppreference.com/w/) #include "Graph.h" #include #include // Required for std::min/max #include // Required for std::set #include // Required for std::pair // Constructor Graph::Graph() : numVertices(0) {} // Section 1: Create Adjacency List from User Input void Graph::buildFromInput(int n) { if (n < 0) { std::cerr << "Error: Number of vertices cannot be negative." << std::endl; return; } numVertices = n; adjList.resize(numVertices); std::cout << "Building graph with " << numVertices << " vertices." << std::endl; for (int i = 0; i < numVertices; ++i) { std::cout << "For Vertex " << i << ": who are their Neighbors? (-1 stops inquiry)\n"; int neighbor; while (true) { std::cout << ""; // Prompt for input std::cin >> neighbor; if (std::cin.fail() || (neighbor < -1)) { std::cout << "Invalid input. Please enter a non-negative integer or -1." << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); continue; // Ask again for the same neighbor input } if (neighbor == -1) { break; // Stop inquiry for this vertex } if (neighbor < 0 || neighbor >= numVertices) { std::cout << "Invalid neighbor vertex: " << neighbor << ". Vertex must be between 0 and " << numVertices - 1 << "." << std::endl; // Don't add invalid neighbor, continue asking for neighbors for vertex i } else { // Add edge (i, neighbor) and (neighbor, i) for undirected graph adjList[i].push_back(neighbor); // Check if neighbor is already in the list to avoid duplicates in the list itself bool found = false; for(int existing_neighbor : adjList[neighbor]) { if (existing_neighbor == i) { found = true; break; } } if (!found) { adjList[neighbor].push_back(i); } } } std::cin.ignore(std::numeric_limits::max(), '\n'); // Clear the rest of the line after the -1 } } // Section 2: Print the Adjacency List void Graph::printAdjacencyList() const { if (numVertices == 0) { std::cout << "Graph is empty." << std::endl; return; } for (int i = 0; i < numVertices; ++i) { std::cout << i << ":"; for (int neighbor : adjList[i]) { std::cout << " " << neighbor; } std::cout << std::endl; } } // Helper function to check if an edge exists bool Graph::hasEdge(int u, int v) const { if (u < 0 || u >= numVertices || v < 0 || v >= numVertices) { return false; // Invalid vertices } for (int neighbor : adjList[u]) { if (neighbor == v) { return true; } } return false; } // Section 3: Validate if a sequence is a valid walk bool Graph::isValidWalk(const std::vector& walk) const { if (walk.size() < 1) { return false; // A walk must have at least one vertex } if (walk.size() == 1) { // A single vertex is a valid trivial walk return walk[0] >= 0 && walk[0] < numVertices; } for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Check if vertices are valid and if an edge exists between them if (u < 0 || u >= numVertices || v < 0 || v >= numVertices || !hasEdge(u, v)) { return false; // Invalid vertex or no edge between consecutive vertices } } return true; // All consecutive vertices are connected by an edge } // Section 4: Get properties of a valid walk void Graph::getWalkProperties(const std::vector& walk) const { if (!isValidWalk(walk)) { std::cout << "Cannot determine properties for an invalid walk." << std::endl; return; } if (walk.size() < 1) { std::cout << "Walk is empty." << std::endl; return; } // Open/Closed if (walk.size() > 1 && walk.front() == walk.back()) { std::cout << "CLOSED" << std::endl; } else { std::cout << "OPEN" << std::endl; } // Trail (no repeated edges) // Use a set to store unique edges {min(u,v), max(u,v)} std::set> visitedEdges; bool isTrail = true; if (walk.size() > 1) { for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Normalize the edge representation std::pair edge = {std::min(u, v), std::max(u, v)}; if (visitedEdges.count(edge)) { isTrail = false; break; } visitedEdges.insert(edge); } } if (isTrail) { std::cout << "TRAIL" << std::endl; } // Path (no repeated vertices, except possibly start/end for closed path) std::set visitedVertices; bool isPath = true; if (walk.size() > 0) { visitedVertices.insert(walk[0]); // Add the first vertex for (size_t i = 1; i < walk.size(); ++i) { int v = walk[i]; // If vertex is already in the set AND it's not the start vertex if (visitedVertices.count(v) && v != walk[0]) { isPath = false; break; } // If vertex is already in the set AND it IS the start vertex, // it's only allowed if it's the very last vertex of a closed walk. if (visitedVertices.count(v) && v == walk[0] && i != walk.size() - 1) { isPath = false; break; } visitedVertices.insert(v); } } if (isPath) { std::cout << "PATH" << std::endl; } // Circuit (closed trail) if (walk.size() > 1 && walk.front() == walk.back() && isTrail) { std::cout << "CIRCUIT" << std::endl; } // Cycle (closed path of length >= 3) // A cycle is a closed path where the only repeated vertex is the start/end vertex, // and the walk has length >= 3 (meaning at least 3 vertices and 3 edges). // A path with length 1 (v0) or 2 (v0, v1) cannot be a cycle. // A path v0, v1, v0 is a closed path of length 2, but not a cycle by standard definition. if (walk.size() > 2 && walk.front() == walk.back() && isPath) { // Check if the internal vertices are unique (already covered by isPath logic) // and if the length is >= 3 edges (walk.size() >= 4 vertices for non-trivial cycle) // or length 3 (v0, v1, v2, v0) bool internalVerticesUnique = true; std::set internalVisited; for(size_t i = 1; i < walk.size() - 1; ++i) { if (internalVisited.count(walk[i])) { internalVerticesUnique = false; break; } internalVisited.insert(walk[i]); } if (internalVerticesUnique) { std::cout << "CYCLE" << std::endl; } } } // Getter for number of vertices int Graph::getNumVertices() const { return numVertices; } ``` ```cpp // Main.cpp // Driver code for the Graph program. // Handles user interaction and calls Graph class methods. // External Resources: // - C++ Standard Library documentation (iostream, vector, list, algorithm, set, utility) // (https://en.cppreference.com/w/) #include #include #include #include // Required for numeric_limits #include // Required for std::min/max #include // Required for tracking visited edges/vertices #include // Required for std::pair #include // Required for std::string #include "Graph.h" // Function to get non-negative integer input from the user int getNonNegativeIntInput(const std::string& prompt) { int value; while (true) { std::cout << prompt; std::cin >> value; if (std::cin.fail() || value < 0) { std::cout << "Invalid input. Please enter a non-negative integer." << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); } else { std::cin.ignore(std::numeric_limits::max(), '\n'); // Clear the rest of the line return value; } } } // Function to get vertex input (non-negative or -1) int getVertexInput(const std::string& prompt) { int value; while (true) { std::cout << prompt; std::cin >> value; if (std::cin.fail() || (value < -1)) { std::cout << "Invalid input. Please enter a non-negative integer or -1." << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); } else { std::cin.ignore(std::numeric_limits::max(), '\n'); // Clear the rest of the line return value; } } } // Section 1: Create Adjacency List from User Input void buildGraphFromUserInput(Graph& graph) { int numVertices = getNonNegativeIntInput("How many Vertices are in this Graph? (Non-Negative Values)\n"); graph.buildFromInput(numVertices); } // Section 2: Print the Adjacency List void printGraphAdjacencyList(const Graph& graph) { std::cout << "\nAdjacency List:" << std::endl; graph.printAdjacencyList(); } // Section 3: Prompt user for a walk and validate std::vector getWalkFromUserInput(int numVertices) { std::vector walk; std::cout << "\nInput walk sequence of alternating vertices that starts and ends with a vertex: (-1 stops input)\n"; int vertex; while (true) { vertex = getVertexInput(""); if (vertex == -1) { break; } if (vertex < 0 || vertex >= numVertices) { std::cout << "Invalid vertex: " << vertex << ". Vertex must be between 0 and " << numVertices - 1 << "." << std::endl; // Don't add invalid vertex to walk } else { walk.push_back(vertex); } } return walk; } void validateAndAnalyzeWalk(const Graph& graph) { if (graph.getNumVertices() == 0) { std::cout << "\nCannot validate walk: Graph is empty." << std::endl; return; } std::vector walk = getWalkFromUserInput(graph.getNumVertices()); if (walk.empty()) { std::cout << "No walk sequence entered." << std::endl; return; } // Section 3: Validate Walk if (graph.isValidWalk(walk)) { std::cout << "WALK IS VALID!" << std::endl; // Section 4: Test and Prompt valid Walk Sequence Properties std::cout << "\nThe Walk Sequence <"; for (size_t i = 0; i < walk.size(); ++i) { std::cout << walk[i] << (i == walk.size() - 1 ? "" : ", "); } std::cout << "> has the following properties:" << std::endl; graph.getWalkProperties(walk); } else { std::cout << "WALK NOT VALID!" << std::endl; } } int main() { Graph graph; // Section 1: Create Adjacency List from User Input buildGraphFromUserInput(graph); // Section 2: Print the Adjacency List printGraphAdjacencyList(graph); // Section 3 & 4: Validate and Analyze Walk (Extra Credit) validateAndAnalyzeWalk(graph); return 0; } ``` ```cpp // Graph.h // Defines the Graph class using an adjacency list. // External Resources: // - C++ Standard Library documentation (vector, list, algorithm, set, utility) // (https://en.cppreference.com/w/) #ifndef GRAPH_H #define GRAPH_H #include #include #include // Required for std::string #include // Required for std::set #include // Required for std::pair #include // Required for numeric_limits class Graph { private: std::vector> adjList; int numVertices; public: // Constructor Graph(); // Section 1: Create Adjacency List from User Input void buildFromInput(int n); // Section 2: Print the Adjacency List void printAdjacencyList() const; // Helper function to check if an edge exists bool hasEdge(int u, int v) const; // Section 3: Validate if a sequence is a valid walk bool isValidWalk(const std::vector& walk) const; // Section 4: Get properties of a valid walk void getWalkProperties(const std::vector& walk) const; // Getter for number of vertices int getNumVertices() const; }; #endif // GRAPH_H ``` ```cpp // Graph.cpp // Implements the Graph class methods. // External Resources: // - C++ Standard Library documentation (iostream, vector, list, algorithm, set, utility) // (https://en.cppreference.com/w/) #include "Graph.h" #include #include // Required for std::min/max #include // Required for std::set #include // Required for std::pair #include // Required for numeric_limits // Constructor Graph::Graph() : numVertices(0) {} // Section 1: Create Adjacency List from User Input void Graph::buildFromInput(int n) { if (n < 0) { std::cerr << "Error: Number of vertices cannot be negative." << std::endl; return; } numVertices = n; adjList.resize(numVertices); std::cout << "Building graph with " << numVertices << " vertices." << std::endl; for (int i = 0; i < numVertices; ++i) { std::cout << "For Vertex " << i << ": who are their Neighbors? (-1 stops inquiry)\n"; int neighbor; while (true) { std::cout << ""; // Prompt for input std::cin >> neighbor; if (std::cin.fail() || (neighbor < -1)) { std::cout << "Invalid input. Please enter a non-negative integer or -1." << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); continue; // Ask again for the same neighbor input } if (neighbor == -1) { break; // Stop inquiry for this vertex } if (neighbor < 0 || neighbor >= numVertices) { std::cout << "Invalid neighbor vertex: " << neighbor << ". Vertex must be between 0 and " << numVertices - 1 << "." << std::endl; // Don't add invalid neighbor, continue asking for neighbors for vertex i } else { // Add edge (i, neighbor) and (neighbor, i) for undirected graph adjList[i].push_back(neighbor); // Check if neighbor is already in the list to avoid duplicates in the list itself bool found = false; for(int existing_neighbor : adjList[neighbor]) { if (existing_neighbor == i) { found = true; break; } } if (!found) { adjList[neighbor].push_back(i); } } } std::cin.ignore(std::numeric_limits::max(), '\n'); // Clear the rest of the line after the -1 } } // Section 2: Print the Adjacency List void Graph::printAdjacencyList() const { if (numVertices == 0) { std::cout << "Graph is empty." << std::endl; return; } for (int i = 0; i < numVertices; ++i) { std::cout << i << ":"; for (int neighbor : adjList[i]) { std::cout << " " << neighbor; } std::cout << std::endl; } } // Helper function to check if an edge exists bool Graph::hasEdge(int u, int v) const { if (u < 0 || u >= numVertices || v < 0 || v >= numVertices) { return false; // Invalid vertices } for (int neighbor : adjList[u]) { if (neighbor == v) { return true; } } return false; } // Section 3: Validate if a sequence is a valid walk bool Graph::isValidWalk(const std::vector& walk) const { if (walk.size() < 1) { return false; // A walk must have at least one vertex } if (walk.size() == 1) { // A single vertex is a valid trivial walk return walk[0] >= 0 && walk[0] < numVertices; } for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Check if vertices are valid and if an edge exists between them if (u < 0 || u >= numVertices || v < 0 || v >= numVertices || !hasEdge(u, v)) { return false; // Invalid vertex or no edge between consecutive vertices } } return true; // All consecutive vertices are connected by an edge } // Section 4: Get properties of a valid walk void Graph::getWalkProperties(const std::vector& walk) const { if (!isValidWalk(walk)) { std::cout << "Cannot determine properties for an invalid walk." << std::endl; return; } if (walk.size() < 1) { std::cout << "Walk is empty." << std::endl; return; } // Open/Closed if (walk.size() > 1 && walk.front() == walk.back()) { std::cout << "CLOSED" << std::endl; } else { std::cout << "OPEN" << std::endl; } // Trail (no repeated edges) // Use a set to store unique edges {min(u,v), max(u,v)} std::set> visitedEdges; bool isTrail = true; if (walk.size() > 1) { for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Normalize the edge representation std::pair edge = {std::min(u, v), std::max(u, v)}; if (visitedEdges.count(edge)) { isTrail = false; break; } visitedEdges.insert(edge); } } if (isTrail) { std::cout << "TRAIL" << std::endl; } // Path (no repeated vertices, except possibly start/end for closed path) std::set visitedVertices; bool isPath = true; if (walk.size() > 0) { visitedVertices.insert(walk[0]); // Add the first vertex for (size_t i = 1; i < walk.size(); ++i) { int v = walk[i]; // If vertex is already in the set AND it's not the start vertex if (visitedVertices.count(v) && v != walk[0]) { isPath = false; break; } // If vertex is already in the set AND it IS the start vertex, // it's only allowed if it's the very last vertex of a closed walk. if (visitedVertices.count(v) && v == walk[0] && i != walk.size() - 1) { isPath = false; break; } visitedVertices.insert(v); } } if (isPath) { std::cout << "PATH" << std::endl; } // Circuit (closed trail) if (walk.size() > 1 && walk.front() == walk.back() && isTrail) { std::cout << "CIRCUIT" << std::endl; } // Cycle (closed path of length >= 3) // A cycle is a closed path where the only repeated vertex is the start/end vertex, // and the walk has length >= 3 (meaning at least 3 vertices and 3 edges). // A path with length 1 (v0) or 2 (v0, v1) cannot be a cycle. // A path v0, v1, v0 is a closed path of length 2, but not a cycle by standard definition. if (walk.size() > 2 && walk.front() == walk.back() && isPath) { // Check if the internal vertices are unique (already covered by isPath logic) // and if the length is >= 3 edges (walk.size() >= 4 vertices for non-trivial cycle) // or length 3 (v0, v1, v2, v0) bool internalVerticesUnique = true; std::set internalVisited; for(size_t i = 1; i < walk.size() - 1; ++i) { if (internalVisited.count(walk[i])) { internalVerticesUnique = false; break; } internalVisited.insert(walk[i]); } if (internalVerticesUnique) { std::cout << "CYCLE" << std::endl; } } } // Getter for number of vertices int Graph::getNumVertices() const { return numVertices; } ``` ```