Inserted loop detection

4 files changed, 69 insertions, 0 deletions

diff --git a/Circuit.cpp b/Circuit.cpp
index e89fcb1..731e79f 100644
--- a/Circuit.cpp
+++ b/Circuit.cpp
@@ -14,6 +14,7 @@ void Circuit::create(string label, vector<string> nodes) {
 		return new_node(label, nodes[0]);
 
 	new_net(label, nodes);
+	ld->add_connection(label, nodes);
 }
 
 void Circuit::new_node(string label, string type) {
diff --git a/Circuit.h b/Circuit.h
index f261cd8..e4b48e1 100644
--- a/Circuit.h
+++ b/Circuit.h
@@ -7,6 +7,8 @@
 #include "Node.h"
 #include "Net.h"
 
+#include "LoopDetection.h"
+
 using std::string;
 using std::vector;
 
@@ -26,6 +28,8 @@ private:
 	std::map<string, Node *> nodes = {};
 	vector<Net *> nets = {};
 
+	LoopDetection * ld = new LoopDetection();
+
 	virtual Node * find_node(string label);
 };
 
diff --git a/LoopDetection.cpp b/LoopDetection.cpp
new file mode 100644
index 0000000..ac4ab93
--- /dev/null
+++ b/LoopDetection.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <unordered_map>
+#include <unordered_set>
+#include <stack>
+
+#include "LoopDetection.h"
+#include "Exception.h"
+
+LoopDetection::~LoopDetection(){}
+
+void LoopDetection::add_connection(const std::string &src, const std::vector<std::string> &dests)
+{
+	for (const auto &dest : dests) 
+		adj_list[src].push_back(dest);
+	
+	if (detect_cycle(src))
+		throw CircuitException( "Cycle detected starting from node: %s", src.c_str());
+}
+
+bool LoopDetection::detect_cycle(const std::string &start) {
+	std::unordered_set<std::string> visited;
+	std::unordered_set<std::string> rec_stack;
+
+	return is_cyclic(start, visited, rec_stack);
+}
+
+bool LoopDetection::is_cyclic(const std::string &node, std::unordered_set<std::string> &visited, std::unordered_set<std::string> &rec_stack) {
+	if (rec_stack.find(node) != rec_stack.end())
+		return true; // Cycle/Loop detected
+
+	if (visited.find(node) != visited.end())
+		return false;
+
+	visited.insert(node);
+	rec_stack.insert(node);
+
+	for (const auto &neighbor : adj_list[node])
+		if (is_cyclic(neighbor, visited, rec_stack))
+			return true;
+
+	rec_stack.erase(node);
+	return false;
+}
+
diff --git a/LoopDetection.h b/LoopDetection.h
new file mode 100644
index 0000000..f12c83b
--- /dev/null
+++ b/LoopDetection.h
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <vector>
+#include <string>
+#include <unordered_set>
+#include <unordered_map>
+
+class LoopDetection {
+public:
+	LoopDetection() = default;
+	virtual ~LoopDetection();
+
+	virtual void add_connection(const std::string &src, const std::vector<std::string> &dests);
+
+private:
+	std::unordered_map<std::string, std::vector<std::string>> adj_list;
+
+	virtual bool detect_cycle(const std::string &start);
+	virtual bool is_cyclic(const std::string &node, std::unordered_set<std::string> &visited, std::unordered_set<std::string> &rec_stack);
+};