/* main.cpp Driver code for Adjacency List Graph Assignment No external resources used. */ #include #include #include #include "Graph.h" // Function to read a walk from user input std::vector readWalk(int numVertices) { std::vector walk; std::cout << "Input walk sequence of alternating vertices that starts and ends with a vertex: (-1 stops input)" << std::endl; int v; while (true) { std::cin >> v; if (v == -1) break; if (v < 0 || v >= numVertices) { std::cout << "Invalid vertex. Please enter a value between 0 and " << numVertices - 1 << " or -1 to stop." << std::endl; continue; } walk.push_back(v); } return walk; } // Check if the walk is valid in the graph bool isValidWalk(const Graph& g, const std::vector& walk) { if (walk.size() < 2) return false; for (size_t i = 0; i + 1 < walk.size(); ++i) { if (!g.hasEdge(walk[i], walk[i + 1])) { return false; } } return true; } // Check walk properties: OPEN/CLOSED, TRAIL, PATH, CIRCUIT, CYCLE void printWalkProperties(const std::vector& walk) { // OPEN/CLOSED bool isClosed = (walk.front() == walk.back()); // TRAIL: no repeated edges std::set> edgeSet; bool isTrail = true; for (size_t i = 0; i + 1 < walk.size(); ++i) { int u = walk[i], v = walk[i + 1]; std::pair e = std::make_pair(u, v); if (edgeSet.count(e)) { isTrail = false; break; } edgeSet.insert(e); } // PATH: no repeated vertices (except possibly first==last for closed) std::set vertexSet; bool isPath = true; for (size_t i = 0; i < walk.size(); ++i) { if (vertexSet.count(walk[i])) { // Allow first==last for closed if (isClosed && i == walk.size() - 1 && walk[i] == walk[0]) continue; isPath = false; break; } vertexSet.insert(walk[i]); } // CIRCUIT: closed and trail bool isCircuit = isClosed && isTrail; // CYCLE: closed and path (length > 2) bool isCycle = isClosed && isPath && walk.size() > 2; std::cout << "The Walk Sequence <"; for (size_t i = 0; i < walk.size(); ++i) { std::cout << walk[i]; if (i + 1 < walk.size()) std::cout << ", "; } std::cout << "> has the following properties:" << std::endl; std::cout << (isClosed ? "CLOSED" : "OPEN") << std::endl; if (isTrail) std::cout << "TRAIL" << std::endl; if (isPath) std::cout << "PATH" << std::endl; if (isCircuit) std::cout << "CIRCUIT" << std::endl; if (isCycle) std::cout << "CYCLE" << std::endl; } int main() { int numVertices; std::cout << "How many Vertices are in this Graph? (Non-Negative Values)" << std::endl; while (true) { std::cin >> numVertices; if (numVertices >= 0) break; std::cout << "Please enter a non-negative value." << std::endl; } Graph g(numVertices); // Part 1: Build adjacency list from user input g.buildAdjListFromInput(); // Part 2: Print adjacency list std::cout << std::endl << "Adjacency List:" << std::endl; g.printAdjList(); // Part 3: Walk validation std::vector walk = readWalk(numVertices); if (isValidWalk(g, walk)) { std::cout << "WALK IS VALID!" << std::endl; printWalkProperties(walk); } else { std::cout << "WALK NOT VALID!" << std::endl; } return 0; } #ifndef GRAPH_H #define GRAPH_H #include #include class Graph { private: int numVertices; std::vector> adjList; public: Graph(int vertices); // Part 1: Build adjacency list from user input void buildAdjListFromInput(); // Part 2: Print adjacency list void printAdjList() const; // Part 3: Check if edge exists bool hasEdge(int u, int v) const; }; #endif #include "Graph.h" #include #include Graph::Graph(int vertices) : numVertices(vertices), adjList(vertices) {} // Part 1: Build adjacency list from user input void Graph::buildAdjListFromInput() { for (int i = 0; i < numVertices; ++i) { std::cout << "For Vertex " << i << ": who are their Neighbors? (-1 stops inquiry)" << std::endl; int neighbor; while (true) { std::cin >> neighbor; if (neighbor == -1) break; if (neighbor < 0 || neighbor >= numVertices) { std::cout << "Invalid neighbor. Please enter a value between 0 and " << numVertices - 1 << " or -1 to stop." << std::endl; continue; } adjList[i].push_back(neighbor); } } } // Part 2: Print adjacency list void Graph::printAdjList() const { for (int i = 0; i < numVertices; ++i) { std::cout << i << ":"; for (int neighbor : adjList[i]) { std::cout << " " << neighbor; } std::cout << std::endl; } } // Part 3: Check if edge exists bool Graph::hasEdge(int u, int v) const { if (u < 0 || u >= numVertices) return false; for (int neighbor : adjList[u]) { if (neighbor == v) return true; } return false; }