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)
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 |> Array.map (fun x -> 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>