Types

Edge[N; E] = ref EdgeObj[N, E]

An edge connects two nodes.

Nodes have a user-supplied .value of type N. Edges have a user-supplied .value of type E.

Source Edit

EdgeResult[N; E] = tuple[source: Node[N, E], edge: Edge[N, E],
                         target: Node[N, E]]

Source Edit

Graph[N; E; F] = ref GraphObj[N, E, F]

A collection of nodes and edges.

Nodes have a user-supplied .value of type N. Edges have a user-supplied .value of type E.

Source Edit

GraphFlag {.size: 8.} = enum
  QueryResult = "the graph only makes sense in relation to another graph",
  UniqueNodes = "the nodes in the graph all have unique values",
  UniqueEdges = "the edges in the graph all have unique values",
  Directed = "edges have different semantics for source and target",
  Undirected = "edges have identical semantics for source and target",
  SelfLoops = "nodes may have edges that target themselves",
  Ultralight = "the graph is even lighter",
  ValueIndex = "node and edge values are indexed for speed"

Source Edit

GraphFlags = int

Source Edit

Node[N; E] = ref NodeObj[N, E]

A node in the graph.

Nodes have a user-supplied .value of type N. Edges have a user-supplied .value of type E.

Source Edit

NoValueIndexGraph = concept g
    contains(g.flags, ValueIndex) == false

Source Edit

ValueIndexGraph = concept g
    contains(g.flags, ValueIndex) == true

Source Edit

Consts

defaultGraphFlags = {Directed, SelfLoops, ValueIndex}: Source Edit

Procs

proc `$`[N, E](thing: Node[N, E] | Edge[N, E]): string: A best-effort convenience. Source Edit
proc `[]`[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]; key: N): Node[N, E]: Index an immutable graph to retrieve a immutable node of value key. Source Edit
proc `[]`[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]; key: N): var Node[ N, E]: Index a mutable graph to retrieve a mutable node of value key.
Example:

var g = newGraph[int, string]() discard g.add 3 assert g[3].value == 3
Source Edit
proc `[]`[N, E](node: Node[N, E]; key: E): Node[N, E]: Index a node by edge key, returning the opposite node.
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 discard g.edge(g[3], "squared", g[9]) let l3 = g[3] l9 = g[3]["squared"] assert l9.value == 9
Source Edit
proc `[]`[N, E](node: var Node[N, E]; key: E): var Node[N, E]: Index a node by edge key, returning the opposite (mutable) node.
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 let squared = g.edge(g[3], "squared", g[9]) let n9 = g[3]["squared"] assert n9.value == 9
Source Edit
proc add[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]; value: N): Node[ N, E]: Creates a new node of value and adds it to the graph. Returns the new node. O(1).
Example:

var g = newGraph[int, string]() discard g.add 3 assert len(g) == 1 discard g.add 9 assert len(g) == 2
Source Edit
proc clear[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]): Empty a graph of all nodes and edges.
Example:

var g = newGraph[int, string]() discard g.add 3 clear(g) assert len(g) == 0
Source Edit
proc contains[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]; edge: Edge[N, E]): bool: Returns true if graph contains edge. O(1).
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 27 let e = g.edge(g[3], "cubed", g[27]) assert e in g
Source Edit
proc contains[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]; node: Node[N, E]): bool: Returns true if graph contains node. O(1).
Example:

var g = newGraph[int, string]() let n = g.add 3 assert n in g
Source Edit
proc contains[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]; value: N): bool: Returns true if graph contains a node with the given value. O(1) for ValueIndex graphs, else O(n).
Example:

var g = newGraph[int, string]() discard g.add 3 assert 3 in g
Source Edit
proc contains[N, E](edge: Edge[N, E]; node: Node[N, E]): bool: Returns true if the edge links to node; else false. O(1).
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 discard g.edge(g[3], "squared", g[9]) for source, edge, target in g.edges: assert source in edge assert target in edge
Source Edit
proc contains[N, E](edge: Edge[N, E]; value: N): bool: Returns true if edge links to a node with the given value; else false. O(1).
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 discard g.edge(g[3], "squared", g[9]) let n = g[9] for source, edge, target in g.edges: assert 9 in edge assert 3 in edge
Source Edit
proc contains[N, E](node: Node[N, E]; edge: Edge[N, E]): bool: Returns true if Node node has Edge edge.
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 let e = g.edge(g[3], "squared", g[9]) assert e in g[3]
Source Edit
proc contains[N, E](node: Node[N, E]; key: E): bool: Returns true if an edge with value key links node. O(log n).
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 discard g.edge(g[3], "squared", g[9]) assert "squared" in g[3]
Source Edit
proc del[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]; node: Node[N, E]): Remove a node from the graph; O(n). Has no effect if the node is not in the graph. Not O(1) yet.
Example:

