APShortestPath

The APShortestPath class is used to solve shortest path problems for graphs stored in matrices. It solves the All-Pairs Shortest Path (APSP) problem for directed graphs. The edge cost/distance (must be non-negative) can be stored in either a dense or sparse matrix. The Floyd-Warshall Algorithm is used.

See also: http://math.stackexchange.com/questions/240556/radius-diameter-and-center-of-graph
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm APSP can be used to determine a graph's eccentricities, radius and diameter. These can also be computed using a BFS-based algorithm.

Linear Supertypes

AnyRef, Any

Instance Constructors

new APShortestPath(c: Matrix)

c
the cost/distance matrix.

Value Members

final def !=(arg0: AnyRef): Boolean

Definition Classes
AnyRef
final def !=(arg0: Any): Boolean

Definition Classes
Any
final def ##(): Int

Definition Classes
AnyRef → Any
final def ==(arg0: AnyRef): Boolean

Definition Classes
AnyRef
final def ==(arg0: Any): Boolean

Definition Classes
Any
final def asInstanceOf[T0]: T0

Definition Classes
Any
def clone(): AnyRef

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
def diam: Double

Return the diameter (longest shortest path) of the graph.
Return the diameter (longest shortest path) of the graph. Must call 'spath' first.
def ecc(i: Int): Double

Return the eccentricity of vertex 'i'.
Return the eccentricity of vertex 'i'. Must call 'spath' first.
i
the vertex whose eccentricity is sought
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def hashCode(): Int

Definition Classes
AnyRef → Any
final def isInstanceOf[T0]: Boolean

Definition Classes
Any
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
def rad: Double

Return the radius (minimum eccentricity) of the graph.
Return the radius (minimum eccentricity) of the graph. Must call 'spath' first.
val rang: Range
def spath(): Unit

Determine the shortest from vertex i to j for all pairs of vertices.
Determine the shortest from vertex i to j for all pairs of vertices. The matrix 'c' is changed in-place from edge length to least distance.
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
def toString(): String

Definition Classes
AnyRef → Any
final def wait(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )

class APShortestPath extends AnyRef

Instance Constructors

new APShortestPath(c: Matrix)

Value Members

final def !=(arg0: AnyRef): Boolean

final def !=(arg0: Any): Boolean

final def ##(): Int

final def ==(arg0: AnyRef): Boolean

final def ==(arg0: Any): Boolean

final def asInstanceOf[T0]: T0

def clone(): AnyRef

def diam: Double

def ecc(i: Int): Double

final def eq(arg0: AnyRef): Boolean

def equals(arg0: Any): Boolean

def finalize(): Unit

final def getClass(): Class[_]

def hashCode(): Int

final def isInstanceOf[T0]: Boolean

final def ne(arg0: AnyRef): Boolean

final def notify(): Unit

final def notifyAll(): Unit

def rad: Double

val rang: Range

def spath(): Unit

final def synchronized[T0](arg0: ⇒ T0): T0

def toString(): String

final def wait(): Unit

final def wait(arg0: Long, arg1: Int): Unit

final def wait(arg0: Long): Unit

Inherited from AnyRef

Inherited from Any

Ungrouped