WaveFunctionCollapse on graphs
A python 3.x package to color a graph based on patterns extracted from an colored example graph, it's based on WaveFunctionCollapse. I wrote a thesis on the algorithm (in German).
Below are some examples:
In the /examples directoy all graphs (GI,GL and GO) can be found as GraphML files. You may also want to look at the example in the Usage section.
To display GraphML files you might want to check out Gephi, Tulip and/or Cytoscape.
The second example from the top (starcave) uses graphs to simulate WFC with N=3.
The general idea is similar to WFC:
Install with pip install graphwfc
or after downloading this repo python setup.py install
.
After installing you can try out the examples by going into the respective directory (e.g. /examples/beach) and running python -m graphwfc -v value
. This will generate an out.graphml file.
All examples use the node attribute 'value' as color which is given by -v value
.
With -e edge_attr
it will check for equality of the edge attribute 'edge_attr' while searching for subgraph isomorphisms. The default is 'type'.
While this package was meant to be used standalone with python -m graphwfc
an API is available which can be found in the autogenerated documenation.
Remarks:
Example code
import networkx as nx
import graphwfc
GI = nx.Graph([(1,2),(2,3),(3,4)])
GI.add_nodes_from([(1,{'c':'b'}),(2,{'c':'b'}),(3,{'c':'r'}),(4,{'c':'y'})])
GL = nx.Graph([(1,2)])
GO = nx.random_tree(40)
S = graphwfc.GraphWFCState(GO=GO,GLs=[GL],GI=GI,node_attr='c')
while not S.run():
S.reset()
GI is the graph blue -- blue -- red -- yellow
('b' -- 'b' -- 'r' -- 'y'
).
GL is 1 -- 2
where 1 and 2 have no color.
We extract the patterns blue -- blue
, blue -- red
and red -- yellow
.
GO will only contain the extracted patterns. As such the GO will be a tree with 40 nodes colored in a way such that no red node has a red neighbour and no yellow node has a neighbour with that is yellow or blue. The color will be stored in the node attribute 'c'.
You can either save the output with
nx.write_graphml(S.GO, "out.graphml")
Or you can visualize it with matplotlib (pip install matplotlib
)
import matplotlib.pyplot as plt
colors = list(nx.get_node_attributes(S.GO,'c').values())
nx.draw(S.GO, node_color=colors, node_size=100)
plt.show()
Fun Fact: This example is an arc consistency problem. In this case GraphWaveFunctionCollapse's constraint propagation will behave somewhat similar to the AC-3 algorithm.