Shortest path between all the vertices using Dijkstra Algorithm on an FGraph.

Dijkstra algorithm, given by a brilliant Dutch computer scientist and software engineer Dr. Edsger Dijkstra in 1959. Dijkstra algorithm is a greedy algorithm that solves the single-source shortest path problem for a directed and undirected graph that has non-negative edge weight.

Let's start with a directed weighted graph. We will find shortest path between all the vertices using Dijkstra Algorithm.

open Graphoscope

let dwg =
    let nodes = [|0,"A";1,"B";2,"C";3,"D";4,"E";5,"F"|]
    let edges = [|0,1,7.;0,2,12.;1,2,2.;1,3,9.;2,4,10.;4,3,4.;3,5,1.;4,5,5.|]
    FGraph.create(nodes,edges)

Let´s have a look on the graph:

And now, let´s compute the shortest paths via Dijkstra :

let dij = Algorithms.Dijkstra.compute(0,dwg)

Shortest path between all the vertices using Dijkstra Algorithm on DiGraph.

Computation of the shortest paths is also available using the DiGraph structure. Lets compare them using the same graph as above:

let dwgDiGraph =
    let nodes = [|0;1;2;3;4;5|]|>Array.map(fun x -> x,x)
    let edges = [|0,1,7.;0,2,12.;1,2,2.;1,3,9.;2,4,10.;4,3,4.;3,5,1.;4,5,5.|]
    DiGraph.createFromNodes nodes
    |> DiGraph.addEdges edges
    

let dijDiGraph = Algorithms.Dijkstra.compute(0,id,dwgDiGraph)
namespace Graphoscope
val dwg: FGraph<int,string,float>
val nodes: (int * string)[]
val edges: (int * int * float)[]
Multiple items
module FGraph from Graphoscope

--------------------
type FGraph = new: unit -> FGraph static member addEdge: nk1: 'NodeKey -> nk2: 'NodeKey -> ed: 'EdgeData -> g: FGraph<'NodeKey,'NodeData,'EdgeData> -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addEdges: edgeSeq: seq<'NodeKey * 'NodeKey * 'EdgeData> -> g: FGraph<'NodeKey,'NodeData,'EdgeData> -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addElement: nk1: 'NodeKey -> nd1: 'NodeData -> nk2: 'NodeKey -> nd2: 'NodeData -> ed: 'EdgeData -> g: FGraph<'NodeKey,'NodeData,'EdgeData> -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addNode: nk: 'NodeKey -> nd: 'NodeData -> g: FGraph<'NodeKey,'NodeData,'EdgeData> -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addNodes: nodeSeq: seq<'NodeKey * 'NodeData> -> g: FGraph<'NodeKey,'NodeData,'EdgeData> -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member clone: graph: FGraph<'NodeKey,'NodeData,'EdgeData> -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member containsEdge: v1: 'NodeKey -> v2: 'NodeKey -> g: FGraph<'NodeKey,'NodeData,'EdgeData> -> bool (requires comparison) static member containsNode: vk: 'NodeKey -> g: FGraph<'NodeKey,'NodeData,'EdgeData> -> bool (requires comparison) static member countEdges: g: FGraph<'NodeKey,'NodeData,'EdgeData> -> int (requires comparison) ...

--------------------
type FGraph<'NodeKey,'NodeData,'EdgeData (requires comparison)> = System.Collections.Generic.Dictionary<'NodeKey,FContext<'NodeKey,'NodeData,'EdgeData>>

--------------------
new: unit -> FGraph
static member FGraph.create: unit -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member FGraph.create: nodes: seq<'NodeKey * 'NodeData> * edges: seq<'NodeKey * 'NodeKey * 'EdgeData> -> FGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
namespace Cytoscape
namespace Cytoscape.NET
val vizGraph: CyGraph.CyGraph
module CyGraph from Cytoscape.NET
val initEmpty: unit -> CyGraph.CyGraph
val withElements: elems: seq<CytoscapeModel.Element> -> cy: CyGraph.CyGraph -> CyGraph.CyGraph
val sk: int
val s: string
val tk: int
val t: string
val el: float
static member FGraph.toSeq: graph: FGraph<'NodeKey,'NodeData,'EdgeData> -> seq<'NodeKey * 'NodeData * 'NodeKey * 'NodeData * 'EdgeData> (requires comparison)
val sk: string
val tk: string
Multiple items
val string: value: 'T -> string
<summary>Converts the argument to a string using <c>ToString</c>.</summary>
<remarks>For standard integer and floating point values the and any type that implements <c>IFormattable</c><c>ToString</c> conversion uses <c>CultureInfo.InvariantCulture</c>. </remarks>
<param name="value">The input value.</param>
<returns>The converted string.</returns>
<example id="string-example"><code lang="fsharp"></code></example>


