Commits

Daniel Plohmann committed ecc835e

crypto id: added functionality to limit display to blocks in loops

Comments (0)

Files changed (1)

idascope/core/Tarjan.py

+#!/usr/bin/python
+class Tarjan():
+    """
+    Tarjan's Algorithm (named for its discoverer, Robert Tarjan) is a graph theory algorithm
+    for finding the strongly connected components of a graph.
+    This can be used to find loops.
+    Based on: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
+
+    Implementation by Dries Verdegem:
+    http://www.logarithmic.net/pfh-files/blog/01208083168/tarjan.py
+    Taken from Dr. Paul Harrison Blog:
+    http://www.logarithmic.net/pfh/blog/01208083168
+    """
+
+    def __init__(self):
+        pass
+
+    def calculate_strongly_connected_components(self, graph):
+        """
+        @param graph: a dictionary describing a directed graph, with keys as nodes and values as successors.
+        @type graph: (dict)
+        @return: (a list of tuples) describing the SCCs
+        """
+
+        index_counter = [0]
+        stack = []
+        lowlinks = {}
+        index = {}
+        result = []
+
+        def calculate_scc_for_node(node):
+            # set the depth index for this node to the smallest unused index
+            index[node] = index_counter[0]
+            lowlinks[node] = index_counter[0]
+            index_counter[0] += 1
+            stack.append(node)
+
+            # Consider successors of `node`
+            try:
+                successors = graph[node]
+            except:
+                successors = []
+            for successor in successors:
+                if successor not in lowlinks:
+                    # Successor has not yet been visited; recurse on it
+                    calculate_scc_for_node(successor)
+                    lowlinks[node] = min(lowlinks[node],lowlinks[successor])
+                elif successor in stack:
+                    # the successor is in the stack and hence in the current strongly connected component (SCC)
+                    lowlinks[node] = min(lowlinks[node],index[successor])
+
+            # If `node` is a root node, pop the stack and generate an SCC
+            if lowlinks[node] == index[node]:
+                connected_component = []
+
+                while True:
+                    successor = stack.pop()
+                    connected_component.append(successor)
+                    if successor == node: break
+                component = tuple(connected_component)
+                # storing the result
+                result.append(component)
+
+        for node in graph:
+            if node not in lowlinks:
+                calculate_scc_for_node(node)
+
+        return result