graph

Here’s a handy index you can use to browse through the various graph functions.

operation kind	functions
creating graphs	`new`
turning graphs into lists	`nodes`
querying a graph	`size`, `has_node`, `has_edge`, `get_context`, `match`
adding/removing elements from a graph	`insert_node`, `insert_directed_edge`, `insert_undirected_edge`, `remove_node`, `remove_directed_edge`, `remove_undirected_edge`
transforming graphs	`fold`, `reverse`, `map_contexts`, `map_values`, `map_labels`, `reverse_edges`, `to_directed`

Types

Context

</>

The context associated with a node in a graph: it contains the node itself and all the incoming and outgoing edges. Edges are stored in a dict going from neighbour’s id to the edge label.

pub type Context(value, label) {
  Context(
    incoming: Dict(Int, label),
    node: Node(value),
    outgoing: Dict(Int, label),
  )
}

Constructors

Context(
  incoming: Dict(Int, label),
  node: Node(value),
  outgoing: Dict(Int, label),
)

Directed

</>

The direction of a directed graph.

pub type Directed

Graph

opaque </>

A directed or undirected graph. A graph is made up of nodes and edges connecting them: each node holds a value and each edge has a label.

The graph also carries along its direction (either Directed or Undirected) in its type so that it’s impossible to mix up Directed and Undirected graphs inadvertently.

pub opaque type Graph(direction, value, label)

Undirected

</>

The direction of an undirected graph.

pub type Undirected

Functions

fold

</>

pub fn fold(
  over graph: Graph(a, b, c),
  from initial: d,
  with fun: fn(d, Context(b, c)) -> d,
) -> d

Reduces the given graph into a single value by applying function to all its contexts, one after the other.

🚨 Graph’s contexts are not sorted in any way so your folding function should never rely on any accidental order the contexts might have.

Examples

// The size function could be implemented using a fold.
// The real implementation is more efficient because it doesn't have to
// traverse all contexts!
pub fn size(graph) {
  fold(
    over: graph,
    from: 0,
    with: fn(size, _context) { size + 1 },
  )
}

get_context

</>

pub fn get_context(
  graph: Graph(a, b, c),
  of node: Int,
) -> Result(Context(b, c), Nil)

Returns the context associated with the node with the given id, if present. Otherwise returns Error(Nil).

Examples

new() |> get(1)
// -> Error(Nil)

new() |> insert_node(Node(1, "a node")) |> get_context(of: 1)
// -> Ok(Context(node: Node(1, "a node"), ..))

has_edge

</>

pub fn has_edge(
  graph: Graph(a, b, c),
  from source: Int,
  to destination: Int,
) -> Bool

Returns True if the graph has an edge connecting the two nodes with the given ids.

Examples

let my_graph =
  new()
  |> insert_node(Node(1, "a node"))
  |> insert_node(Node(2, "other node"))
  |> insert_directed_edge("edge label", from: 1, to: 2)

my_graph |> has_edge(from: 1, to: 2)
// -> True

my_graph |> has_edge(from: 2, to: 1)
// -> False

has_node

</>

pub fn has_node(graph: Graph(a, b, c), node_id: Int) -> Bool

Returns True if the graph contains a node with the given id.

Examples

let my_graph = new() |> insert_node(Node(1, "a node"))

my_graph |> has_node(1)
// -> True

my_graph |> has_node(2)
// -> False

insert_directed_edge

</>

pub fn insert_directed_edge(
  graph: Graph(Directed, a, b),
  labelled label: b,
  from source: Int,
  to destination: Int,
) -> Graph(Directed, a, b)

Adds an edge connecting two nodes in a directed graph.

let my_graph =
  new()
  |> insert_node(Node(1, "a node"))
  |> insert_node(Node(2, "other node"))
  |> insert_directed_edge("edge label", from: 1, to: 2)

my_graph |> has_edge(from: 1, to: 2)
// -> True

my_graph |> has_edge(from: 2, to: 1)
// -> False

insert_node

</>

pub fn insert_node(
  graph: Graph(a, b, c),
  node: Node(b),
) -> Graph(a, b, c)

Adds a node to the given graph. If the graph already contains a node with the same id, that will be replaced by the new one. The newly added node won’t be connected to any existing node.

Examples

new() |> insert_node(Node(1, "a node")) |> nodes
// -> [Node(1, "a node")]