--------------------
type string = System.String
<summary>An abbreviation for the CLI type <see cref="T:System.String" />.</summary>
<category>Basic Types</category>
module Elements from Cytoscape.NET
val node: id: string -> dataAttributes: CyParam.CyStyleParam list -> Elements.Node
module CyParam from Cytoscape.NET
val label: v: 'a -> CyParam.CyStyleParam
val edge: id: string -> sourceId: string -> targetId: string -> dataAttributes: CyParam.CyStyleParam list -> Elements.Edge
val sprintf: format: Printf.StringFormat<'T> -> 'T
<summary>Print to a string using the given format.</summary>
<param name="format">The formatter.</param>
<returns>The formatted result.</returns>
<example>See <c>Printf.sprintf</c> (link: <see cref="M:Microsoft.FSharp.Core.PrintfModule.PrintFormatToStringThen``1" />) for examples.</example>
val withStyle: selector: string -> cyStyles: seq<CyParam.CyStyleParam> -> cy: CyGraph.CyGraph -> CyGraph.CyGraph
val content: v: 'a -> CyParam.CyStyleParam
val color: v: 'a -> CyParam.CyStyleParam
module Curve from Cytoscape.NET.CyParam
val style: v: 'a -> CyParam.CyStyleParam
module Target from Cytoscape.NET.CyParam
module Arrow from Cytoscape.NET.CyParam.Target
val shape: v: 'a -> CyParam.CyStyleParam
module Source from Cytoscape.NET.CyParam
module Arrow from Cytoscape.NET.CyParam.Source
val withZoom: zoom: CytoscapeModel.Zoom -> cy: CyGraph.CyGraph -> CyGraph.CyGraph
namespace Cytoscape.NET.CytoscapeModel
Multiple items
type Zoom = inherit DynamicObj new: unit -> Zoom static member Init: ?Level: float * ?Position: (int * int) * ?RenderedPosition: (int * int) * ?ZoomingEnabled: bool -> Zoom static member Update: ?Level: float * ?Position: (int * int) * ?RenderedPosition: (int * int) * ?ZoomingEnabled: bool -> (Zoom -> Zoom)

--------------------
new: unit -> CytoscapeModel.Zoom
static member CytoscapeModel.Zoom.Init: ?Level: float * ?Position: (int * int) * ?RenderedPosition: (int * int) * ?ZoomingEnabled: bool -> CytoscapeModel.Zoom
val withLayout: ly: Layout -> cy: CyGraph.CyGraph -> CyGraph.CyGraph
Multiple items
module Layout from Cytoscape.NET

--------------------
type Layout = inherit DynamicObj new: name: string -> Layout member name: string
<summary> Layout type inherits from dynamic object </summary>

--------------------
new: name: string -> Layout
val initCose: applyOption: (Layout -> Layout) -> Layout
<summary> initializes a layout of type "cose" applying the givin layout option function. The cose (Compound Spring Embedder) layout uses a physics simulation to lay out graphs. </summary>
Multiple items
type LayoutOptions = new: unit -> LayoutOptions static member Cose: ?Refresh: int * ?BoundingBox: 'a * ?NodeDimensionsIncludeLabels: bool * ?Randomize: bool * ?ComponentSpacing: int * ?NodeRepulsion: 'b * ?NodeOverlap: int * ?IdealEdgeLength: 'c * ?EdgeElasticity: 'd * ?NestingFactor: float * ?Gravity: int * ?NumIter: int * ?InitialTemp: int * ?CoolingFactor: float * ?MinTemp: float -> ('L -> 'L) (requires 'L :> Layout) static member Generic: ?Positions: 'a0 * ?Zoom: 'a1 * ?Pan: 'a2 * ?Fit: bool * ?Padding: int * ?Animate: bool * ?AnimationDuration: int * ?AnimationEasing: 'a3 * ?AnimateFilter: 'a4 * ?AnimationThreshold: int * ?Ready: 'a5 * ?Stop: 'a6 * ?Transform: 'a7 -> ('L -> 'L) (requires 'L :> Layout)
<summary> Functions provide the options of the Layout objects </summary>

