equal
deleted
inserted
replaced
89 |
89 |
90 /*transitive*/ |
90 /*transitive*/ |
91 def all_preds(xs: List[Key]): List[Key] = reachable(imm_preds, xs)._1.flatten |
91 def all_preds(xs: List[Key]): List[Key] = reachable(imm_preds, xs)._1.flatten |
92 def all_succs(xs: List[Key]): List[Key] = reachable(imm_succs, xs)._1.flatten |
92 def all_succs(xs: List[Key]): List[Key] = reachable(imm_succs, xs)._1.flatten |
93 |
93 |
|
94 /*strongly connected components; see: David King and John Launchbury, |
|
95 "Structuring Depth First Search Algorithms in Haskell"*/ |
|
96 def strong_conn: List[List[Key]] = |
|
97 reachable(imm_preds, all_succs(keys.toList))._1.filterNot(_.isEmpty).reverse |
|
98 |
94 |
99 |
95 /* minimal and maximal elements */ |
100 /* minimal and maximal elements */ |
96 |
101 |
97 def minimals: List[Key] = |
102 def minimals: List[Key] = |
98 (List.empty[Key] /: rep) { |
103 (List.empty[Key] /: rep) { |
110 |
115 |
111 def new_node(x: Key, info: A): Graph[Key, A] = |
116 def new_node(x: Key, info: A): Graph[Key, A] = |
112 { |
117 { |
113 if (rep.isDefinedAt(x)) throw new Graph.Duplicate(x) |
118 if (rep.isDefinedAt(x)) throw new Graph.Duplicate(x) |
114 else new Graph[Key, A](rep + (x -> (info, (Set.empty, Set.empty)))) |
119 else new Graph[Key, A](rep + (x -> (info, (Set.empty, Set.empty)))) |
|
120 } |
|
121 |
|
122 def default_node(x: Key, info: A): Graph[Key, A] = |
|
123 { |
|
124 if (rep.isDefinedAt(x)) this |
|
125 else new_node(x, info) |
115 } |
126 } |
116 |
127 |
117 def del_nodes(xs: List[Key]): Graph[Key, A] = |
128 def del_nodes(xs: List[Key]): Graph[Key, A] = |
118 { |
129 { |
119 xs.foreach(get_entry) |
130 xs.foreach(get_entry) |