SpanningForest

mill.internal.SpanningForest

Algorithm to compute the minimal spanning forest of a directed acyclic graph that covers a particular subset of importantVertices (a "Steiner Forest"), minimizing the maximum height of the resultant trees. When multiple solutions exist with the same height, one chosen is arbitrarily. (This is much simpler than the "real" algorithm which aims to minimize the sum of edge/vertex weights)

Returns the forest as a Node structure with the top-level node containing the roots of the forest

Attributes

Source
SpanningForest.scala
Graph
Supertypes
class Object
trait Matchable
class Any
Self type

Members list

Type members

Classlikes

case class Node(values: Map[Int, Node] = ...)

Attributes

Source
SpanningForest.scala
Supertypes
trait Serializable
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all

Value members

Concrete methods

def applyInferRoots(indexGraphEdges: Array[Array[Int]], importantVertices: Set[Int]): Node

Build spanning forest, inferring roots as importantVertices with no incoming edges from other importantVertices.

Build spanning forest, inferring roots as importantVertices with no incoming edges from other importantVertices.

Attributes

Source
SpanningForest.scala
def applyWithRoots(indexGraphEdges: Array[Array[Int]], roots: Set[Int], importantVertices: Set[Int]): Node

Build spanning forest with explicitly provided roots.

Build spanning forest with explicitly provided roots.

Attributes

Source
SpanningForest.scala
def breadthFirst[T](start: IterableOnce[T])(edges: T => IterableOnce[T]): Seq[T]

Attributes

Source
SpanningForest.scala
def graphMapToIndices[T](vertices: Iterable[T], edges: Map[T, Seq[T]]): (Map[T, Int], Array[Array[Int]])

Attributes

Source
SpanningForest.scala
def reverseEdges[T, V](edges: Iterable[(T, Iterable[V])]): Map[V, Vector[T]]

Attributes

Source
SpanningForest.scala
def spanningTreeToJsonTree(node: Node, stringify: Int => String): Obj

Attributes

Source
SpanningForest.scala
def writeJson(indexEdges: Array[Array[Int]], interestingIndices: Set[Int], render: Int => String): Obj

Attributes

Source
SpanningForest.scala
def writeJsonFile(path: Path, indexEdges: Array[Array[Int]], interestingIndices: Set[Int], render: Int => String): Unit

Attributes

Source
SpanningForest.scala