--------------------
new: unit -> Layout.LayoutOptions
static member Layout.LayoutOptions.Cose: ?Refresh: int * ?BoundingBox: 'a * ?NodeDimensionsIncludeLabels: bool * ?Randomize: bool * ?ComponentSpacing: int * ?NodeRepulsion: 'b * ?NodeOverlap: int * ?IdealEdgeLength: 'c * ?EdgeElasticity: 'd * ?NestingFactor: float * ?Gravity: int * ?NumIter: int * ?InitialTemp: int * ?CoolingFactor: float * ?MinTemp: float -> ('L -> 'L) (requires 'L :> Layout)
val withSize: width: int * height: int -> cy: CyGraph.CyGraph -> CyGraph.CyGraph
type HTML = static member CreateGraphHTML: graphData: string * zooming: string * divId: string * cytoscapeReference: CytoscapeJSReference * ?Width: int * ?Height: int -> XmlNode list static member CreateGraphScript: graphData: string * zooming: string * cytoscapeReference: CytoscapeJSReference -> XmlNode static member Doc: graphHTML: XmlNode list * cytoscapeReference: CytoscapeJSReference * ?AdditionalHeadTags: XmlNode list -> XmlNode static member show: cy: Cytoscape * ?DisplayOpts: DisplayOptions -> unit static member toEmbeddedHTML: ?DisplayOpts: DisplayOptions -> (Cytoscape -> string) static member toGraphHTML: ?DisplayOpts: DisplayOptions -> (Cytoscape -> string) static member toGraphHTMLNodes: ?DisplayOpts: DisplayOptions -> (Cytoscape -> XmlNode list)
<summary> HTML template for Cytoscape </summary>
static member HTML.toGraphHTML: ?DisplayOpts: DisplayOptions -> (CytoscapeModel.Cytoscape -> string)
val dij: System.Collections.Generic.Dictionary<int,float>
namespace Graphoscope.Algorithms
Multiple items
type Dijkstra = new: unit -> Dijkstra static member compute: starting: 'NodeKey * graph: FGraph<'NodeKey,'NodeData,'EdgeData> -> Dictionary<'NodeKey,float> (requires comparison) + 2 overloads static member computeBetween: origin: 'NodeKey * destination: 'NodeKey * graph: FGraph<'NodeKey,'NodeData,float> -> 'a2 (requires comparison) + 1 overload static member computeWithEdgeData: starting: 'NodeKey * graph: FGraph<'NodeKey,'NodeData,float> -> Dictionary<'NodeKey,float> (requires comparison) + 1 overload static member computeWithEdgeDataBy: starting: 'NodeKey * getEdgeWeight: ('EdgeData -> float) * graph: FGraph<'NodeKey,'NodeData,'EdgeData> -> Dictionary<'NodeKey,float> (requires comparison) + 1 overload static member ofAdjGraph: starting: 'NodeKey -> getEdgeWeight: ('EdgeData -> float) -> graph: AdjGraph<'NodeKey,'NodeData,'EdgeData> -> Dictionary<'NodeKey,float> (requires comparison and comparison and comparison) static member ofDiGraph: source: 'NodeKey -> getEdgeWeight: ('EdgeData -> float) -> graph: DiGraph<'NodeKey,'a2,'EdgeData> -> ('NodeKey * float)[] (requires comparison) static member ofDiGraphAllPairs: getEdgeWeight: ('EdgeData -> float) -> graph: DiGraph<'NodeKey,'a2,'EdgeData> -> 'NodeKey[] * float[][] (requires comparison) static member ofDiGraphAllPairsWithPath: getEdgeWeight: ('EdgeData -> float) -> graph: DiGraph<'NodeKey,'a2,'EdgeData> -> ('NodeKey * 'NodeKey * float * 'NodeKey[] option)[][] (requires comparison) static member ofDiGraphBetween: getEdgeWeight: ('EdgeData -> float) -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> origin: 'NodeKey -> destination: 'NodeKey -> float option (requires comparison) ...
<summary> Computes Dijkstra's shortest path </summary>

--------------------
new: unit -> Algorithms.Dijkstra
static member Algorithms.Dijkstra.compute: starting: 'NodeKey * graph: AdjGraph<'NodeKey,'NodeData,'EdgeData> -> System.Collections.Generic.Dictionary<'NodeKey,float> (requires comparison and comparison and comparison)
static member Algorithms.Dijkstra.compute: starting: 'NodeKey * graph: FGraph<'NodeKey,'NodeData,'EdgeData> -> System.Collections.Generic.Dictionary<'NodeKey,float> (requires comparison)
static member Algorithms.Dijkstra.compute: starting: 'NodeKey * getEdgeWeight: ('EdgeData -> float) * graph: DiGraph<'NodeKey,'a,'EdgeData> -> ('NodeKey * float)[] (requires comparison)
val dwgDiGraph: DiGraph<int,int,float>
val nodes: (int * int)[]
module Array from Microsoft.FSharp.Collections
<summary>Contains operations for working with arrays.</summary>
<remarks> See also <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/arrays">F# Language Guide - Arrays</a>. </remarks>
val map: mapping: ('T -> 'U) -> array: 'T[] -> 'U[]
<summary>Builds a new array whose elements are the results of applying the given function to each of the elements of the array.</summary>
<param name="mapping">The function to transform elements of the array.</param>
<param name="array">The input array.</param>
<returns>The array of transformed elements.</returns>
<exception cref="T:System.ArgumentNullException">Thrown when the input array is null.</exception>
<example id="map-1"><code lang="fsharp"> let inputs = [| "a"; "bbb"; "cc" |] inputs |&gt; Array.map (fun x -&gt; x.Length) </code> Evaluates to <c>[| 1; 3; 2 |]</c></example>
val x: int
Multiple items
module DiGraph from Graphoscope

