cpp // Graph.h #ifndef GRAPH_H #define GRAPH_H #include #include #include #include #include // For std::pair // Citation: Standard C++ library features (vector, iostream, set, algorithm, utility) are used. class Graph { private: std::vector> adjList; int numVertices; public: // Constructor Graph(int numVertices); // Function to input graph from user void inputGraph(); // Function to print the adjacency list void printGraph() const; // Function to check if a walk is valid bool isValidWalk(const std::vector& walk) const; // Function to analyze walk properties void analyzeWalkProperties(const std::vector& walk) const; // Helper to get number of vertices int getNumVertices() const { return numVertices; } }; #endif // GRAPH_H ```cpp // Graph.cpp #include "Graph.h" // Citation: Standard C++ library features (vector, iostream, set, algorithm, utility) are used. // Constructor Graph::Graph(int numVertices) : numVertices(numVertices) { if (numVertices >= 0) { adjList.resize(numVertices); } else { this->numVertices = 0; // Handle non-negative requirement std::cerr << "Error: Number of vertices must be non-negative. Initializing with 0 vertices." << std::endl; } } // Function to input graph from user void Graph::inputGraph() { if (numVertices <= 0) { std::cout << "Graph has no vertices to input." << std::endl; return; } std::cout << "--- Input Graph Edges ---" << std::endl; for (int i = 0; i < numVertices; ++i) { std::cout << "For Vertex " << i << ": who are their Neighbors? (-1 stops inquiry)" << std::endl; int neighbor; while (std::cin >> neighbor && neighbor != -1) { if (neighbor >= 0 && neighbor < numVertices) { // Add edge (i, neighbor) adjList[i].push_back(neighbor); // Assuming undirected graph, add edge (neighbor, i) as well // Check if neighbor already has i to avoid duplicates in adjacency list representation bool found = false; for(int existing_neighbor : adjList[neighbor]) { if (existing_neighbor == i) { found = true; break; } } if (!found) { adjList[neighbor].push_back(i); } } else { std::cout << "Invalid neighbor vertex: " << neighbor << ". Must be between 0 and " << numVertices - 1 << "." << std::endl; } } // Clear the input buffer after reading numbers std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); } std::cout << "--- Graph Input Complete ---" << std::endl; } // Function to print the adjacency list void Graph::printGraph() const { if (numVertices <= 0) { std::cout << "Graph is empty." << std::endl; return; } std::cout << "\n--- Adjacency List ---" << std::endl; for (int i = 0; i < numVertices; ++i) { std::cout << i << ":"; // Sort neighbors for consistent output (optional but nice) std::vector sorted_neighbors = adjList[i]; std::sort(sorted_neighbors.begin(), sorted_neighbors.end()); for (int neighbor : sorted_neighbors) { std::cout << " " << neighbor; } std::cout << std::endl; } std::cout << "----------------------" << std::endl; } // Function to check if a walk is valid bool Graph::isValidWalk(const std::vector& walk) const { if (walk.size() < 2) { // A walk must have at least two vertices (one edge) to be non-trivial // A single vertex sequence could be considered a trivial walk, but the prompt implies edges. // Let's require at least 2 vertices for a valid walk check involving edges. return walk.size() == 1; // A single vertex is a valid trivial walk } for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Check if vertices are within bounds if (u < 0 || u >= numVertices || v < 0 || v >= numVertices) { std::cout << "Walk contains invalid vertex index." << std::endl; return false; } // Check if (u, v) is an edge in the graph bool found_edge = false; for (int neighbor : adjList[u]) { if (neighbor == v) { found_edge = true; break; } } if (!found_edge) { std::cout << "Invalid walk: No edge between vertex " << u << " and vertex " << v << "." << std::endl; return false; } } return true; // All consecutive pairs are edges } // Function to analyze walk properties void Graph::analyzeWalkProperties(const std::vector& walk) const { if (walk.empty()) { std::cout << "Cannot analyze properties of an empty walk." << std::endl; return; } std::cout << "\n--- Walk Properties ---" << std::endl; // Print the walk sequence std::cout << "Walk Sequence: <"; for (size_t i = 0; i < walk.size(); ++i) { std::cout << walk[i] << (i == walk.size() - 1 ? "" : ", "); } std::cout << ">" << std::endl; // 1. Open/Closed bool isClosed = (walk.size() > 1 && walk.front() == walk.back()); std::cout << (isClosed ? "CLOSED" : "OPEN") << std::endl; if (walk.size() < 2) { std::cout << "Walk is too short for further properties (Trail, Path, Circuit, Cycle)." << std::endl; std::cout << "-----------------------" << std::endl; return; } // 2. Trail (all edges distinct) std::set> visited_edges; bool isTrail = true; for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Canonical representation for undirected edge (u, v) std::pair edge = {std::min(u, v), std::max(u, v)}; if (visited_edges.count(edge)) { isTrail = false; break; } visited_edges.insert(edge); } if (isTrail) { std::cout << "TRAIL" << std::endl; } // 3. Path (all vertices distinct, except possibly start/end for closed path) std::set visited_vertices; bool isPath = true; for (size_t i = 0; i < walk.size(); ++i) { int v = walk[i]; if (visited_vertices.count(v)) { // If vertex is already visited, it's not a path unless it's the last vertex // and the walk is closed, and this is the start vertex. if (!(isClosed && i == walk.size() - 1 && v == walk.front())) { isPath = false; break; } } visited_vertices.insert(v); } // Special check for path: if closed, the start vertex should only appear again at the end. // The set check above handles this correctly if the start vertex is inserted first. // Let's re-verify the path condition for closed walks: // All vertices v0, ..., vL-1 must be distinct. vL must be equal to v0. if (isClosed && walk.size() > 1) { std::set vertices_except_last; bool distinct_internal = true; for(size_t i = 0; i < walk.size() - 1; ++i) { if (vertices_except_last.count(walk[i])) { distinct_internal = false; break; } vertices_except_last.insert(walk[i]); } // A closed walk is a path if v0...vL-1 are distinct AND vL == v0 isPath = distinct_internal && (walk.back() == walk.front()); } else { // For open walks, all vertices must be distinct std::set all_vertices; isPath = true; for(int v : walk) { if (all_vertices.count(v)) { isPath = false; break; } all_vertices.insert(v); } } if (isPath) { std::cout << "PATH" << std::endl; } // 4. Circuit (closed trail) if (isClosed && isTrail) { std::cout << "CIRCUIT" << std::endl; } // 5. Cycle (closed path of length >= 3) // Length of walk v0, v1, ..., vL is L (number of edges). // Number of vertices is L+1. // A cycle requires L >= 3, which means number of vertices >= 4. // Also, for a cycle, the only repeated vertex is the start/end vertex. // The path check already ensures v0...vL-1 are distinct for a closed path. if (isClosed && isPath && walk.size() >= 4) { // Walk length >= 3 means vertices >= 4 std::cout << "CYCLE" << std::endl; } else if (isClosed && isPath && walk.size() == 3) { // Special case: A closed path of length 2 (3 vertices v0, v1, v0) is a cycle if v0 != v1. // The path check ensures v0 and v1 are distinct here. if (walk[0] != walk[1]) { std::cout << "CYCLE" << std::endl; } } std::cout << "-----------------------" << std::endl; } ``` ```cpp // Main.cpp #include "Graph.h" #include // Required for numeric_limits // Citation: Standard C++ library features (iostream, vector, limits) are used. int main() { int numVertices; // 1. Create Graph from User Input std::cout << "How many Vertices are in this Graph? (Non-Negative Values)" << std::endl; while (!(std::cin >> numVertices) || numVertices < 0) { std::cout << "Invalid input. Please enter a non-negative integer for the number of vertices." << std::endl; std::cin.clear(); // Clear error flags std::cin.ignore(std::numeric_limits::max(), '\n'); // Discard invalid input } Graph graph(numVertices); graph.inputGraph(); // 2. Print the Adjacency List graph.printGraph(); // 3. & 4. Walk Validation and Properties (Extra Credit) std::cout << "\n--- Walk Validation and Properties ---" << std::endl; std::cout << "Input walk sequence of alternating vertices that starts and ends with a vertex: (-1 stops input)" << std::endl; std::vector walk; int vertex; while (std::cin >> vertex && vertex != -1) { walk.push_back(vertex); } // Clear the input buffer after reading numbers std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); if (walk.empty()) { std::cout << "No walk sequence entered." << std::endl; } else { if (graph.isValidWalk(walk)) { std::cout << "WALK IS VALID!" << std::endl; graph.analyzeWalkProperties(walk); } else { std::cout << "WALK NOT VALID!" << std::endl; } } return 0; } ``` ```cpp // Graph.h #ifndef GRAPH_H #define GRAPH_H #include #include #include #include #include // For std::pair #include // Required for numeric_limits // Citation: Standard C++ library features (vector, iostream, set, algorithm, utility, limits) are used. class Graph { private: std::vector> adjList; int numVertices; public: // Constructor Graph(int numVertices); // Function to input graph from user void inputGraph(); // Function to print the adjacency list void printGraph() const; // Function to check if a walk is valid bool isValidWalk(const std::vector& walk) const; // Function to analyze walk properties void analyzeWalkProperties(const std::vector& walk) const; // Helper to get number of vertices int getNumVertices() const { return numVertices; } }; #endif // GRAPH_H ``` ```cpp // Graph.cpp #include "Graph.h" // Citation: Standard C++ library features (vector, iostream, set, algorithm, utility, limits) are used. // Constructor Graph::Graph(int numVertices) : numVertices(numVertices) { if (numVertices >= 0) { adjList.resize(numVertices); } else { this->numVertices = 0; // Handle non-negative requirement std::cerr << "Error: Number of vertices must be non-negative. Initializing with 0 vertices." << std::endl; } } // Function to input graph from user void Graph::inputGraph() { if (numVertices <= 0) { std::cout << "Graph has no vertices to input." << std::endl; return; } std::cout << "--- Input Graph Edges ---" << std::endl; for (int i = 0; i < numVertices; ++i) { std::cout << "For Vertex " << i << ": who are their Neighbors? (-1 stops inquiry)" << std::endl; int neighbor; while (std::cin >> neighbor && neighbor != -1) { if (neighbor >= 0 && neighbor < numVertices) { // Add edge (i, neighbor) adjList[i].push_back(neighbor); // Assuming undirected graph, add edge (neighbor, i) as well // Check if neighbor already has i to avoid duplicates in adjacency list representation bool found = false; for(int existing_neighbor : adjList[neighbor]) { if (existing_neighbor == i) { found = true; break; } } if (!found) { adjList[neighbor].push_back(i); } } else { std::cout << "Invalid neighbor vertex: " << neighbor << ". Must be between 0 and " << numVertices - 1 << "." << std::endl; } } // Clear the input buffer after reading numbers std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); } std::cout << "--- Graph Input Complete ---" << std::endl; } // Function to print the adjacency list void Graph::printGraph() const { if (numVertices <= 0) { std::cout << "Graph is empty." << std::endl; return; } std::cout << "\n--- Adjacency List ---" << std::endl; for (int i = 0; i < numVertices; ++i) { std::cout << i << ":"; // Sort neighbors for consistent output (optional but nice) std::vector sorted_neighbors = adjList[i]; std::sort(sorted_neighbors.begin(), sorted_neighbors.end()); for (int neighbor : sorted_neighbors) { std::cout << " " << neighbor; } std::cout << std::endl; } std::cout << "----------------------" << std::endl; } // Function to check if a walk is valid bool Graph::isValidWalk(const std::vector& walk) const { if (walk.empty()) { std::cout << "Walk is empty." << std::endl; return false; // An empty sequence is not typically considered a valid walk } if (walk.size() == 1) { int v = walk[0]; if (v < 0 || v >= numVertices) { std::cout << "Walk contains invalid vertex index." << std::endl; return false; } return true; // A single vertex is a valid trivial walk } for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Check if vertices are within bounds if (u < 0 || u >= numVertices || v < 0 || v >= numVertices) { std::cout << "Walk contains invalid vertex index." << std::endl; return false; } // Check if (u, v) is an edge in the graph bool found_edge = false; for (int neighbor : adjList[u]) { if (neighbor == v) { found_edge = true; break; } } if (!found_edge) { std::cout << "Invalid walk: No edge between vertex " << u << " and vertex " << v << "." << std::endl; return false; } } return true; // All consecutive pairs are edges } // Function to analyze walk properties void Graph::analyzeWalkProperties(const std::vector& walk) const { if (walk.empty()) { std::cout << "Cannot analyze properties of an empty walk." << std::endl; return; } std::cout << "\n--- Walk Properties ---" << std::endl; // Print the walk sequence std::cout << "Walk Sequence: <"; for (size_t i = 0; i < walk.size(); ++i) { std::cout << walk[i] << (i == walk.size() - 1 ? "" : ", "); } std::cout << ">" << std::endl; if (walk.size() == 1) { std::cout << "OPEN" << std::endl; // A single vertex walk is open std::cout << "Walk is too short for further properties (Trail, Path, Circuit, Cycle)." << std::endl; std::cout << "-----------------------" << std::endl; return; } // 1. Open/Closed bool isClosed = (walk.front() == walk.back()); std::cout << (isClosed ? "CLOSED" : "OPEN") << std::endl; // 2. Trail (all edges distinct) std::set> visited_edges; bool isTrail = true; for (size_t i = 0; i < walk.size() - 1; ++i) { int u = walk[i]; int v = walk[i+1]; // Canonical representation for undirected edge (u, v) std::pair edge = {std::min(u, v), std::max(u, v)}; if (visited_edges.count(edge)) { isTrail = false; break; } visited_edges.insert(edge); } if (isTrail) { std::cout << "TRAIL" << std::endl; } // 3. Path (all vertices distinct, except possibly start/end for closed path) std::set visited_vertices_for_path; bool isPath = true; for (size_t i = 0; i < walk.size(); ++i) { int v = walk[i]; if (visited_vertices_for_path.count(v)) { // If vertex is already visited, it's not a path unless it's the last vertex // and the walk is closed, and this is the start vertex. if (!(isClosed && i == walk.size() - 1 && v == walk.front())) { isPath = false; break; } } visited_vertices_for_path.insert(v); } // Additional check for closed path: the start vertex should only appear again at the end. // The set check above handles this correctly if the start vertex is inserted first. // Let's re-verify the path condition for closed walks: // All vertices v0, ..., vL-1 must be distinct. vL must be equal to v0. if (isClosed && walk.size() > 1) { std::set vertices_except_last; bool distinct_internal = true; for(size_t i = 0; i < walk.size() - 1; ++i) { if (vertices_except_last.count(walk[i])) { distinct_internal = false; break; } vertices_except_last.insert(walk[i]); } // A closed walk is a path if v0...vL-1 are distinct AND vL == v0 isPath = distinct_internal && (walk.back() == walk.front()); } else { // For open walks, all vertices must be distinct std::set all_vertices; isPath = true; for(int v : walk) { if (all_vertices.count(v)) { isPath = false; break; } all_vertices.insert(v); } } if (isPath) { std::cout << "PATH" << std::endl; } // 4. Circuit (closed trail) if (isClosed && isTrail) { std::cout << "CIRCUIT" << std::endl; } // 5. Cycle (closed path of length >= 3) // Length of walk v0, v1, ..., vL is L (number of edges). // Number of vertices is L+1. // A cycle requires L >= 3, which means number of vertices >= 4. // Also, for a cycle, the only repeated vertex is the start/end vertex. // The path check already ensures v0...vL-1 are distinct for a closed path. if (isClosed && isPath && walk.size() >= 4) { // Walk length >= 3 means vertices >= 4 std::cout << "CYCLE" << std::endl; } else if (isClosed && isPath && walk.size() == 3) { // Special case: A closed path of length 2 (3 vertices v0, v1, v0) is a cycle if v0 != v1. // The path check ensures v0 and v1 are distinct here. if (walk[0] != walk[1]) { std::cout << "CYCLE" << std::endl; } } std::cout << "-----------------------" << std::endl; } ``` ```cpp // Main.cpp #include "Graph.h" #include // Required for numeric_limits // Citation: Standard C++ library features (iostream, vector, limits) are used. int main() { int numVertices; // 1. Create Graph from User Input std::cout << "How many Vertices are in this Graph? (Non-Negative Values)" << std::endl; while (!(std::cin >> numVertices) || numVertices < 0) { std::cout << "Invalid input. Please enter a non-negative integer for the number of vertices." << std::endl; std::cin.clear(); // Clear error flags std::cin.ignore(std::numeric_limits::max(), '\n'); // Discard invalid input } Graph graph(numVertices); graph.inputGraph(); // 2. Print the Adjacency List graph.printGraph(); // 3. & 4. Walk Validation and Properties (Extra Credit) std::cout << "\n--- Walk Validation and Properties ---" << std::endl; std::cout << "Input walk sequence of alternating vertices that starts and ends with a vertex: (-1 stops input)" << std::endl; std::vector walk; int vertex; while (std::cin >> vertex && vertex != -1) { walk.push_back(vertex); } // Clear the input buffer after reading numbers std::cin.clear(); std::cin.ignore(std::numeric_limits::max(), '\n'); if (walk.empty()) { std::cout << "No walk sequence entered." << std::endl; } else { if (graph.isValidWalk(walk)) { std::cout << "WALK IS VALID!" << std::endl; graph.analyzeWalkProperties(walk); } else { std::cout << "WALK NOT VALID!" << std::endl; } } return 0; } ```