From 359357f4c5609cded790c5890c0c0dd7a2cf73d6 Mon Sep 17 00:00:00 2001 From: Fabrice Desclaux Date: Wed, 23 Mar 2016 16:06:31 +0100 Subject: Core/Graph: add loop test --- miasm2/core/graph.py | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) (limited to 'miasm2/core/graph.py') diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index c98bf8a9..d97ca8be 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -478,6 +478,34 @@ class DiGraph(object): """Performs a depth first search on the reversed graph from @head""" return self._walk_generic_first(head, -1, self.predecessors_iter) + def has_loop(self): + """Return True if the graph contains at least a cycle""" + todo = list(self.nodes()) + # tested nodes + done = set() + # current DFS nodes + current = set() + while todo: + node = todo.pop() + if node in done: + continue + + if node in current: + # DFS branch end + for succ in self.successors_iter(node): + if succ in current: + return True + # A node cannot be in current AND in done + current.remove(node) + done.add(node) + else: + # Launch DFS from node + todo.append(node) + current.add(node) + todo += self.successors(node) + + return False + def compute_natural_loops(self, head): """ Computes all natural loops in the graph. -- cgit 1.4.1