object Vertex { object Ordering extends scala.math.Ordering[Vertex] { def compare(v1: Vertex, v2: Vertex): Int =
(v1, v2) match { case (Node(a), Node(b)) => Graph_Display.Node.Ordering.compare(a, b) case (Dummy(a1, a2, i), Dummy(b1, b2, j)) =>
Graph_Display.Node.Ordering.compare(a1, b1) match { case 0 =>
Graph_Display.Node.Ordering.compare(a2, b2) match { case 0 => i compare j case ord => ord
} case ord => ord
} case (Node(a), Dummy(b, _, _)) =>
Graph_Display.Node.Ordering.compare(a, b) match { case 0 => -1 case ord => ord
} case (Dummy(a, _, _), Node(b)) =>
Graph_Display.Node.Ordering.compare(a, b) match { case 0 => 1 case ord => ord
}
}
}
}
val initial_graph =
make_graph(
input_graph.iterator.map(
{ case (a, (content, (_, bs))) => val lines = split_lines(node_text(a, content)) val w2 = metrics.node_width2(lines) val h2 = metrics.node_height2(lines.length)
((Node(a), Info(0.0, 0.0, w2, h2, lines)), bs.toList.map(Node.apply))
}).toList)
val initial_levels: Levels =
initial_graph.topological_order.foldLeft(empty_levels) { case (levels, vertex) => val level =
1 + initial_graph.imm_preds(vertex).foldLeft(-1) { case (m, v) => m max levels(v) }
levels + (vertex -> level)
}
/* graph with dummies */
val dummy_info = Info(0.0, 0.0, metrics.dummy_size2, metrics.dummy_size2, Nil)
val (dummy_graph, dummy_levels) =
input_graph.edges_iterator.foldLeft((initial_graph, initial_levels)) { case ((graph, levels), (node1, node2)) => val v1 = Node(node1); val l1 = levels(v1) val v2 = Node(node2); val l2 = levels(v2) if (l2 - l1 <= 1) (graph, levels) else { val dummies_levels =
(for { (l, i) <- ((l1 + 1) until l2).iterator.zipWithIndex } yield (Dummy(node1, node2, i), l)).toList val dummies = dummies_levels.map(_._1)
val levels1 = dummies_levels.foldLeft(levels)(_ + _) val graph1 =
(v1 :: dummies ::: List(v2)).sliding(2)
.foldLeft(dummies.foldLeft(graph)(_.new_node(_, dummy_info)).del_edge(v1, v2)) { case (g, Seq(a, b)) => g.add_edge(a, b) case (g, _) => g
}
(graph1, levels1)
}
}
/* minimize edge crossings and initial coordinates */
val levels = minimize_crossings(options, dummy_graph, level_list(dummy_levels))
val levels_graph: Graph =
levels.foldLeft((dummy_graph, 0.0)) { case ((graph, y), level) => val num_lines = level.foldLeft(0) { case (n, v) => n max graph.get_node(v).lines.length } val num_edges = level.foldLeft(0) { case (n, v) => n + graph.imm_succs(v).size }
val y1 = y + metrics.node_height2(num_lines)
val graph1 =
level.foldLeft((graph, 0.0)) { case ((g, x), v) => val info = g.get_node(v) val g1 = g.map_node(v, _ => info.copy(x = x + info.width2, y = y1)) val x1 = x + info.width + metrics.gap
(g1, x1)
}._1
val y2 = y1 + metrics.level_height2(num_lines, num_edges)
(graph1, y2)
}._1
/* pendulum/rubberband layout */
val output_graph =
rubberband(options, metrics, levels,
pendulum(options, metrics, levels, levels_graph))
new Layout(metrics, input_graph, output_graph)
}
}
/** edge crossings **/
privatetype Level = List[Vertex]
privatedef minimize_crossings(
options: Options,
graph: Graph,
levels: List[Level]
): List[Level] = { def resort(parent: Level, child: Level, top_down: Boolean): Level =
child.map({ v => val ps = if (top_down) graph.imm_preds(v) else graph.imm_succs(v) val weight =
ps.foldLeft(0.0) { case (w, p) => w + (0 max parent.indexOf(p)) } / (ps.size max 1)
(v, weight)
}).sortBy(_._2).map(_._1)
(1 to (2 * options.int("graphview_iterations_minimize_crossings"))).
foldLeft((levels, count_crossings(graph, levels))) { case ((old_levels, old_crossings), iteration) => val top_down = (iteration % 2 == 1) val new_levels = if (top_down) {
old_levels.tail.foldLeft(List(old_levels.head)) { case (tops, bot) => resort(tops.head, bot, top_down) :: tops
}.reverse
} else { val rev_old_levels = old_levels.reverse
rev_old_levels.tail.foldLeft(List(rev_old_levels.head)) { case (bots, top) => resort(bots.head, top, top_down) :: bots
}
} val new_crossings = count_crossings(graph, new_levels) if (new_crossings < old_crossings)
(new_levels, new_crossings) else
(old_levels, old_crossings)
}._1
}
privatedef level_list(levels: Levels): List[Level] = { val max_lev = levels.foldLeft(-1) { case (m, (_, l)) => m max l } val buckets = new Array[Level](max_lev + 1) for (l <- 0 to max_lev) { buckets(l) = Nil } for ((v, l) <- levels) { buckets(l) = v :: buckets(l) }
buckets.iterator.map(_.sorted(Vertex.Ordering)).toList
}
privatedef count_crossings(graph: Graph, levels: List[Level]): Int =
levels.iterator.sliding(2).map { case Seq(top, bot) =>
top.iterator.zipWithIndex.map { case (outer_parent, outer_parent_index) =>
graph.imm_succs(outer_parent).iterator.map(bot.indexOf(_)).map(outer_child =>
(0 until outer_parent_index).iterator.map(inner_parent =>
graph.imm_succs(top(inner_parent)).iterator.map(bot.indexOf(_))
.count(inner_child => outer_child < inner_child)).sum).sum
}.sum case _ => 0
}.sum
/** pendulum method **/
/*This is an auxiliary class which is used by the layout algorithm when calculating coordinates with the "pendulum method". A "region" is a
group of vertices which "stick together".*/ privateclass Region(val content: List[Vertex]) { def distance(metrics: Metrics, graph: Graph, that: Region): Double =
vertex_left(graph, that.content.head) -
vertex_right(graph, this.content.last) -
metrics.gap
def deflection(graph: Graph, top_down: Boolean): Double =
((for (a <- content.iterator) yield { val x = graph.get_node(a).x val bs = if (top_down) graph.imm_preds(a) else graph.imm_succs(a)
bs.iterator.map(graph.get_node(_).x - x).sum / (bs.size max 1)
}).sum / content.length).round.toDouble
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
