Yog.FSharp
Getting Started Examples API Reference GitHub

Model Module

Namespace: Yog.Multi
Assembly: Yog.FSharp.dll

Multigraph data structure supporting parallel edges.

A multigraph allows multiple edges between the same pair of nodes, useful for modeling scenarios like: - Multi-modal transportation (different routes between cities) - Redundant network connections - Temporal graphs (same edge at different times) - Multiple relationship types (without using hypergraphs)

Comparison with Simple Graph

Aspect

MultiGraph

Graph

Parallel edges

Allowed

Combined/Not allowed

Edge identity

EdgeId per edge

No identity

Storage

Map

Nested maps

Use case

Multi-modal, redundant

Standard algorithms

Operations

  • addEdge: Creates new edge, returns EdgeId
  • toSimpleGraph: Collapse parallel edges using merge function
  • toSimpleGraphMinEdges: Keep minimum weight edge
  • toSimpleGraphSumEdges: Sum parallel edge weights

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 

open Yog.Multi

// Model multiple flights between cities
let multiGraph =
    Model.empty Directed
    |> Model.addNode 0 "NYC"
    |> Model.addNode 1 "LON"
    |> fun g ->
        let g1, _ = Model.addEdge 0 1 (Flight("BA112", 420)) g
        let g2, _ = Model.addEdge 0 1 (Flight("VS003", 400)) g1
        g2

// Collapse to simple graph with cheapest flight
let simple = Model.toSimpleGraphMinEdges compare multiGraph
namespace Yog
namespace Yog.Multi
val multiGraph: MultiGraph<string,System.IComparable>
module Model from Yog.Multi
<summary> Multigraph data structure supporting parallel edges. A multigraph allows multiple edges between the same pair of nodes, useful for modeling scenarios like: - Multi-modal transportation (different routes between cities) - Redundant network connections - Temporal graphs (same edge at different times) - Multiple relationship types (without using hypergraphs) ## Comparison with Simple Graph | Aspect | MultiGraph | Graph | |--------|-----------|-------| | Parallel edges | Allowed | Combined/Not allowed | | Edge identity | EdgeId per edge | No identity | | Storage | Map&lt;EdgeId, Edge&gt; | Nested maps | | Use case | Multi-modal, redundant | Standard algorithms | ## Operations - `addEdge`: Creates new edge, returns EdgeId - `toSimpleGraph`: Collapse parallel edges using merge function - `toSimpleGraphMinEdges`: Keep minimum weight edge - `toSimpleGraphSumEdges`: Sum parallel edge weights ## Example ```fsharp open Yog.Multi // Model multiple flights between cities let multiGraph = Model.empty Directed |&gt; Model.addNode 0 "NYC" |&gt; Model.addNode 1 "LON" |&gt; fun g -&gt; let g1, _ = Model.addEdge 0 1 (Flight("BA112", 420)) g let g2, _ = Model.addEdge 0 1 (Flight("VS003", 400)) g1 g2 // Collapse to simple graph with cheapest flight let simple = Model.toSimpleGraphMinEdges compare multiGraph ``` </summary>
val empty: kind: Yog.Model.GraphType -> MultiGraph<'n,'e> (requires equality and equality)
<summary> Creates an empty multigraph. ## Parameters - `kind`: Directed or Undirected ## Example ```fsharp let graph = Model.empty Directed ``` </summary>
val addNode: id: Yog.Model.NodeId -> data: 'n -> graph: MultiGraph<'n,'e> -> MultiGraph<'n,'e> (requires equality and equality)
<summary> Adds a node to the multigraph. ## Example ```fsharp let graph = Model.empty Directed |&gt; Model.addNode 0 "A" ``` </summary>
val g: MultiGraph<string,System.IComparable>
val g1: MultiGraph<string,System.IComparable>
val addEdge: src: Yog.Model.NodeId -> dst: Yog.Model.NodeId -> data: 'e -> graph: MultiGraph<'n,'e> -> MultiGraph<'n,'e> * EdgeId (requires equality and equality)
<summary> Adds an edge between two nodes. ## Returns Tuple of (updated graph, new EdgeId) ## Example ```fsharp let graph, edgeId = Model.addEdge 0 1 "weight" graph ``` </summary>
val g2: MultiGraph<string,System.IComparable>
val simple: Yog.Model.Graph<string,System.IComparable>
val toSimpleGraphMinEdges: compareFn: ('e -> 'e -> int) -> graph: MultiGraph<'n,'e> -> Yog.Model.Graph<'n,'e> (requires equality and equality)
<summary> Collapses the multigraph by keeping the minimum weight. ## Parameters - `compareFn`: Comparison function for edge weights </summary>
val compare: e1: 'T -> e2: 'T -> int (requires comparison)

