FilesExpand file tree

master

/

tarjan.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

153 lines (124 loc) · 4.1 KB

master

/

tarjan.py

Copy path

Top

File metadata and controls

• Code
• Blame

153 lines (124 loc) · 4.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

"""

Implements Tarjan's algorithm for finding strongly connected components

in a graph.

https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

"""

class Node(object):

def __init__(self, name):

self.name = name

def __eq__(self, obj):

if isinstance(obj, Node):

return obj.name == self.name

elif isinstance(obj, str):

return obj == self.name

return False

def __repr__(self):

return self.name

def __hash__(self):

return hash(self.name)

class DirectedEdge(object):

def __init__(self, node_from, node_to):

self.nf = node_from

self.nt = node_to

def __eq__(self, obj):

if isinstance(obj, DirectedEdge):

return obj.nf == self.nf and obj.nt == self.nt

return False

def __repr__(self):

return '({0} -> {1})'.format(self.nf, self.nt)

class DirectedGraph(object):

def __init__(self, load_dict={}):

self.nodes = []

self.edges = []

self.adjmt = {}

if load_dict and type(load_dict) == dict:

for v in load_dict:

node_from = self.add_node(v)

self.adjmt[node_from] = []

for w in load_dict[v]:

node_to = self.add_node(w)

self.adjmt[node_from].append(node_to)

self.add_edge(v, w)

def add_node(self, node_name):

try:

return self.nodes[self.nodes.index(node_name)]

except ValueError:

node = Node(node_name)

self.nodes.append(node)

return node

def add_edge(self, node_name_from, node_name_to):

try:

node_from = self.nodes[self.nodes.index(node_name_from)]

node_to = self.nodes[self.nodes.index(node_name_to)]

self.edges.append(DirectedEdge(node_from, node_to))

except ValueError:

pass

INDEX = 0

STACK = []

def strongconnect(graph, v, sccs):

global INDEX, STACK

# Set the depth index for v to the smallest unused index

v.index = INDEX

v.lowlink = INDEX

INDEX += 1

STACK.append(v)

v.on_stack = True

# Consider successors of v

for w in graph.adjmt[v]:

if w.index == None:

# Successor w has not yet been visited; recurse on it

strongconnect(graph, w, sccs)

v.lowlink = min(v.lowlink, w.lowlink)

elif w.on_stack:

# Successor w is in stack S and hence in the current SCC

# If w is not on stack, then (v, w) is a cross-edge in the DFS tree and must be ignored

# Note: The next line may look odd - but is correct.

# It says w.index not w.lowlink; that is deliberate and from the original paper

v.lowlink = min(v.lowlink, w.index)

# If v is a root node, pop the stack and generate an SCC

if v.lowlink == v.index:

# start a new strongly connected component

scc = []

while True:

w = STACK.pop()

w.on_stack = False

scc.append(w)

if w == v:

break

sccs.append(scc)

def tarjan(graph):

# Set all node index to None

for v in graph.nodes:

v.index = None

sccs = []

for v in graph.nodes:

if v.index == None:

strongconnect(graph, v, sccs)

return sccs

if __name__ == '__main__':

# Graph from https://en.wikipedia.org/wiki/File:Scc.png

example = {

'A': ['B'],

'B': ['C', 'E', 'F'],

'C': ['D', 'G'],

'D': ['C', 'H'],

'E': ['A', 'F'],

'F': ['G'],

'G': ['F'],

'H': ['D', 'G']

}

g = DirectedGraph(example)

print(tarjan(g))

# Graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#/media/File:Tarjan%27s_Algorithm_Animation.gif

example = {

'A': ['E'],

'B': ['A'],

'C': ['B', 'D'],

'D': ['C'],

'E': ['B'],

'F': ['B', 'E', 'G'],

'G': ['F', 'C'],

'H': ['G', 'H', 'D']

}

g = DirectedGraph(example)

print(tarjan(g))