Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- fun findCriticalEdges ((E,G) : ugraph) : edges =
- let
- val n = Seq.length G
- val zs = Seq.tabulate (fn _=>0) n
- val V = Seq.tabulate (fn i=>i) n
- val X = STSeq.fromSeq (Seq.tabulate (fn _=>false) n)
- val S = (STSeq.fromSeq zs, STSeq.fromSeq zs,0,~1)
- fun visit (D,LO,t,u) v =
- let
- val D' = STSeq.update(D,(v,t))
- val LO' = STSeq.update(LO,(v,t))
- in (D',LO',t+1,v) end
- fun revisit (D,LO,t,u) v =
- let
- val LO' = STSeq.update(LO,(u,min(STSeq.nth D v,STSeq.nth LO u)))
- in (D,LO',t,v) end
- fun finish (D,LO,t,u) v =
- let
- val LO' = STSeq.update(LO,(u,min(STSeq.nth LO v, STSeq.nth LO u)))
- in (D,LO',t,v) end
- fun dfs g ((s,x,p),v) =
- if(p=v) then (s,x,p)
- else if(STSeq.nth x v) then ((revisit s v),x,p)
- else
- let
- val s' = visit s v
- val x' = STSeq.update (x,(v,true))
- val (s'',x'',p') = Seq.iterate (dfs g) (s',x',v) (Seq.nth g v)
- in
- ((finish s'' v),x'',p')
- end
- val ((D,LO,_,_),_,_) = Seq.iterate (dfs G) (S,X,~1) V
- fun crit(u,v) = (STSeq.nth D u) < (STSeq.nth LO v)
- in
- Seq.filter crit E
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement