80 lines
1.7 KiB
Nim
80 lines
1.7 KiB
Nim
import sequtils, strutils, tables
|
|
|
|
type
|
|
|
|
Node = ref object
|
|
val: int
|
|
index: int
|
|
lowLink: int
|
|
onStack: bool
|
|
|
|
Nodes = seq[Node]
|
|
|
|
DirectedGraph = object
|
|
nodes: seq[Node]
|
|
edges: Table[int, Nodes]
|
|
|
|
|
|
func initNode(n: int): Node =
|
|
Node(val: n, index: -1, lowLink: -1, onStack: false)
|
|
|
|
|
|
func `$`(node: Node): string = $node.val
|
|
|
|
|
|
func tarjan(g: DirectedGraph): seq[Nodes] =
|
|
var index = 0
|
|
var s: seq[Node]
|
|
var sccs: seq[Nodes]
|
|
|
|
|
|
func strongConnect(v: Node) =
|
|
|
|
# Set the depth index for "v" to the smallest unused index.
|
|
v.index = index
|
|
v.lowLink = index
|
|
inc index
|
|
s.add v
|
|
v.onStack = true
|
|
|
|
# Consider successors of "v".
|
|
for w in g.edges[v.val]:
|
|
if w.index < 0:
|
|
# Successor "w" has not yet been visited; recurse on it.
|
|
w.strongConnect()
|
|
v.lowLink = min(v.lowLink, w.lowLink)
|
|
elif w.onStack:
|
|
# Successor "w" is in stack "s" and hence in the current SCC.
|
|
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:
|
|
var scc: Nodes
|
|
while true:
|
|
let w = s.pop()
|
|
w.onStack = false
|
|
scc.add w
|
|
if w == v: break
|
|
sccs.add scc
|
|
|
|
|
|
for v in g.nodes:
|
|
if v.index < 0:
|
|
v.strongConnect()
|
|
result = move(sccs)
|
|
|
|
|
|
when isMainModule:
|
|
|
|
let vs = toSeq(0..7).map(initNode)
|
|
let es = {0: @[vs[1]],
|
|
1: @[vs[2]],
|
|
2: @[vs[0]],
|
|
3: @[vs[1], vs[2], vs[4]],
|
|
4: @[vs[5], vs[3]],
|
|
5: @[vs[2], vs[6]],
|
|
6: @[vs[5]],
|
|
7: @[vs[4], vs[7], vs[6]]}.toTable
|
|
var g = DirectedGraph(nodes: vs, edges: es)
|
|
let sccs = g.tarjan()
|
|
echo sccs.join("\n")
|