Identifying cycles

[goodmami]

Issue #11 is concerned with finding re-entrancies, but cycles may be harder to detect. If we can efficiently detect cycles, we could (a) flag graphs as being cyclical; (b) identify the relations involved in creating a cycle; or even (c) reject cyclical graphs from being created. A simple cycle looks like this:

(a / A :rel a)

Issue #11 has the following example (left); the same graph with a different top (right) looks like a cycle:

(a / A                    (b / B
   :rel (b / B               :rel (c / C
           :rel (c / C))             :rel-of (a / A
   :rel c)                                      :rel b)))

However this is not a cycle, since the relation from c to a (:rel-of) is inverted.

[flipz357]

I think topological sort, i.e., Kahn method is quite simple and solves this problem efficiently.

Just curious, why would it be important for penman to flag graphs that are cyclical? Isn't it more like a custom use-case, for which somebody then would simply resort to packages like networkx?