Welcome! SimpleGraph is a small, easy-to-learn functional library for working with undirected graphs (simple graph) in F#. It’s designed for introductory programming students: the API is minimal, every operation is pure, and the types are friendly.
- A simple graph is stored as an adjacency map:
Map<'T, Set<'T>>. - Vertices can be any comparable type (
'T : comparison) likeint,string, or a record with comparable fields. - The graph is undirected: adding
(u, v)is equivalent to adding(v, u). - Self-loops (edges from a vertex to itself) are ignored.
- All operations return a new graph (the original is unchanged).
You have three simple options:
Copy the library source into your solution (e.g., Library.fs / Library.fsi) and add it to your project. Be sure it compiles before files that use it.
In an .fsx script, reference the compiled assembly or include the .fs directly:
#load "Library.fs" // if the file is in the same folder
open FSharp.simpleGraphNamespace:
FSharpModule:simpleGraph
Add it to your project file with
dotnet add package DIKU.Graph --version 1.0.0
or use it in F# interactive mode by adding
#r "nuget: DIKU.Graph, 1.0.0"in the top of your script.
open simpleGraph
// 1) Start from the empty graph
let g0 : Graph<string> = empty
// 2) Add vertices (idempotent: adding twice is fine)
let g1 =
g0
|> addVertex "A"
|> addVertex "B"
|> addVertex "C"
// 3) Add edges (undirected, self-loops ignored)
let g2 =
g1
|> addEdge "A" "B"
|> addEdge "B" "C"
// 4) Query
let vs = vertices g2 // Set<string> = set ["A"; "B"; "C"]
let es = edges g2 // Set<string * string> = set [("A","B"); ("B","C")]
let nbsB = neighbors "B" g2 // set ["A"; "C"]
let degB = degree "B" g2 // 2
let has = hasEdge "A" "C" g2 // false
// 5) Remove
let g3 = removeEdge "B" "C" g2
let g4 = removeVertex "A" g3
// 6) Build from an edge list
let g5 =
ofEdges [ "A","B"; "B","C"; "C","D"; "D","A" ] // square
// 7) Depth-first search & connectivity
let order = dfs "A" g5 // e.g., ["A"; "B"; "C"; "D"]
let comps = connectedComponents g5 // e.g., [["A";"B";"C";"D"]]
let ok = isConnected g5 // trueAll functions live in the simpleGraph module.
| Value / Function | Type (simplified) | What it is / does |
|---|---|---|
Graph<'T> |
Map<'T, Set<'T>> |
Graph type (adjacency sets). |
empty |
Graph<'T> |
The empty graph (no vertices, no edges). |
addVertex |
'T -> Graph<'T> -> Graph<'T> |
Add a vertex (no effect if it already exists). |
removeVertex |
'T -> Graph<'T> -> Graph<'T> |
Remove a vertex and all incident edges. |
addEdge |
'T -> 'T -> Graph<'T> -> Graph<'T> |
Add an edge (u,v) (self-loops ignored). |
removeEdge |
'T -> 'T -> Graph<'T> -> Graph<'T> |
Remove the edge (u,v) if present. |
vertices |
Graph<'T> -> Set<'T> |
All vertices. |
edges |
Graph<'T> -> Set<'T * 'T> |
All edges (u,v) with u <= v. |
neighbors |
'T -> Graph<'T> -> Set<'T> |
The neighbor set of a vertex. |
degree |
'T -> Graph<'T> -> int |
The number of neighbors of a vertex. |
hasVertex |
'T -> Graph<'T> -> bool |
Whether a vertex exists. |
hasEdge |
'T -> 'T -> Graph<'T> -> bool |
Whether an edge exists. |
ofEdges |
('T * 'T) list -> Graph<'T> |
Build a graph from a list of undirected edges. |
dfs |
'T -> Graph<'T> -> 'T list |
Depth-first search visit order from a start vertex. |
connectedComponents |
Graph<'T> -> 'T list list |
Each component as a vertex list. |
isConnected |
Graph<'T> -> bool |
True if the graph is non-empty and has one component. |
All functions require 'T : comparison since they are implemented with the Set/Map Collection data types.
let tri =
empty
|> addEdge 1 2
|> addEdge 2 3
|> addEdge 1 3
printfn "%A" (vertices tri) // set [1; 2; 3]
printfn "%A" (edges tri) // set [(1,2); (1,3); (2,3)]
printfn "%b" (isConnected tri) // truelet two =
ofEdges [ "A","B"; "B","C"; "X","Y" ]
connectedComponents two
// [ ["A"; "B"; "C"]; ["X"; "Y"] ] (order may vary)let g =
ofEdges [ 1,2; 2,3; 2,4; 4,5; 3,6 ]
dfs 1 g
// A plausible order: [1;2;3;6;4;5] (depends on Set ordering)- The graph is a
Mapfrom vertex to aSetof neighbors. MapandSetare balanced trees—lookups/updates are O(log n) (good enough for learning and small graphs).- Because the data is immutable, every change returns a new graph. Under the hood, F# shares structure efficiently, so copying is not as expensive as it sounds.