org-graph

README.md

Relations

Relations are maintained through the outline hierarchy and special properties on the entries so we can model arbitrary graphs instead of only DAGs. This means you can define parents or children completely outside the hierarchy or even in different files.

Relations are kept in sync bidirectionally so please only use the API to maintain them otherwise things might get lost. Because the relations are bidirectional the graph traversal and querying is extremly fast.

Parents

Parents are defined by the GRAPH_PARENTS property as list of IDs and implicitly through the org outline hierarchy: all headlines above this one are this entry's parents.

You can optionally skip parents defined by hierarchy if you give them non-nil property GRAPH_PARENT_SKIP. This will skip the parent with the property but will continue the traversal further up.

You can optionally skip all parents above the current one by giving it non-nil property GRAPH_PARENT_ROOT. This will include this parent but will not traverse any further. If you do not want to include the root give it the GRAPH_PARENT_SKIP property as well.

Children

Children are defined by the GRAPH_CHILDREN property as list of IDs and implicitly through the org outline hierarchy: the entire subtree (excluding current entry) are this entry's children.

You can optionally skip children defined by hierarchy if you give them non-nil property GRAPH_CHILD_SKIP. This will skip the child with the property but will continue the traversal further down.

You can optionally skip all children below the current child by giving it non-nil property GRAPH_CHILD_LEAF. This will include this child but will not traverse any further. If you do not want to include the leaf give it the GRAPH_CHILD_SKIP property as well.

API

• org-graph-get-parents to get parents of current entry.
• org-graph-get-children to get children of current entry.
• org-graph-add-parent to add a parent to the current entry.
  • check if the parent is defined by hierarchy and do not add the ID
• org-graph-add-child to add a child to the current entry.
  • check if the child is defined by hierarchy and do not add the ID
• org-graph-remove-parent to remove a parent from the current entry.
• org-graph-remove-child to remove a child from the current entry.

It would be also nice to add some way to store link properties (that is, label/annotate the edges of the graph). We might use some simple property format like :GRAPH_EDGE: id <properties>. This can only be stored on e.g. parent (or child) because we can get to the other end of the relation relatively simply by using the traversal properties.

example.org

A

B

C

D

E

F

G

H

I

J

K

org-graph.el

;;; Parents

(defun org-graph--get-parents-from-tree (&optional pom)
  "Get all parents of the headline at POM.

If any of the parents has the property GRAPH_PARENT_SKIP this
parent is not included in the parents but its parents *are*
traversed.

If any of the parents (including this entry) has the property
GRAPH_PARENT_ROOT all the parents above this headline will be
ignored.  This root parent is included, so if you want to skip it
as well give it GRAPH_PARENT_SKIP property as well.

Return list of markers pointing to the parent entries."
  (org-with-point-at pom
    (let (re)
      (while (and (not (org-entry-properties nil "GRAPH_PARENT_ROOT"))
                  (org-up-heading-safe))
        (unless (org-entry-properties nil "GRAPH_PARENT_SKIP")
          (push (point-marker) re)))
      (nreverse re))))

(defun org-graph--get-parents-from-property (&optional pom)
  "Get all parents specified in the GRAPH_PARENTS property at POM.

Return list of markers pointing to the parent entries."
  (org-with-point-at pom
    (let ((parents (org-entry-get-multivalued-property nil "GRAPH_PARENTS")))
      (-map (lambda (entry) (org-id-find entry 'marker)) parents))))

(defun org-graph-get-parents (&optional pom)
  "Return all parents at POM."
  (let ((parents-from-property (org-graph--get-parents-from-property pom))
        (parents-from-tree (org-graph--get-parents-from-tree pom)))
    (-map
     (lambda (p)
       (org-with-point-at p
         (list :pom p :name (org-get-heading 'no-tags 'no-todo))))
     (-concat parents-from-tree parents-from-property))))

(defun org-graph-add-parent (&optional pom)
  (interactive)
  (org-with-point-at pom
    (-when-let (parent (-last-item (org-refile-get-location "Parent: ")))
      (let ((my-id (org-id-get-create))
            (parent-id (org-with-point-at parent (org-id-get-create))))
        (org-entry-add-to-multivalued-property parent "GRAPH_CHILDREN" my-id)
        (org-entry-add-to-multivalued-property pom "GRAPH_PARENTS" parent-id)))))

;;; Children
(defun org-graph--get-children-from-tree (&optional pom)
  "Get all children of the headline at POM.

If any of the children has the property GRAPH_CHILD_SKIP this
child is not included in the children but its children *are*
traversed.

If any of the children has the property GRAPH_CHILD_LEAF no
children of that headline will be included.  This leaf headline
is included, so if you want to skip it as well give it the
GRAPH_CHILD_SKIP property.

Return list of markers pointing to the child entries."
  (org-with-point-at pom
    (let* ((re nil)
           (children
            (org-map-entries
             'point-marker t 'tree
             (lambda ()
               (if (org-entry-properties nil "GRAPH_CHILD_LEAF")
                   ;; we still want to include this one if it doesn't have skip on it
                   (progn
                     (unless (org-entry-properties nil "GRAPH_CHILD_SKIP")
                       (push (point-marker) re))
                     (save-excursion (org-end-of-subtree t)))
                 (when (org-entry-properties nil "GRAPH_CHILD_SKIP")
                   (save-excursion
                     (outline-next-heading)
                     (point))))))))
      (let ((re (-sort '< (-concat re children))))
        ;; pop the first entry if it is the current one, we don't want
        ;; to duplicate it
        (when (= (car re) (save-excursion (org-back-to-heading t) (point)))
          (pop re))
        re))))

(defun org-graph--get-children-from-property (&optional pom)
  "Get all children specified in the GRAPH_CHILDREN property at POM.

Return list of markers pointing to the child entries."
  (org-with-point-at pom
    (let ((parents (org-entry-get-multivalued-property nil "GRAPH_CHILDREN")))
      (-map (lambda (entry) (org-id-find entry 'marker)) parents))))

(defun org-graph-get-children (&optional pom)
  "Return all children at POM."
  (let ((children-from-property (org-graph--get-children-from-property pom))
        (children-from-tree (org-graph--get-children-from-tree pom)))
    (-map
     (lambda (p)
       (org-with-point-at p
         (list :pom p :name (org-get-heading 'no-tags 'no-todo))))
     (-concat children-from-tree children-from-property))))

(defun org-graph-add-child (&optional pom)
  (interactive)
  (org-with-point-at pom
    (-when-let (child (-last-item (org-refile-get-location "Child: ")))
      (let ((my-id (org-id-get-create))
            (child-id (org-with-point-at child (org-id-get-create))))
        (org-entry-add-to-multivalued-property child "GRAPH_PARENTS" my-id)
        (org-entry-add-to-multivalued-property pom "GRAPH_CHILDREN" child-id)))))