Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 1.17 KB | None | 0 0
  1.   fun findCriticalEdges ((E,G) : ugraph) : edges =
  2.   let
  3.     val n = Seq.length G
  4.     val zs = Seq.tabulate (fn _=>0) n
  5.     val V = Seq.tabulate (fn i=>i) n
  6.     val X = STSeq.fromSeq (Seq.tabulate (fn _=>false) n)
  7.     val S = (STSeq.fromSeq zs, STSeq.fromSeq zs,0,~1)
  8.  
  9.     fun visit (D,LO,t,u) v =
  10.     let
  11.       val D' = STSeq.update(D,(v,t))
  12.       val LO' = STSeq.update(LO,(v,t))
  13.     in (D',LO',t+1,v) end
  14.  
  15.     fun revisit (D,LO,t,u) v =
  16.     let
  17.       val LO' = STSeq.update(LO,(u,min(STSeq.nth D v,STSeq.nth LO u)))
  18.     in (D,LO',t,v) end
  19.  
  20.     fun finish (D,LO,t,u) v =
  21.     let
  22.       val LO' = STSeq.update(LO,(u,min(STSeq.nth LO v, STSeq.nth LO u)))
  23.     in (D,LO',t,v) end
  24.  
  25.     fun dfs g ((s,x,p),v) =
  26.       if(p=v) then (s,x,p)
  27.       else if(STSeq.nth x v) then ((revisit s v),x,p)
  28.       else
  29.         let
  30.           val s' = visit s v
  31.           val x' = STSeq.update (x,(v,true))
  32.           val (s'',x'',p') = Seq.iterate (dfs g) (s',x',v) (Seq.nth g v)
  33.         in
  34.           ((finish s'' v),x'',p')
  35.         end
  36.  
  37.     val ((D,LO,_,_),_,_) = Seq.iterate (dfs G) (S,X,~1) V
  38.     fun crit(u,v) = (STSeq.nth D u) < (STSeq.nth LO v)
  39.   in
  40.     Seq.filter crit E
  41.   end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement