src/Pure/General/graph.scala
changeset 48348 cbb25adad26f
parent 46712 8650d9a95736
child 48350 09bf3b73e446
equal deleted inserted replaced
48347:8bb27ab9e841 48348:cbb25adad26f
    12 import scala.annotation.tailrec
    12 import scala.annotation.tailrec
    13 
    13 
    14 
    14 
    15 object Graph
    15 object Graph
    16 {
    16 {
    17   class Duplicate[Key](x: Key) extends Exception
    17   class Duplicate[Key](val key: Key) extends Exception
    18   class Undefined[Key](x: Key) extends Exception
    18   class Undefined[Key](val key: Key) extends Exception
    19   class Cycles[Key](cycles: List[List[Key]]) extends Exception
    19   class Cycles[Key](val cycles: List[List[Key]]) extends Exception
    20 
    20 
    21   def empty[Key, A](implicit ord: Ordering[Key]): Graph[Key, A] =
    21   def empty[Key, A](implicit ord: Ordering[Key]): Graph[Key, A] =
    22     new Graph[Key, A](SortedMap.empty(ord))
    22     new Graph[Key, A](SortedMap.empty(ord))
    23 
    23 
    24   def string[A]: Graph[String, A] = empty(Ordering.String)
    24   def string[A]: Graph[String, A] = empty(Ordering.String)
   207         case Nil => add_edge(x, y)
   207         case Nil => add_edge(x, y)
   208         case cycles => throw new Graph.Cycles(cycles.map(x :: _))
   208         case cycles => throw new Graph.Cycles(cycles.map(x :: _))
   209       }
   209       }
   210     }
   210     }
   211 
   211 
   212   def add_deps_cyclic(y: Key, xs: List[Key]): Graph[Key, A] =
   212   def add_deps_acyclic(y: Key, xs: List[Key]): Graph[Key, A] =
   213     (this /: xs)(_.add_edge_acyclic(_, y))
   213     (this /: xs)(_.add_edge_acyclic(_, y))
   214 
   214 
   215   def topological_order: List[Key] = all_succs(minimals)
   215   def topological_order: List[Key] = all_succs(minimals)
   216 }
   216 }