219 /** pendulum method **/ |
219 /** pendulum method **/ |
220 |
220 |
221 /*This is an auxiliary class which is used by the layout algorithm when |
221 /*This is an auxiliary class which is used by the layout algorithm when |
222 calculating coordinates with the "pendulum method". A "region" is a |
222 calculating coordinates with the "pendulum method". A "region" is a |
223 group of vertices which "stick together".*/ |
223 group of vertices which "stick together".*/ |
224 private class Region(init: Vertex) |
224 private class Region(val content: List[Vertex]) |
225 { |
225 { |
226 var content: List[Vertex] = List(init) |
|
227 |
|
228 def distance(metrics: Metrics, graph: Graph, that: Region): Double = |
226 def distance(metrics: Metrics, graph: Graph, that: Region): Double = |
229 vertex_left(metrics, graph, that.content.head) - |
227 vertex_left(metrics, graph, that.content.head) - |
230 vertex_right(metrics, graph, this.content.last) - |
228 vertex_right(metrics, graph, this.content.last) - |
231 metrics.box_gap |
229 metrics.box_gap |
232 |
230 |
237 bs.iterator.map(graph.get_node(_).x - x).sum / (bs.size max 1) |
235 bs.iterator.map(graph.get_node(_).x - x).sum / (bs.size max 1) |
238 }).sum / content.length).round.toDouble |
236 }).sum / content.length).round.toDouble |
239 |
237 |
240 def move(graph: Graph, dx: Double): Graph = |
238 def move(graph: Graph, dx: Double): Graph = |
241 if (dx == 0.0) graph else (graph /: content)(move_vertex(_, _, dx)) |
239 if (dx == 0.0) graph else (graph /: content)(move_vertex(_, _, dx)) |
242 } |
240 |
243 |
241 def combine(that: Region): Region = new Region(content ::: that.content) |
244 private type Regions = List[List[Region]] |
242 } |
245 |
243 |
246 private def pendulum( |
244 private def pendulum( |
247 options: Options, metrics: Metrics, levels: List[Level], levels_graph: Graph): Graph = |
245 options: Options, metrics: Metrics, levels: List[Level], levels_graph: Graph): Graph = |
248 { |
246 { |
249 def iteration(graph: Graph, regions: Regions, top_down: Boolean): (Graph, Regions, Boolean) = |
247 def combine_regions(graph: Graph, top_down: Boolean, level: List[Region]): List[Region] = |
250 { |
248 level match { |
251 val (graph1, regions1, moved) = |
249 case r1 :: rest => |
252 ((graph, List.empty[List[Region]], false) /: (if (top_down) regions else regions.reverse)) { |
250 val rest1 = combine_regions(graph, top_down, rest) |
253 case ((graph, tops, moved), bot) => |
251 rest1 match { |
254 val bot1 = collapse(graph, bot, top_down) |
252 case r2 :: rest2 => |
255 val (graph1, moved1) = deflect(graph, bot1, top_down) |
253 val d1 = r1.deflection(graph, top_down) |
256 (graph1, bot1 :: tops, moved || moved1) |
254 val d2 = r2.deflection(graph, top_down) |
|
255 if (// Do regions touch? |
|
256 r1.distance(metrics, graph, r2) <= 0.0 && |
|
257 // Do they influence each other? |
|
258 (d1 <= 0.0 && d2 < d1 || d2 > 0.0 && d1 > d2 || d1 > 0.0 && d2 < 0.0)) |
|
259 r1.combine(r2) :: rest2 |
|
260 else r1 :: rest1 |
|
261 case _ => r1 :: rest1 |
|
262 } |
|
263 case _ => level |
257 } |
264 } |
258 (graph1, regions1.reverse, moved) |
265 |
259 } |
266 def deflect(level: List[Region], top_down: Boolean, graph: Graph): (Graph, Boolean) = |
260 |
|
261 def collapse(graph: Graph, level: List[Region], top_down: Boolean): List[Region] = |
|
262 { |
|
263 if (level.size <= 1) level |
|
264 else { |
|
265 var next = level |
|
266 var regions_changed = true |
|
267 while (regions_changed) { |
|
268 regions_changed = false |
|
269 for (i <- Range(next.length - 1, 0, -1)) { |
|
270 val (r1, r2) = (next(i - 1), next(i)) |
|
271 val d1 = r1.deflection(graph, top_down) |
|
272 val d2 = r2.deflection(graph, top_down) |
|
273 |
|
274 if (// Do regions touch? |
|
275 r1.distance(metrics, graph, r2) <= 0.0 && |
|
276 // Do they influence each other? |
|
277 (d1 <= 0.0 && d2 < d1 || d2 > 0.0 && d1 > d2 || d1 > 0.0 && d2 < 0.0)) |
|
278 { |
|
279 regions_changed = true |
|
280 r1.content = r1.content ::: r2.content |
|
281 next = next.filter(next.indexOf(_) != i) |
|
282 } |
|
283 } |
|
284 } |
|
285 next |
|
286 } |
|
287 } |
|
288 |
|
289 def deflect(graph: Graph, level: List[Region], top_down: Boolean): (Graph, Boolean) = |
|
290 { |
267 { |
291 ((graph, false) /: (0 until level.length)) { |
268 ((graph, false) /: (0 until level.length)) { |
292 case ((graph, moved), i) => |
269 case ((graph, moved), i) => |
293 val r = level(i) |
270 val r = level(i) |
294 val d = r.deflection(graph, top_down) |
271 val d = r.deflection(graph, top_down) |
300 else d |
277 else d |
301 (r.move(graph, offset), moved || d != 0) |
278 (r.move(graph, offset), moved || d != 0) |
302 } |
279 } |
303 } |
280 } |
304 |
281 |
305 val initial_regions = levels.map(level => level.map(new Region(_))) |
282 val initial_regions = levels.map(level => level.map(l => new Region(List(l)))) |
306 |
283 |
307 ((levels_graph, initial_regions, true, true) /: |
284 ((levels_graph, initial_regions, true, true) /: |
308 (1 to options.int("graphview_iterations_pendulum"))) { |
285 (1 to options.int("graphview_iterations_pendulum"))) { |
309 case ((graph, regions, top_down, moved), _) => |
286 case ((graph, regions, top_down, moved), _) => |
310 if (moved) { |
287 if (moved) { |
311 val (graph1, regions1, moved1) = iteration(graph, regions, top_down) |
288 val (graph1, regions1, moved1) = |
312 (graph1, regions1, !top_down, moved1) |
289 ((graph, List.empty[List[Region]], false) /: |
|
290 (if (top_down) regions else regions.reverse)) { case ((graph, tops, moved), bot) => |
|
291 val bot1 = combine_regions(graph, top_down, bot) |
|
292 val (graph1, moved1) = deflect(bot1, top_down, graph) |
|
293 (graph1, bot1 :: tops, moved || moved1) |
|
294 } |
|
295 (graph1, regions1.reverse, !top_down, moved1) |
313 } |
296 } |
314 else (graph, regions, !top_down, moved) |
297 else (graph, regions, !top_down, moved) |
315 }._1 |
298 }._1 |
316 } |
299 } |
317 |
300 |