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 apply(indexGraphEdges: Array[Array[Int]], importantVertices: Set[Int], limitToImportantVertices: Boolean): Node

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