möchte­gern­geek

Der wohl berühmteste zelluläre Automat ist vermutlich Conway’s Game of Life. Er und nahe Verwandte sind geradezu lächerlich gut untersucht. Das LifeWiki gibt einen ganz guten Überblick. Die Regeln sind einfach: Jede Zelle hat 8 Nachbarn, wenn genau 3 Nachbarn leben, erwacht sie auch zum Leben, bei weniger als 2 oder mehr als 3 stirbt sie (23/3). Wenn man die Regeln des Automaten ändert, kann man mit 12345/3 labyrinthartige Strukturen erzeugen.

Der Code ist als Gist auf GitHub verfügbar.

Zu jedem Zeitpunkt ist im obigen Video ein Relative Neighborhood Graph (RNG) zu sehen. Der RNG verbindet Knoten miteinander, die nahe beieinander sind. Für die Knotenmenge $V$ muss also eine Metrik definiert sein, sodass eine Distanz $d_{ij}$ zwischen zwei Knoten definiert ist. Dann verbindet der RNG alle Knoten, die die Bedingung $$ d_{ij} \le \max(d_{ik}, d_{kj}) \quad \forall k \in V\setminus{i, j} $$ erfüllen.

Dementsprechend simpel kann man einen RNG erzeugen.

import random

import networkx as nx
import matplotlib.pyplot as plt


def dist(n1, n2):
    """Euclidean distance"""
    return ((n1[0] - n2[0])**2 + (n1[1] - n2[1])**2)**0.5


def rng(G):
    """Insert edges according to the RNG rules into the graph G"""
    for c1 in G.nodes():
        for c2 in G.nodes():
            d = dist(c1, c2)
            for possible_blocker in G.nodes():
                distToC1 = dist(possible_blocker, c1)
                distToC2 = dist(possible_blocker, c2)
                if distToC1 < d and distToC2 < d:
                    # this node is in the lune and blocks
                    break
            else:
                G.add_edge(c1, c2)


if __name__ == "__main__":
    # generate some random coordinates
    coordinates = [(random.random(),random.random()) for _ in range(100)]

    G = nx.Graph()
    for x, y in coordinates:
        G.add_node((x, y), x=x, y=y)

    rng(G)

    # draw the graph G
    pos = {n: (n[0], n[1]) for n in G.nodes()}
    nx.draw_networkx_nodes(G, pos=pos, node_shape="o")
    nx.draw_networkx_edges(G, pos=pos)

    plt.show()

Interessanterweise tauchen alle Kanten des RNG auch in der Delaunay Triangulation der gleichen Knotenmenge auf. Dies kann man nutzen, um RNGs in $\mathcal{O}(N \log N)$ zu konstruieren.

Meiner persönlichen Meinung nach, bildet der RNG mit dem Verhältnis von Knoten zu Kanten ein ästhetisches Optimum.

Man hat ein großes C++ Projekt, ändert einen Header, führt make aus und ein seltsamer Fehler tritt im Programm auf. Das liegt natürlich daran, dass make nicht alle Quelldateien neu kompiliert hat, die den Header einbinden. Woher sollte make das auch wissen? Alle Header per Hand in der Makefile einzutragen und zu pflegen, ist Wahnsinn und wird den Programmierer in denselben treiben.

make ist ein sehr allgemein gehaltenes Programm, wie ich in einem vorherigen Eintrag gezeigt habe. Sich um Eigenheiten von C oder C++ zu kümmern fällt also nicht in den Aufgabenbereich von make. Aber glücklicherweise gibt es ein Programm, dessen Hauptaufgabe es ist, sich mit den Eigenheiten von C bzw. C++ auszukennen: den Compiler. Tatsächlich bietet (zumindest GCC) die Option eine C oder C++ Datei zu parsen und alle inkludierten Header auszugeben.

g++ -MM myCode.cpp

Das ausnutzend, bietet die offizielle Dokumentation von GNU make folgende Rule, um je eine „dependency“ Makefile pro .c Datei zu erzeugen und automatisch einzubinden.

%.d: %.c
    @set -e; rm -f $@; \
    $(CC) -M $(CPPFLAGS) $< > $@.$$$$; \
    sed ’s,\($*\)\.o[ :]*,\1.o $@ : ,g’ < $@.$$$$ > $@; \
    rm -f $@.$$$$

include $(sources:.c=.d)

Falls man .o Dateien in ein obj/ Verzeichnis speichert, muss man die Regex anpassen. In meinen Projekten leistet mir diese Rule gute Dienste.

Alternativ könnte man natürlich auf ein anderes Buildsystem statt handgepflegter Makefiles umsteigen.