Brandes
net.walend.disentangle.graph.semiring.Brandes$
object Brandes
Brandes' algorithm for betweenness and minimal paths.
Attributes
- Since:
v0.1.0
- Graph
- Supertypes
- class Objecttrait Matchableclass Any
- Self type
- Brandes.type
Members list
Concise view
Type members
Classlikes
case class BrandesSteps[Node, CoreLabel](weight: CoreLabel, pathCount: Int, choiceIndexes: Seq[Int])
Attributes
- Graph
- Supertypes
- trait Serializabletrait Producttrait Equalsclass Objecttrait Matchableclass Any
case class BrandesSupport[Node, CoreLabel, Key](coreSupport: SemiringSupport[CoreLabel, Key]) extends SemiringSupport[Option[BrandesSteps[Node, CoreLabel]], Key]
Attributes
- Companion:
- object
- Graph
- Supertypes
- trait Serializabletrait Producttrait Equalsclass Objecttrait Matchableclass Any
object BrandesSupport
Attributes
- Companion:
- class
- Graph
- Supertypes
- trait Producttrait Mirrorclass Objecttrait Matchableclass Any
- Self type
- BrandesSupport.type
Value members
Concrete methods
def allLeastPathsAndBetweenness[Node, EdgeLabel, CoreLabel, Key](edges: Iterable[(Node, Node, EdgeLabel)], nodeOrder: Seq[Node], coreSupport: SemiringSupport[CoreLabel, Key], labelForEdge: (Node, Node, EdgeLabel) => CoreLabel): (IndexedSeq[(Node, Node, Option[BrandesSteps[Node, CoreLabel]])], Map[Node, Double])
This method runs Dijkstra's algorithm and finds betweenness for all nodes in the label graph.
This method runs Dijkstra's algorithm and finds betweenness for all nodes in the label graph.
Attributes
def brandesDijkstra[Node, Label, Key](labelDigraph: IndexedLabelDigraph[Node, Label], support: SemiringSupport[Label, Key])(sink: InnerNodeType): (IndexedSeq[(Node, Node, Label)], Stack[(InnerNodeType, Label)])
Dijkstra's algorithm for a single sink, with a Seq of visited edges to support Brandes' algorithm.
Dijkstra's algorithm for a single sink, with a Seq of visited edges to support Brandes' algorithm.
O(n ln(n) + a)
Attributes
def createLabelDigraph[Node, EdgeLabel, CoreLabel, Key](edges: Iterable[(Node, Node, EdgeLabel)], nodeOrder: Seq[Node], support: BrandesSupport[Node, CoreLabel, Key], labelForEdge: (Node, Node, EdgeLabel) => CoreLabel): IndexedLabelDigraph[Node, Option[BrandesSteps[Node, CoreLabel]]]
Create a digraph of Labels from an edge list.
Create a digraph of Labels from an edge list.
Attributes
- Returns:
an IndexedDigraph with graph's nodes, a self-edge for each node with the semiring's identifier, and an edge for each edge specified by labelForEdge.
def partialBetweenness[Node, CoreLabel, Label <: Option[BrandesSteps[Node, CoreLabel]], Key](support: BrandesSupport[Node, CoreLabel, Key], labelGraph: IndexedLabelDigraph[Node, Label])(sink: InnerNodeType, stack: Stack[(InnerNodeType, Label)], shortestPathsToSink: IndexedSeq[(Node, Node, Label)]): IndexedSeq[Double]
Find partial betweenness
Find partial betweenness
O(a)