Yog.FSharp
Getting Started Examples API Reference GitHub

Model Module

Namespace: Yog
Assembly: Yog.FSharp.dll

Core graph data structures and basic operations for the yog library.

This module defines the fundamental Graph type and provides all basic operations for creating and manipulating graphs. The graph uses an adjacency list representation with dual indexing (both outgoing and incoming edges) for efficient traversal in both directions.

Types

Type Description

Graph<'nodeData, 'edgeData>

A simple graph data structure that can be directed or undirected. - 'nodeData: The type of data stored at each node - 'edgeData: The type of data (usually weight) stored on each edge

GraphType

The type of graph: directed or undirected.

NodeId

Unique identifier for a node in the graph.

Functions and values

Function or value Description

addEdge src dst weight graph

Full Usage: addEdge src dst weight graph

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

Adds an edge to the graph with the given weight.

For directed graphs, adds a single edge from src to dst. For undirected graphs, adds edges in both directions.

Example

1: 
2: 

graph
|> addEdge 1 2 10

Note: If src or dst have not been added via addNode, an ArgumentException is thrown. To automatically create missing endpoints when adding an edge, use addEdgeEnsured or addEdgeEnsuredWith.

Parameters

  • src: The source node ID.
  • dst: The destination node ID.
  • weight: The weight of the edge.
  • graph: The graph to add the edge to. ## Returns A new graph with the edge added.

src : NodeId
dst : NodeId
weight : 'e
graph : Graph<'n, 'e>
Returns: Graph<'n, 'e>

addEdgeEnsured src dst weight srcDefault dstDefault graph

Full Usage: addEdgeEnsured src dst weight srcDefault dstDefault graph

Parameters:
    src : NodeId
    dst : NodeId
    weight : 'e
    srcDefault : 'n
    dstDefault : 'n
    graph : Graph<'n, 'e>

Returns: Graph<'n, 'e>

Like addEdge, but ensures both endpoint nodes exist first.

If src or dst is not already in the graph, it is created with the supplied default data before the edge is added. Nodes that already exist are left unchanged.

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

// Nodes 1 and 2 are created automatically with data "unknown"
empty Directed
|> addEdgeEnsured 1 2 10 "unknown" "unknown"

// Existing nodes keep their data; only missing ones get the default
empty Directed
|> addNode 1 "Alice"
|> addEdgeEnsured 1 2 5 "anon" "anon"
// Node 1 is still "Alice", node 2 is "anon"

Parameters

  • src: The source node ID.
  • dst: The destination node ID.
  • weight: The weight of the edge.
  • srcDefault: The default data for the source node if it doesn't exist.
  • dstDefault: The default data for the destination node if it doesn't exist.
  • graph: The graph to add the edge to. ## Returns A new graph with the edge added and endpoints ensured.

src : NodeId
dst : NodeId
weight : 'e
srcDefault : 'n
dstDefault : 'n
graph : Graph<'n, 'e>
Returns: Graph<'n, 'e>

addEdgeEnsuredWith src dst weight createDefault graph

Full Usage: addEdgeEnsuredWith src dst weight createDefault graph

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

Like addEdge, but ensures both endpoint nodes exist first by generating default data via a callback.

Parameters

  • src: The source node ID.
  • dst: The destination node ID.
  • weight: The weight of the edge.
  • createDefault: A callback that takes a NodeId and returns the default data for that node.
  • graph: The graph to add the edge to. ## Returns A new graph with the edge added and endpoints ensured.

src : NodeId
dst : NodeId
weight : 'e
createDefault : NodeId -> 'n
graph : Graph<'n, 'e>
Returns: Graph<'n, 'e>

addEdgeWithCombine src dst weight combine graph

Full Usage: addEdgeWithCombine src dst weight combine graph

Parameters:
    src : NodeId
    dst : NodeId
    weight : 'e
    combine : 'e -> 'e -> 'e
    graph : Graph<'n, 'e>

Returns: Graph<'n, 'e>

Adds an edge, but if an edge already exists between src and dst, it combines the new weight with the existing one using combine.

The combine function receives (existingWeight, newWeight) and should return the combined weight.

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 

let graph =
  empty Directed
  |> addNode 1 "A"
  |> addNode 2 "B"
  |> addEdge 1 2 10
  |> addEdgeWithCombine 1 2 5 (+)
// Edge 1->2 now has weight 15 (10 + 5)

Time Complexity: O(1)

Use Cases

  • **Edge contraction** in graph algorithms (Stoer-Wagner min-cut)
  • **Multi-graph support** (adding parallel edges with combined weights)
  • **Incremental graph building** (accumulating weights from multiple sources)

Parameters

  • src: The source node ID.
  • dst: The destination node ID.
  • weight: The weight of the edge.
  • combine: A function to combine existing and new weights.
  • graph: The graph to add the edge to. ## Returns A new graph with the edge added or weights combined.
val graph: obj

src : NodeId
dst : NodeId
weight : 'e
combine : 'e -> 'e -> 'e
graph : Graph<'n, 'e>
Returns: Graph<'n, 'e>

addNode id data graph

Full Usage: addNode id data graph

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

Adds a node to the graph with the given ID and data. If a node with this ID already exists, its data will be replaced.

Example

