möchte­gern­geek

Vor einiger Zeit habe ich @randomGraphs geschrieben: Ein Twitterbot, der einen Zufallsgraphen pro Tag tweetet.

Die meisten Graphtypen, die er darstellen kann stammen aus der NetworkX Bibliothek oder sind reale Netzwerke. Ein paar Proximity Graphs habe ich selbst geschrieben. Die Darstellung und gegebenenfalls das Layout übernimmt Cytoscape oder graph-tool (dessen Autor diesem Bot folgt).

Bei diesem Projekt habe ich exzessiv Gebrauch von Pythons Decorator und Introspection gemacht, sodass man, um einen neuen Graphtyp einzuführen nur eine Methode schreiben muss, die eine Graph-Datenstruktur zurück gibt. Einstellungen, welche Darstellungen erlaubt sind, werden per decorator getätigt und alle Methoden werden per Introspection automatisch zum Pool hinzugefügt, aus dem der Zufallsgenerator zieht.

Eine typische Methode sieht etwa so aus.

@synonym("Barabasi Albert")
@synonym("preferential attachment")
@style(styles_all)
@layout(["kamada-kawai", "force-directed", "sfdp", "fruchterman_reingold", "arf", "radial_tree"])
def generateBarabasiAlbert(self, N=None, m=None, **kwargs):
    if N is None: N = random.randint(4, 400)
    if m is None: m = random.randint(1, 5)

    G = gen.barabasi_albert_graph(N, m)  # gen is networkx Generator
    details = dict(name="Barabási-Albert Graph", N=N, m=m, seed=self.seed,
                   template="{name}, N = {N}, m = {m}")

    return G, details

Und liefert für $N=226, m=1$ und das radial_tree Layout beispielsweise diesen Graph. Die Größe der Knoten wird hier von der Betweenness Centrality bestimmt.

Die @synonym Decorators ermöglichen die zweite Funktion des Bots, denn er tweetet nicht nur einmal am Tag einen zufälligen Graphen, sondern reagiert auch auf Mentions. Falls in der Mention der Name der Methode oder eines der per @synonym registrierten Worte auftaucht, antwortet er mit einem Bild des entsprechenden Graphen. Dank fuzzywuzzy ist es sogar resistent gegen Tippfehler.

Twitter unterstützt leider keine Vektorgrafiken und wandelt Bilder gerne in stark komprimierte .jpg, was gerade bei diesen Graphen zu störenden Artefakten führt. Dagegen hilft es, wenn ich einen Rand aus transparenten Pixeln dem Bild hinzufüge. Das führt dazu, dass Twitter .jpg nicht als geeignetes Format ansieht und die Bilder im verlustfreien .png ausliefert.

convert -alpha on -channel RGBA -bordercolor "rgba(0,0,0,0)" -border "1x1" input.png output.png

Der komplette Quellcode ist auf Github.

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.