110 |
110 |
111 |
111 |
112 /* reachability */ |
112 /* reachability */ |
113 |
113 |
114 /*reachable nodes with length of longest path*/ |
114 /*reachable nodes with length of longest path*/ |
115 def reachable_length(next: Key => Keys, xs: List[Key]): Map[Key, Int] = |
115 def reachable_length( |
|
116 count: Key => Int, |
|
117 next: Key => Keys, |
|
118 xs: List[Key]): Map[Key, Int] = |
116 { |
119 { |
117 def reach(length: Int)(rs: Map[Key, Int], x: Key): Map[Key, Int] = |
120 def reach(length: Int)(rs: Map[Key, Int], x: Key): Map[Key, Int] = |
118 if (rs.get(x) match { case Some(n) => n >= length case None => false }) rs |
121 if (rs.get(x) match { case Some(n) => n >= length case None => false }) rs |
119 else ((rs + (x -> length)) /: next(x))(reach(length + 1)) |
122 else ((rs + (x -> length)) /: next(x))(reach(length + count(x))) |
120 (Map.empty[Key, Int] /: xs)(reach(0)) |
123 (Map.empty[Key, Int] /: xs)(reach(0)) |
121 } |
124 } |
122 def node_height: Map[Key, Int] = reachable_length(imm_preds(_), maximals) |
125 def node_height(count: Key => Int): Map[Key, Int] = |
123 def node_depth: Map[Key, Int] = reachable_length(imm_succs(_), minimals) |
126 reachable_length(count, imm_preds(_), maximals) |
|
127 def node_depth(count: Key => Int): Map[Key, Int] = |
|
128 reachable_length(count, imm_succs(_), minimals) |
124 |
129 |
125 /*reachable nodes with size limit*/ |
130 /*reachable nodes with size limit*/ |
126 def reachable_limit( |
131 def reachable_limit( |
127 limit: Int, |
132 limit: Int, |
128 count: Key => Boolean, |
133 count: Key => Int, |
129 next: Key => Keys, |
134 next: Key => Keys, |
130 xs: List[Key]): Keys = |
135 xs: List[Key]): Keys = |
131 { |
136 { |
132 def reach(res: (Int, Keys), x: Key): (Int, Keys) = |
137 def reach(res: (Int, Keys), x: Key): (Int, Keys) = |
133 { |
138 { |
134 val (n, rs) = res |
139 val (n, rs) = res |
135 if (rs.contains(x)) res |
140 if (rs.contains(x)) res |
136 else ((if (count(x)) n + 1 else n, rs + x) /: next(x))(reach _) |
141 else ((n + count(x), rs + x) /: next(x))(reach _) |
137 } |
142 } |
138 |
143 |
139 @tailrec def reachs(size: Int, rs: Keys, rest: List[Key]): Keys = |
144 @tailrec def reachs(size: Int, rs: Keys, rest: List[Key]): Keys = |
140 rest match { |
145 rest match { |
141 case Nil => rs |
146 case Nil => rs |