module BellmanFord(bellman_ford_shortest_paths) where
  import Graph
  import PropertyMap
  import Relax
  
  bellman_ford_shortest_paths ::
    (EdgeListGraph g e v, ReadWritePropertyMap d v n,
     ReadWritePropertyMap p v v, ReadPropertyMap w e n) =>
    g -> Int -> w -> p -> d -> (Combiner n) -> (Comparer n)
      -> (d, p, Bool)
  bellman_ford_shortest_paths g n w p d plus less =
    let (df,pf) = outer_loop 0 d p
        outer_loop k d1 p1 = 
	  if (k < n) then 
	    let (d2,p2,changed) = edge_loop (edges g) d1 p1 False
	    in if (changed) then
		 outer_loop (k + 1) d2 p2
	       else (d2,p2)
          else (d1, p1)
        edge_loop [] d p c = (d,p,c)
        edge_loop (e:es) d1 p1 c1 =
          let (d2,p2,c2) = relax e g w d1 p1 plus less
          in edge_loop es d2 p2 (c1 || c2)
        neg_cycles [] d w = False
        neg_cycles (e:es) d w =
          if (less (plus (get d (src e g)) (get w e))
                   (get d (tgt e g))) then
            True
          else neg_cycles es d w
    in (df, pf, neg_cycles (edges g) df w)