Functions and values

Function or value Description

addEdge src dst data graph

Full Usage: addEdge src dst data graph

Parameters:
Returns: MultiGraph<'n, 'e> * EdgeId

Tuple of (updated graph, new EdgeId)

Adds an edge between two nodes.

Example

1: 

let graph, edgeId = Model.addEdge 0 1 "weight" graph
val graph: obj
val edgeId: obj

src : NodeId
dst : NodeId
data : 'e
graph : MultiGraph<'n, 'e>
Returns: MultiGraph<'n, 'e> * EdgeId

Tuple of (updated graph, new EdgeId)

addNode id data graph

Full Usage: addNode id data graph

Parameters:
Returns: MultiGraph<'n, 'e>

Adds a node to the multigraph.

Example

1: 

let graph = Model.empty Directed |> Model.addNode 0 "A"
val graph: obj

id : NodeId
data : 'n
graph : MultiGraph<'n, 'e>
Returns: MultiGraph<'n, 'e>

empty kind

Full Usage: empty kind

Parameters:
Returns: MultiGraph<'n, 'e>

Creates an empty multigraph.

Parameters

  • kind: Directed or Undirected

Example

1: 

let graph = Model.empty Directed
val graph: obj

kind : GraphType
Returns: MultiGraph<'n, 'e>

successors id graph

Full Usage: successors id graph

Parameters:
Returns: (NodeId * EdgeId * 'e) list

List of (target node, EdgeId, edge data)

Gets successors with their EdgeIds.
id : NodeId
graph : MultiGraph<'n, 'e>
Returns: (NodeId * EdgeId * 'e) list

List of (target node, EdgeId, edge data)

toSimpleGraph combineFn graph

Full Usage: toSimpleGraph combineFn graph

Parameters:
    combineFn : 'e -> 'e -> 'e
    graph : MultiGraph<'n, 'e>

Returns: Graph<'n, 'e>

A simple Graph with combined edges.

Collapses the multigraph into a simple Graph by combining parallel edges.

Parameters

  • combineFn: Function to merge edge weights when multiple edges exist
  • graph: The multigraph to collapse

Example

1: 
2: 
3: 
4: 
5: 

// Sum parallel edge weights
let simple = Model.toSimpleGraph (+) multiGraph

// Keep maximum weight
let simple = Model.toSimpleGraph max multiGraph
val simple: obj
val max: e1: 'T -> e2: 'T -> 'T (requires comparison)

combineFn : 'e -> 'e -> 'e
graph : MultiGraph<'n, 'e>
Returns: Graph<'n, 'e>

A simple Graph with combined edges.

toSimpleGraphMinEdges compareFn graph

Full Usage: toSimpleGraphMinEdges compareFn graph

Parameters:
    compareFn : 'e -> 'e -> int
    graph : MultiGraph<'n, 'e>

Returns: Graph<'n, 'e>

Collapses the multigraph by keeping the minimum weight.

Parameters

  • compareFn: Comparison function for edge weights

compareFn : 'e -> 'e -> int
graph : MultiGraph<'n, 'e>
Returns: Graph<'n, 'e>

toSimpleGraphSumEdges addFn graph

Full Usage: toSimpleGraphSumEdges addFn graph

Parameters:
    addFn : 'e -> 'e -> 'e
    graph : MultiGraph<'n, 'e>

Returns: Graph<'n, 'e>

Collapses the multigraph by summing weights.

Parameters

  • addFn: Addition function for edge weights

addFn : 'e -> 'e -> 'e
graph : MultiGraph<'n, 'e>
Returns: Graph<'n, 'e>