Dijkstra
net.walend.disentangle.graph.semiring.Dijkstra$
object Dijkstra
An implementation of Dijkstra's algorithm for general graph minimization for both single-source and single-sink.
Attributes
- Since:
v0.1.0
- Graph
- Supertypes
- class Objecttrait Matchableclass Any
- Self type
- Dijkstra.type
Members list
Concise view
Value members
Concrete methods
def allNodesSingleSource[Node, Label, Key](labelDigraph: IndexedLabelDigraph[Node, Label], support: SemiringSupport[Label, Key]): Seq[(Node, Node, Label)]
O(n^2 ln(n) + na)
O(n^2 ln(n) + na)
Attributes
def allPairsLeastPaths[Node, EdgeLabel, Label, Key](edges: Iterable[(Node, Node, EdgeLabel)], support: SemiringSupport[Label, Key], labelForEdge: (Node, Node, EdgeLabel) => Label, nodeOrder: Seq[Node]): Seq[(Node, Node, Label)]
O(n^2 ln(n) + na)
O(n^2 ln(n) + na)
Attributes
def allPairsShortestPaths[Node, EdgeLabel](edges: Iterable[(Node, Node, EdgeLabel)], nodeOrder: Seq[Node]): Seq[(Node, Node, Option[FirstStepsTrait[Node, Int]])]
def createLabelDigraph[Node, EdgeLabel, Label, Key](edges: Iterable[(Node, Node, EdgeLabel)], support: SemiringSupport[Label, Key], labelForEdge: (Node, Node, EdgeLabel) => Label, nodeOrder: Seq[Node]): IndexedLabelDigraph[Node, Label]
Create a digraph of Labels from an edge list.
Create a digraph of Labels from an edge list.
O(n ln(n) + a ln(n))
Attributes
- Returns:
an IndexedDigraph with all nodes, a self-edge for each node with the semiring's identifier, and an edge for label edge specified by labelForEdge.
def dijkstraSingleSink[Node, Label, Key](initialDigraph: IndexedLabelDigraph[Node, Label], support: SemiringSupport[Label, Key])(sink: InnerNodeType): IndexedSeq[(Node, Node, Label)]
Dijkstra's algorithm for a single sink.
Dijkstra's algorithm for a single sink.
O(n ln(n) + a)
Attributes
def dijkstraSingleSource[Node, Label, Key](initialGraph: IndexedLabelDigraph[Node, Label], support: SemiringSupport[Label, Key])(source: InnerNodeType): Seq[(Node, Node, Label)]
Dijkstra's algorithm.
Dijkstra's algorithm.
O(n ln(n) + e)
Attributes
def relaxSink[Node, Label, Key](digraph: IndexedLabelDigraph[Node, Label], labels: ArrayBuffer[Label], semiring: Semiring)(from: InnerEdgeType, through: InnerNodeType, to: InnerNodeType): Label
O(1)
O(1)
Attributes
def relaxSource[Node, Label, Key](digraph: IndexedLabelDigraph[Node, Label], labels: ArrayBuffer[Label], semiring: Semiring)(from: InnerNodeType, through: InnerNodeType, to: InnerEdgeType): Label
O(1)
O(1)