Your First Graph

Caution

gen is pre-release and its API is still changing.

This guide models six services and the services each one depends on, then asks six questions about them with one library, gen-graph. It then adds a second relation, containment, over a different set of nodes.

1. Declare the nodes

   The nodes are your data. type is a field you chose. gen-graph gives it no meaning:

   services = {
     web    = { deps = [ "api" ];         type = "frontend";  };
     api    = { deps = [ "db" "cache" ];  type = "backend";   };
     worker = { deps = [ "db" "queue" ];  type = "backend";   };
     db     = { deps = [ ];               type = "datastore"; };
     cache  = { deps = [ ];               type = "datastore"; };
     queue  = { deps = [ ];               type = "datastore"; };
   };

2. Relate them

   The accessor record tells gen-graph where the edges are. edges is all a traversal needs. nodeData lets a query read the other attributes:

   g = {
     edges    = id: services.${id}.deps or [ ];
     parent   = _: null;
     nodes    = builtins.attrNames services;
     nodeData = id: services.${id};
   };

3. Read the result back

   {
     entryPoints  = graph.roots g;                              # (1)
     datastores   = graph.leaves g;                             # (2)
     webDeps      = graph.reachableFrom g "web";                # (3)
     dbImpact     = graph.dependents { } g "db";                # (4)
     backendNodes = graph.select g (d: d.type == "backend");    # (5)
     hasCycles    = graph.cycles g != [ ];
   }

   1. Nodes that nothing depends on.
   2. Nodes that depend on nothing.
   3. Everything web needs, transitively.
   4. Everything that needs db. dependents takes an options set first, and { } selects the defaults.
   5. A query over nodeData. It reads each node’s type field.

   This returns:

   {
     "entryPoints": ["web", "worker"],
     "datastores": ["cache", "db", "queue"],
     "webDeps": ["api", "db", "cache"],
     "dbImpact": ["api", "web", "worker"],
     "backendNodes": ["api", "worker"],
     "hasCycles": false
   }

   Rely on which nodes each list contains. The order of webDeps and dbImpact is the order the traversal visited them in.

A second relation

g declares parent = _: null, so no node has a container. Give the nodes a real containment relation and ancestorsOf answers questions about it:

hosts = {
  "env:prod" = { parent = null; };
  "host:web" = { parent = "env:prod"; };
  "host:db"  = { parent = "env:prod"; };
};

g2 = {
  edges = _: [ ];
  parent = id: hosts.${id}.parent or null;
  nodes = builtins.attrNames hosts;
  nodeData = id: hosts.${id};
};

graph.ancestorsOf g2 "host:web"   # [ "env:prod" ]

edges and parent are two relations over the same node set, read by two accessors. A real graph can declare both, and more.

Several gen-graph functions take an options set before the accessor record: dependents, topoOrder and pathsBetween. Pass { } for the defaults. Leaving it out fails with an error.

The same model at any scale

A framework built on gen uses this same graph. Its hosts, users and features are nodes like services above. It adds more relations, some declared by hand and some produced by rules, and its own names for things. Your Configuration as a Graph explains nodes and edges in full.

Going further

Graphs and QueriesTraversal, ordering, cycles, labelled path queries and selectors.

From an Aspect to a NixOS SystemPut features on these nodes and build real NixOS systems.