--------------------
type DiGraph = new: unit -> DiGraph static member addEdge: edge: ('NodeKey * 'NodeKey * 'EdgeData) -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addEdges: edges: ('NodeKey * 'NodeKey * 'EdgeData)[] -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addElement: nk1: 'NodeKey -> nd1: 'NodeData -> nk2: 'NodeKey -> nd2: 'NodeData -> ed: 'EdgeData -> g: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addNode: nodeKey: 'NodeKey -> nodeData: 'NodeData -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member addNodes: nodes: ('NodeKey * 'NodeData)[] -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) static member countEdges: graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> int (requires comparison) static member countNodes: graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> int (requires comparison) static member createFromEdges: edges: ('NodeKey * 'NodeKey * 'EdgeData)[] -> DiGraph<'NodeKey,'NodeKey,'EdgeData> (requires comparison) static member createFromNodes: nodes: ('NodeKey * 'NodeData)[] -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison) ...

--------------------
type DiGraph<'NodeKey,'NodeData,'EdgeData (requires comparison)> = new: unit -> DiGraph<'NodeKey,'NodeData,'EdgeData>

--------------------
new: unit -> DiGraph

--------------------
new: unit -> DiGraph<'NodeKey,'NodeData,'EdgeData>
static member DiGraph.createFromNodes: nodes: ('NodeKey * 'NodeData)[] -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member DiGraph.addEdges: edges: ('NodeKey * 'NodeKey * 'EdgeData)[] -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
val dijDiGraph: (int * float)[]
val id: x: 'T -> 'T
<summary>The identity function</summary>
<param name="x">The input value.</param>
<returns>The same value.</returns>
<example id="id-example"><code lang="fsharp"> id 12 // Evaulates to 12 id "abc" // Evaulates to "abc" </code></example>