var g = newGraph[int, string]() let n = g.add 3 g.del n assert len(g) == 0
Source Edit
proc del[N, E](node: var Node[N, E]; edge: Edge[N, E]): Remove edge from node. Of course, this also removes edge from the target node on the opposite side. O(log n). Source Edit
proc del[N, E](node: var Node[N, E]; value: E): Remove edge with value value from node. Of course, this also removes the edge from the target node on the opposite side. O(log n)
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 discard g.edge(g[3], "squared", g[9]) var n9 = g[3]["squared"] n9.del "squared" assert not peers(g[3], n9)
Source Edit
proc edge[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]; node: var Node[N, E]; value: E; target: var Node[N, E]): Edge[N, E]: Link node to target via a new edge of value; O(1).
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 27 let e = g.edge(g[3], "cubed", g[27]) assert e.value == "cubed" assert g[3] in e assert g[27] in e
Source Edit
proc edge[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]; node: Node[N, E]; value: E; target: Node[N, E]): Edge[N, E]: Add new edge into graph using immutable source and target nodes. Source Edit
proc hash[N, E, F](graph: Graph[N, E, F]): Hash: Produce a Hash that uniquely identifies the graph based upon its contents. Source Edit
proc hash[N, E](edge: Edge[N, E]): Hash: Produce a Hash that uniquely identifies the edge. Source Edit
proc hash[N, E](node: Node[N, E]): Hash: Produce a Hash that uniquely identifies the node and varies with changes to its neighborhood. Source Edit
proc incl[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]; node: Node[N, E]): Includes a node in the graph. Has no effect if the node is already in the graph. O(1).
Example:

var g = newGraph[int, string]() let n = g.add 3 var q = newGraph[int, string]() q.incl n q.incl n assert len(q) == 1
Source Edit
proc init(graph: var NoValueIndexGraph): Source Edit
proc init(graph: var ValueIndexGraph): Source Edit
proc len[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]): int: Return the number of nodes in a graph. O(1).
Example:

var g = newGraph[int, string]() assert len(g) == 0
Source Edit
proc len[T](list: Container[T]): int {....deprecated: "count() conveys the O(n) cost".}: Deprecated: count() conveys the O(n) cost
Use count() instead; it expresses the O more clearly. Source Edit
proc newContainer[N, E, F](graph: Graph[N, E, F]; form: typedesc): auto: Create a new container for nodes or edges. Source Edit
proc node[N, E; F: static[GraphFlags]](graph: var Graph[N, E, F]; value: N): Node[ N, E]: Create a new node compatible with graph; O(1).
Example:

var g = newGraph[int, string]() var n = g.node(3) assert len(g) == 0 g.incl n assert len(g) == 1
Source Edit
proc nodesAreUnique[N, E, F](graph: Graph[N, E, F]): bool: Returns true if there are no nodes in the graph with duplicate values. O(1) for ValueIndex graphs, else O(n).
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 assert g.nodesAreUnique discard g.add 3 assert not g.nodesAreUnique
Source Edit
proc peers[N, E](node: Node[N, E]; target: Node[N, E]): bool: Returns true if node shares an edge with target.
Example:

var g = newGraph[int, string]() var g3 = g.add 3 g9 = g.add 9 assert not peers(g9, g3) discard g.edge(g3, "squared", g9) assert peers(g3, g9)
Source Edit

Iterators

iterator edges[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]): EdgeResult[ N, E]: Yield source node, edge, and target node from a graph.
Example:

var g = newGraph[int, string]() discard g.add 3 discard g.add 9 discard g.edge(g[3], "squared", g[9]) for source, edge, target in edges(g): assert edge.value == "squared" assert source.value == 3 assert target.value == 9
Source Edit
iterator incoming[N, E](node: Node[N, E]): tuple[edge: Edge[N, E], source: Node[N, E]]: Yield incoming edge and source source from a node. Source Edit
iterator incoming[N, E](node: var Node[N, E]): tuple[edge: var Edge[N, E], source: var Node[N, E]]: Yield mutable incoming edge and source source from a mutable node. Source Edit
iterator items[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]): N: Yield the values of nodes in the graph.
Example:

var g = newGraph[int, string]() discard g.add 3 for value in items(g): assert value == 3
Source Edit
iterator neighbors[N, E](node: Node[N, E]): tuple[edge: Edge[N, E], node: Node[N, E]]: Yield edge and target node from a node. Source Edit
iterator nodes[N, E; F: static[GraphFlags]](graph: Graph[N, E, F]): Node[N, E]: Yield each node in the graph.
Example:

var g = newGraph[int, string]() discard g.add 3 for node in nodes(g): assert node.value == 3
Source Edit
iterator outgoing[N, E](node: Node[N, E]): tuple[edge: Edge[N, E], target: Node[N, E]]: Yield outgoing edge and target target from a node. Source Edit
iterator outgoing[N, E](node: var Node[N, E]): tuple[edge: var Edge[N, E], target: var Node[N, E]]: Yield mutable outgoing edge and target target from a mutable node. Source Edit

Converters

converter toFlags(value: GraphFlags): set[GraphFlag] {....raises: [], tags: [], forbids: [].}: Source Edit
converter toInt(flags: set[GraphFlag]): GraphFlags {....raises: [], tags: [], forbids: [].}: Source Edit

Templates

template flags[N, E, F](graph: Graph[N, E, F]): set[GraphFlag]: Source Edit
template newGraph[N, E](): auto: Source Edit
template newGraph[N, E](wanted: GraphFlags): auto: Create a new graph; nodes will hold N while edges will hold E.
Example:

var g = newGraph[int, string]() assert g != nil
Source Edit

gram

Types

Consts

Procs

Iterators

Converters

Templates