Class DijkstraGraphDistance

Compute Dijkstra shortest-path algorithm on a graph. Computation is index-based, but can use sparse data structures if the index space will be sparse.

Construction is somewhat complicated, but see shortcut static methods at end of file for common construction cases:

• MeshVertices(mesh) - compute on vertices of mesh
• MeshVertices(mesh) - compute on vertices of mesh

Inheritance

Object

DijkstraGraphDistance

Inherited Members

Object.ToString()

Object.Equals(Object)

Object.Equals(Object, Object)

Object.ReferenceEquals(Object, Object)

Object.GetHashCode()

Object.GetType()

Object.MemberwiseClone()

Namespace: g3

Assembly: cs.temp.dll.dll

Syntax

public class DijkstraGraphDistance

Constructors

DijkstraGraphDistance(Int32, Boolean, Func<Int32, Boolean>, Func<Int32, Int32, Single>, Func<Int32, IEnumerable<Int32>>, IEnumerable<Vector2d>)

Constructor configures the graph as well. Graph is not specified explicitly, is provided via functions, for maximum flexibility.

nMaxID: maximum ID that will be added. bSparse: is ID space large but sparse? this will save memory nodeFilterF: restrict to a subset of nodes (eg if you want to filter neighbours but not change neighboursF nodeDistanceF: must return (symmetric) distance between two nodes a and b neighboursF: return enumeration of neighbours of a seeds: although Vector2d, are actually pairs (id, seedvalue) (or use AddSeed later)

Declaration

public DijkstraGraphDistance(int nMaxID, bool bSparse, Func<int, bool> nodeFilterF, Func<int, int, float> nodeDistanceF, Func<int, IEnumerable<int>> neighboursF, IEnumerable<Vector2d> seeds = null)

Parameters

Type	Name	Description
Int32	nMaxID
Boolean	bSparse
Func<Int32, Boolean>	nodeFilterF
Func<Int32, Int32, Single>	nodeDistanceF
Func<Int32, IEnumerable<Int32>>	neighboursF
IEnumerable<Vector2d>	seeds

Fields

InvalidValue

Declaration

public const float InvalidValue = 3.40282347E+38F

Field Value

Type	Description
Single

TrackOrder

if you enable this, then you can call GetOrder()

Declaration

public bool TrackOrder

Field Value

Type	Description
Boolean

Properties

MaxDistance

Get the maximum distance encountered during the Compute()

Declaration

public float MaxDistance { get; }

Property Value

Type	Description
Single

Methods

AddSeed(Int32, Single)

Add seed point as id/distance pair

Declaration

public void AddSeed(int id, float seed_dist)

Parameters

Type	Name	Description
Int32	id
Single	seed_dist

Compute()

Compute distances from seeds to all other ids.

Declaration

public void Compute()

Compute_Dense()

Declaration

protected void Compute_Dense()

Compute_Sparse()

Declaration

protected void Compute_Sparse()

ComputeToMaxDistance(Single)

Compute distances that are less/equal to fMaxDistance from the seeds Terminates early, so Queue may not be empty

Declaration

public void ComputeToMaxDistance(float fMaxDistance)

Parameters

Type	Name	Description
Single	fMaxDistance

ComputeToMaxDistance_Dense(Single)

Declaration

protected void ComputeToMaxDistance_Dense(float fMaxDistance)

Parameters

Type	Name	Description
Single	fMaxDistance

ComputeToMaxDistance_Sparse(Single)

Declaration

protected void ComputeToMaxDistance_Sparse(float fMaxDistance)

Parameters

Type	Name	Description
Single	fMaxDistance

ComputeToNode(Func<Int32, Boolean>, Single)

Compute distances until node_id is frozen, or (optional) max distance is reached Terminates early, so Queue may not be empty

Declaration

public int ComputeToNode(Func<int, bool> terminatingNodeF, float fMaxDistance = 3.40282347E+38F)

Parameters

Type	Name	Description
Func<Int32, Boolean>	terminatingNodeF
Single	fMaxDistance

Returns

Type	Description
Int32

ComputeToNode(Int32, Single)

Compute distances until node_id is frozen, or (optional) max distance is reached Terminates early, so Queue may not be empty [TODO] can reimplement this w/ internal call to ComputeToNode(func) ?

Declaration

public void ComputeToNode(int node_id, float fMaxDistance = 3.40282347E+38F)

Parameters

Type	Name	Description
Int32	node_id
Single	fMaxDistance

ComputeToNode_Dense(Func<Int32, Boolean>, Single)

Declaration

protected int ComputeToNode_Dense(Func<int, bool> terminatingNodeF, float fMaxDistance)

Parameters

Type	Name	Description
Func<Int32, Boolean>	terminatingNodeF
Single	fMaxDistance

Returns

Type	Description
Int32

ComputeToNode_Dense(Int32, Single)

Declaration

protected void ComputeToNode_Dense(int node_id, float fMaxDistance)

Parameters

Type	Name	Description
Int32	node_id
Single	fMaxDistance

ComputeToNode_Sparse(Func<Int32, Boolean>, Single)

Declaration

protected int ComputeToNode_Sparse(Func<int, bool> terminatingNodeF, float fMaxDistance)

Parameters

Type	Name	Description
Func<Int32, Boolean>	terminatingNodeF
Single	fMaxDistance

Returns

Type	Description
Int32

ComputeToNode_Sparse(Int32, Single)

Declaration

protected void ComputeToNode_Sparse(int node_id, float fMaxDistance)

Parameters

Type	Name	Description
Int32	node_id
Single	fMaxDistance

GetDistance(Int32)

Get the computed distance at node id. returns InvalidValue if node was not computed.

Declaration

public float GetDistance(int id)

Parameters

Type	Name	Description
Int32	id

Returns

Type	Description
Single

GetOrder()

Get (internal) list of frozen nodes in increasing distance-order. Requries that TrackOrder=true before Compute call.

Declaration

public List<int> GetOrder()

Returns

Type	Description
List<Int32>

GetPathToSeed(Int32, List<Int32>)

Walk from node fromv back to the (graph-)nearest seed point.

Declaration

public bool GetPathToSeed(int fromv, List<int> path)

Parameters

Type	Name	Description
Int32	fromv
List<Int32>	path

Returns

Type	Description
Boolean

IsSeed(Int32)

Declaration

public bool IsSeed(int id)

Parameters

Type	Name	Description
Int32	id

Returns

Type	Description
Boolean

MeshTriangles(DMesh3, Boolean)

shortcut to construct graph for mesh triangles

Declaration

public static DijkstraGraphDistance MeshTriangles(DMesh3 mesh, bool bSparse = false)

Parameters

Type	Name	Description
DMesh3	mesh
Boolean	bSparse

Returns

Type	Description
DijkstraGraphDistance

MeshVertices(DMesh3, Boolean)

shortcut to construct graph for mesh vertices

Declaration

public static DijkstraGraphDistance MeshVertices(DMesh3 mesh, bool bSparse = false)

Parameters

Type	Name	Description
DMesh3	mesh
Boolean	bSparse

Returns

Type	Description
DijkstraGraphDistance

Reset()

reset internal data structures/etc

Declaration

public void Reset()