One of the ideas I wanted to explore was the ability to have a graph
(essentially a drawing). Combined with the ability to line up future
changes that will be applied to this graph. In
WEIR this kind
of future change is named an alteration.
The main motivation was that this would let you collect a series of
alterations, then apply them later. Knowing that you can safely access the
current state of the graph because it is currently unaltered. This
functionality is made possible with a macro,
that collects and the applies the alterations.
Another motivation was that this would provide an expressive and simple interface, where the complexity of actually applying the alteration is hidden behind the scenes.
For simple cases this worked well enough, but I quickly realised that I wanted to create (nested) alterations that were dependent on other alterations. Essentially I wanted a dependency graph of futures. In other words, it proved to be far more limited than I had initially imagined.
Implementing this dependency graph seemed rather complicated, so I had mostly discarded it.
Since I made the first version of this functionality, I have only made a few technical improvements to the code that enables it. Beyond that I have largely left it unaltered.
The implementation isn't that interesting in itself, I assume there are other people who have implemented this kind of dependency resolving more elegantly. However, I thought I'd share an example of what this new functionality allows me to do. Or perhaps, more interestingly, how it to some extent lets me write an algorithm that almost looks like pseudo code.
The example below is an iterative algorithm that starts with a single straight line (edge). And then proceeds to select edges at random. Effectively the selected edge is split at the middle, and two new edges are appended at the split, rotated around the middle of the edge.
We assume that we have an initial graph instance,
wer, with an initial seed edge. Furthermore the alteration,
(add-edge? ...), will only do anything with a certain
probability, and if the new edge does not cross any existing edges.
; repeats n times: ; select a random edge, ee, from wer (with-rnd-edge (wer ee) (let* ((vv (get-verts wer ee)) ; positions of edge (mid (get-mid vv)) ; midpoint of edge (angle (get-rnd-angle)) ; random angle (rotated (rotate vv mid angle))) ; rotate vv around mid (with (wer %) ; delete the selected edge (% (ldel-edge? ee)) ; nev vertex in the middle, named :mid (% (add-vert? mid) :mid) ; two new verts, rotated relative to ; initial edge, named :r1 and :r2 (% (add-vert? (first rotated)) :r1) (% (add-vert? (second rotated)) :r2) ; four new edges from :mid to the ; new vertices :r1 and :r2; and the existing ; vertices of edge, ee ; (:mid :r1) means that this alteration ; depends on :mid and :r1 (% (add-edge? :mid :r1) (:mid :r1)) (% (add-edge? :mid :r2) (:mid :r2)) (% (add-edge? :mid (first ee)) (:mid)) (% (add-edge? :mid (second ee)) (:mid)))))
- An alteration is unaware of the current state of the graph; if it happens to be invalid in some way when it is about to be applied, it will be discarded.
- For some definition of easy.
- You can probably spot a possible flaw here. Depending on how
(add-edge? ...)is implemented the intersection test will happen at the time of alteration creation, or at the time of alteration application. My code does the latter, because it works just as well for what I wanted to do. This kind of consideration applies to all possible alterations.