# simpliFiRE.IDAscope / idascope / core / helpers / Tarjan.py

 ```Daniel Plohmann ecc835e 2012-09-18 ``` ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68``` ```#!/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 ```
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.