django-directed#

Tools for building, querying, manipulating, and exporting directed graphs with django.

Documentation can be found at https://django-directed.readthedocs.io/en/latest/

Caution

This project is very much a Work In Progress, and is not production-ready. Once it is in a more complete state, it will be moved to the github Watervize organization for long-term development and maintenance.

Fundamentals#

Graphs in django-directed are constructed with three models (or potentially more in case of extended features).

Graph: Represents a connected graph of nodes and edges. It makes it easy to associate metadata with a particular graph and to run commands and queries limited to a subset of all the Edges and Nodes in the database.
Edge: Connects Nodes to one another within a particular Graph instance.
Node: A node can belong to more than one Graph. This allows us to represent multi-dimensional or multi-layered graphs.

django-directed includes model factories for building various types of directed graphs. As an example, imagine a project in which you display family trees and also provide a searchable interface for research papers about family trees, where papers can be linked to previous papers that they cite. Both of these concepts can be represented by a Directed Acyclic Graph (DAG), and within your project you could create a set of DAG models for the family tree app and another set of DAG models for the academic papers app.

Quickstart#

Assuming you have already started a django project and an app named myapp

Install django-directed#

pip install django-directed

Create the concrete models#

Using the DAG factory, create a set of concrete Graph, Edge, and Node models for your project. Perform the following steps in your app’s models.py

Build a configuration object that will be passed into the factory. Here, we are using the simplest configuration which specifies the graph type (default options include ‘CYCLIC’, ‘DAG’, ‘POLYTREE’, ‘ARBORESCENCE’) and the model names (with appname.ModelName). We fall back to the default values for all other configuration options.

from django_directed.config import GraphConfig


my_config = GraphConfig(
    graph_type="DAG",
    graph_model_name="myapp.DAGGraph",
    edge_model_name="myapp.DAGEdge",
    node_model_name="myapp.DAGNode",
)

Create the concrete models from a model factory service. In this example, we are adding some fields as an example of what you might do in your own application.

from django.db import models
from django_directed.models.model_factory import factory


# Create DAG factory instance
dag = factory.create(config=my_config)

# Create concrete models
class DAGGraph(dag.graph()):
    metadata = models.JSONField(default=str, blank=True)


class DAGEdge(dag.edge()):
    name = models.CharField(max_length=101, blank=True)
    weight = models.SmallIntegerField(default=1)

    def save(self, *args, **kwargs):
        self.name = f"{self.parent.name} -to- {self.child.name}"
        super().save(*args, **kwargs)


class DAGNode(dag.node()):
    name = models.CharField(max_length=50)
    weight = models.SmallIntegerField(default=1)

Note

The model names here (DAGGraph, etc) are for example only. You are welcome to use whatever names you like, but the model names should match the names provided in the configuration.

Migrations#

As usual when working with models in django, we need to make migrations and then run them.

python manage.py makemigrations
python manage.py migrate

Build a couple graphs using our DAG models#

Tip

We are using the graph_context_manager here, which is provided in django-directed for convenience. If you decide not to use this context manager, you need to provide the graph instance when creating or querying with Nodes and Edges.

from django_directed.context_managers import graph_scope

from myapp.models import DAGGraph, DAGEdge, DAGNode


# Create a graph instance
first_graph = DAGGraph.objects.create()
# Create a second graph instance, which will share nodes with first_graph
another_graph = DAGGraph.objects.create()

with graph_scope(first_graph):

    # Create several nodes (not yet connected)
    root = DAGNode.objects.create(name="root")

    a1 = DAGNode.objects.create(name="a1")
    a2 = DAGNode.objects.create(name="a2")
    a3 = DAGNode.objects.create(name="a3")

    b1 = DAGNode.objects.create(name="b1")
    b2 = DAGNode.objects.create(name="b2")
    b3 = DAGNode.objects.create(name="b3")
    b4 = DAGNode.objects.create(name="b4")

    c1 = DAGNode.objects.create(name="c1")
    c2 = DAGNode.objects.create(name="c2")

    # Connect nodes with edges
    root.add_child(a1)
    root.add_child(a2)

    # You can add from either side of the relationship
    a3.add_parent(root)

    b1.add_parent(a1)
    a1.add_child(b2)
    a2.add_child(b2)
    a3.add_child(b3)
    a3.add_child(b4)

    b3.add_child(c2)
    b3.add_child(c1)
    b4.add_child(c2)

with graph_scope(another_graph):

    # Connect nodes with edges
    c1 = DAGNode.objects.get(name="c1")
    c2 = DAGNode.objects.get(name="c2")

    c1.add_child(c2)

Advanced Usage

View this project on Github.