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`, `match_any`
adding/removing elements from a graph	`insert_node`, `insert_directed_edge`, `insert_undirected_edge`, `remove_node`, `remove_directed_edge`, `remove_undirected_edge`
transforming graphs	`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.Dict(Int, label),
    node: Node(value),
    outgoing: dict.Dict(Int, label),
  )
}

Constructors

Context(
  incoming: dict.Dict(Int, label),
  node: Node(value),
  outgoing: dict.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

Values

get_context

</>

pub fn get_context(
  graph: Graph(direction, value, label),
  of node: Int,
) -> Result(Context(value, label), Nil)

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

Examples

assert Error(Nil) == graph.new() |> graph.get_context(of: 1)
let assert Ok(graph.Context(node: Node(1, "a node"), ..)) =
  graph.new()
  |> graph.insert_node(graph.Node(1, "a node"))
  |> graph.get_context(of: 1)

has_edge

</>

pub fn has_edge(
  graph: Graph(direction, value, label),
  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 graph =
  graph.new()
  |> graph.insert_node(graph.Node(1, "a node"))
  |> graph.insert_node(graph.Node(2, "another node"))
  |> graph.insert_directed_edge("label", from: 1, to: 2)

assert graph.has_edge(graph, from: 1, to: 2)
assert !graph.has_edge(graph, from: 2, to: 1)

has_node

</>

pub fn has_node(
  graph: Graph(direction, value, label),
  node_id: Int,
) -> Bool

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

Examples

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

assert graph.has_node(graph, 1)
assert !graph.has_node(graph, 2)

insert_directed_edge

</>

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

Adds an edge connecting two nodes in a directed graph.

insert_node

</>

pub fn insert_node(
  graph: Graph(direction, value, label),
  node: Node(value),
) -> Graph(direction, value, label)

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.

insert_undirected_edge

</>

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

Adds an edge connecting two nodes in an undirected graph.

match

</>

pub fn match(
  graph: Graph(direction, value, label),
  node_id: Int,
) -> Result(
  #(Context(value, label), Graph(direction, value, label)),
  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.

match_any

</>

pub fn match_any(
  graph: Graph(direction, value, label),
) -> Result(
  #(Context(value, label), Graph(direction, value, label)),
  Nil,
)

If the graph contains any node, returns a tuple containing a node of the graph (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(direction, value, label)

Creates a new empty graph.

nodes

</>

pub fn nodes(
  graph: Graph(direction, value, label),
) -> List(Node(value))

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

Examples

assert [] == graph.new() |> graph.nodes
assert [graph.Node(1, "")]
  == graph.new()
  |> graph.insert_node(graph.Node(1, "a node"))
  |> graph.nodes

remove_directed_edge

</>

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

Removes a directed edge connecting two nodes from a graph.

remove_node

</>

pub fn remove_node(
  graph: Graph(direction, value, label),
  node_id: Int,
) -> Graph(direction, value, label)

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, value, label),
  between one: Int,
  and other: Int,
) -> Graph(Undirected, value, label)

Removes an undirected edge connecting two nodes from a graph.

reverse_edges

</>

pub fn reverse_edges(
  graph: Graph(Directed, value, label),
) -> Graph(Directed, value, label)

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

size

</>

pub fn size(graph: Graph(direction, value, label)) -> Int

Returns the number of nodes of the graph.

Examples

assert 0 == graph.new() |> graph.size
assert 1
  == graph.new()
  |> graph.insert_node(graph.Node(1, "a node"))
  |> graph.size

to_directed

</>

pub fn to_directed(
  graph: Graph(Undirected, value, label),
) -> Graph(Directed, value, label)

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.