1: 
2: 
3: 

graph
|> addNode 1 "Node A"
|> addNode 2 "Node B"

Parameters

  • id: The unique identifier for the node.
  • data: The data to store at the node.
  • graph: The graph to add the node to. ## Returns A new graph with the node added.

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

allNodes graph

Full Usage: allNodes graph

Parameters:
Returns: NodeId list

Returns all node IDs in the graph. This includes all nodes, even isolated nodes with no edges.

Parameters

  • graph: The graph. ## Returns A list of all node IDs.

graph : Graph<'n, 'e>
Returns: NodeId list

edgeCount graph

Full Usage: edgeCount graph

Parameters:
Returns: int

Returns the number of edges in the graph.

For undirected graphs, each edge is counted once (the pair {u, v}). For directed graphs, each directed edge (u -> v) is counted once. Time Complexity: O(V)

Parameters

  • graph: The graph. ## Returns The number of edges.

graph : Graph<'n, 'e>
Returns: int

empty graphType

Full Usage: empty graphType

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

Creates a new empty graph of the specified type.

Example

1: 

let graph = Model.empty Directed

Parameters

  • graphType: The type of the graph. ## Returns A new empty graph.
val graph: obj

graphType : GraphType
Returns: Graph<'n, 'e>

neighbors id graph

Full Usage: neighbors id graph

Parameters:
Returns: (NodeId * 'e) list

Gets everyone connected to the node, regardless of direction.

For undirected graphs, this is equivalent to successors. For directed graphs, this combines both outgoing and incoming edges without duplicates.

Parameters

  • id: The node ID to get neighbors for.
  • graph: The graph. ## Returns A list of connected node IDs and edge weights.

id : NodeId
graph : Graph<'n, 'e>
Returns: (NodeId * 'e) list

nodeCount

Full Usage: nodeCount

Returns: Graph<'a, 'b> -> int

Returns the number of nodes in the graph. Equivalent to order. Time Complexity: O(1)
Returns: Graph<'a, 'b> -> int

order graph

Full Usage: order graph

Parameters:
Returns: int

Returns the number of nodes in the graph (graph order). Time Complexity: O(1)

Parameters

  • graph: The graph. ## Returns The number of nodes.

graph : Graph<'n, 'e>
Returns: int

predecessorIds node graph

Full Usage: predecessorIds node graph

Parameters:
Returns: NodeId list

Returns just the NodeIds of predecessors (without edge weights).

Parameters

  • node: The node ID to get predecessors for.
  • graph: The graph. ## Returns A list of predecessor node IDs.

node : NodeId
graph : Graph<'n, 'e>
Returns: NodeId list

predecessors id graph

Full Usage: predecessors id graph

Parameters:
Returns: (NodeId * 'e) list

Gets nodes you came FROM (Predecessors).

Parameters

  • id: The node ID to get predecessors for.
  • graph: The graph. ## Returns A list of predecessor node IDs and edge weights.

id : NodeId
graph : Graph<'n, 'e>
Returns: (NodeId * 'e) list

removeEdge src dst graph

Full Usage: removeEdge src dst graph

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

Removes an edge from src to dst. For undirected graphs, removes edges in both directions.

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 

// Directed graph - removes single directed edge
let graph =
  empty Directed
  |> addNode 1 "A"
  |> addNode 2 "B"
  |> addEdge 1 2 10
  |> removeEdge 1 2
// Edge 1->2 is removed

Time Complexity: O(1)

Parameters

  • src: The source node ID.
  • dst: The destination node ID.
  • graph: The graph to remove the edge from. ## Returns A new graph with the edge removed.
val graph: obj

src : NodeId
dst : NodeId
graph : Graph<'n, 'e>
Returns: Graph<'n, 'e>

removeNode id graph

Full Usage: removeNode id graph

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

Removes a node and all its connected edges (incoming and outgoing).

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 

let graph =
  empty Directed
  |> addNode 1 "A"
  |> addNode 2 "B"
  |> addNode 3 "C"
  |> addEdge 1 2 10
  |> addEdge 2 3 20

let graph = removeNode 2 graph
// Node 2 is removed, along with edges 1->2 and 2->3

Time Complexity: O(deg(v)) - proportional to the number of edges connected to the node, not the whole graph.

Parameters

  • id: The ID of the node to remove.
  • graph: The graph to remove the node from. ## Returns A new graph with the node and its connections removed.
val graph: obj

id : NodeId
graph : Graph<'n, 'e>
Returns: Graph<'n, 'e>

successorIds id graph

Full Usage: successorIds id graph

Parameters:
Returns: NodeId list

Returns just the NodeIds of successors (without edge weights). Convenient for traversal algorithms that only need the IDs.

Parameters

  • id: The node ID to get successors for.
  • graph: The graph. ## Returns A list of successor node IDs.

id : NodeId
graph : Graph<'n, 'e>
Returns: NodeId list

successors id graph

Full Usage: successors id graph

Parameters:
Returns: (NodeId * 'e) list

Gets nodes you can travel TO (Successors).

Parameters

  • id: The node ID to get successors for.
  • graph: The graph. ## Returns A list of successor node IDs and edge weights.

id : NodeId
graph : Graph<'n, 'e>
Returns: (NodeId * 'e) list