insert_undirected_edge

</>

pub fn insert_undirected_edge(
  graph: Graph(Undirected, a, b),
  labelled label: b,
  between one: Int,
  and other: Int,
) -> Graph(Undirected, a, b)

Adds an edge connecting two nodes in an undirected graph.

Examples

let my_graph =
  new()
  |> insert_node(Node(1, "a node"))
  |> insert_node(Node(2, "other node"))
  |> insert_undirected_edge("edge label", between: 1, and: 2)

my_graph |> has_edge(from: 1, to: 2)
// -> True

my_graph |> has_edge(from: 2, to: 1)
// -> True

map_contexts

</>

pub fn map_contexts(
  in graph: Graph(a, b, c),
  with fun: fn(Context(b, c)) -> Context(b, c),
) -> Graph(Directed, b, c)

Transform the contexts associated with each node.

This function can add and remove arbitrary edges from the graph by updating the incoming and outgoing edges of a context. So we can’t assume the final graph will still be Undirected, that’s why it is always treated as a Directed one.

Examples

// The reverse function can be implemented with `map_contexts`
pub fn reverse(graph) {
  map_contexts(in: graph, with: fn(context) {
    Context(
      ..context,
      incoming: context.outgoing,
      outgoing: context.incoming,
    )
  })
}

map_labels

</>

pub fn map_labels(
  in graph: Graph(a, b, c),
  with fun: fn(c) -> d,
) -> Graph(a, b, d)

Transforms the labels of all the graph’s edges using the given function.

Examples

new()
|> insert_node(Node(1, "a node"))
|> insert_undirected_edge(UndirectedEdge(1, 1, "label"))
|> map_labels(fn(label) { label <> "!" })
|> labels
// -> ["label!"]

map_values

</>

pub fn map_values(
  in graph: Graph(a, b, c),
  with fun: fn(b) -> d,
) -> Graph(a, d, c)

Transforms the values of all the graph’s nodes using the given function.

Examples

new()
|> insert_node(Node(1, "a node"))
|> map_nodes(fn(value) { value <> "!" })
|> nodes
// -> [Node(1, "my node!")]

match

</>

pub fn match(
  graph: Graph(a, b, c),
  node_id: Int,
) -> Result(#(Context(b, c), Graph(a, b, c)), Nil)

If the graph contains a node with the given id, returns a tuple containing the context of that node (with all edges looping back to itself removed) and the “remaining” graph: that is, the original graph where that node has been removed.

new

</>

pub fn new() -> Graph(a, b, c)

Creates a new empty graph.

Examples

nodes(new())
// -> []

nodes

</>

pub fn nodes(graph: Graph(a, b, c)) -> List(Node(b))

Returns a list of all the nodes contained in the graph.

Examples

new() |> nodes
// -> []

new() |> insert_node(Node(1, "a node")) |> nodes
// -> [Node(1, "a node")]

remove_directed_edge

</>

pub fn remove_directed_edge(
  graph: Graph(Directed, a, b),
  from source: Int,
  to destination: Int,
) -> Graph(Directed, a, b)

Removes a directed edge connecting two nodes from a graph.

remove_node

</>

pub fn remove_node(
  graph: Graph(a, b, c),
  node_id: Int,
) -> Graph(a, b, c)

Removes a node with the given id from the graph. If there’s no node with the given id it does nothing.

remove_undirected_edge

</>

pub fn remove_undirected_edge(
  graph: Graph(Undirected, a, b),
  between one: Int,
  and other: Int,
) -> Graph(Undirected, a, b)

Removes an undirected edge connecting two nodes from a graph.

reverse_edges

</>

pub fn reverse_edges(
  graph: Graph(Directed, a, b),
) -> Graph(Directed, a, b)

Flips the direction of every edge in the graph. All incoming edges will become outgoing and vice-versa.

size

</>

pub fn size(graph: Graph(a, b, c)) -> Int

Returns the number of nodes of the graph.

Examples

new() |> size
// -> 0

new() |> insert_node(Node(1, "a node")) |> size
// -> 1

to_directed

</>

pub fn to_directed(
  graph: Graph(Undirected, a, b),
) -> Graph(Directed, a, b)

Turns an undirected graph into a directed one. Every edge connecting two nodes in the original graph will be considered as a pair of edges connecting the nodes going in both directions.