graphwfc package

Submodules

graphwfc.GraphWFCState module

class graphwfc.GraphWFCState.GraphWFCState(GO, GI=None, GLs=None, pattern_count_per_GL=None, GI_isos_per_GL=None, GO_isos_per_GL=None, node_attr='color', edge_attr='type')

Bases: object

includes everything needed to run GraphWaveFunctionCollapse

Variables:
  • GO – a copy of the input GO but with ‘invisible’ nodes removed. After run() returned True it will be colored.
  • iteration_count – The amount of iterations that :py:meth:run did since the last :py:meth:reset
  • invisible_nodes – The nodes omitted from GO since they are not targeted by any isomorphism
GO
__init__(GO, GI=None, GLs=None, pattern_count_per_GL=None, GI_isos_per_GL=None, GO_isos_per_GL=None, node_attr='color', edge_attr='type')

the constructor sets up the state after 0 iterations

This will create a GraphWFCState. Since we have to find isomorphisms this can take a while if a GL in GLs is ‘big’. If available GI_isos_per_GL, GO_isos_per_GL and pattern_count_per_GL can be set so they do need to be computed.

Parameters:
  • GO – the output graph to be colored
  • GI – the colored graph used as the example input. Every node must be colored and None is not a accepted as color.
  • GLs – the ordered (e.g. a list) graphs that describe the patterns (optional if pattern_count_per_GL, GI_isos_per_GL and GO_isos_per_GL are given)
  • pattern_count_per_GL – (optional) a cached return value from helpers.get_patterns()
  • GI_isos_per_GL – (optional) a cached return value from helpers.get_isos()
  • GO_isos_per_GL – (optional) a cached return value from helpers.get_isos()
  • node_attr – the name of the node attribute used as color
  • edge_attr – the name of the edge attribute used to distinguish between edges
Raises:

ValueError – if OG can’t be colored (if it doesn’t throw it still may be impossible)
invisible_nodes
iteration_count
reset()

resets the object to the state after the construction

This is useful if run() runs into a contradiction (it returns false). Call this method and and run() can be called again. This is not called automatically so that information about the contradiction can be extracted

run(iter: int = -1)

runs GraphWaveFunctionCollapse on the graphs

After initialising the GraphWFCState, we need to run the GraphWaveFunctionCollapse algorithm using this method. It will iterate until a contradiction is observed, colors were determined for all nodes or after the given amount of maximal iterations.

Parameters:iter – the maximum amount of GraphWaveFunctionCollapse-iterations. No limiting if negative
Returns:True if GO has been completely colored, False if a contradiction occurred and nothing if the maximum amount of iterations was used up.

graphwfc.helpers module

graphwfc.helpers.get_isos(GB: networkx.classes.digraph.DiGraph, GLs, edge_attr='type')

returns the isomorphisms from every GL in GLs to a node induced subgraph of G as a ordered list of nodes

This function is used to get the needed isos. Usually called with GI or GO as G. While this is called by the GraphWFCState constructor it might be useful to call it yourself and cache the results if some graphs are used multiple times.

Parameters:
  • GB – the ‘big’ Graph, GI or GO
  • GLs – the ‘small’ graphs GL in an order (e.g. in a list)
  • edge_attr – the attribute used to decide whether two edges should be considered to be of the same type
Returns:

the isos in G per LG
graphwfc.helpers.get_patterns(GI: networkx.classes.digraph.DiGraph, GLs=None, GI_isos_per_GL=None, node_attr='color', edge_attr='type')

extracts the patterns from GI for each GL and counts them

This is called by the GraphWFCState constructor. If neither GI nor GLs differ for two GraphWFCStates, this can be used to cache the patterns. Its return value can be used as the pattern_count_per_GL parameter.
Parameters:
  • GI – the input Graph to extract the patterns from
  • GLs – the (ordered) GLs to define the ‘shape’ of the patterns
  • GI_isos_per_GL – the cached isos from e.g. get_isos(GI, GL, edge_attr=edge_attr). Alternative for the GLs parameter
  • node_attr – the node attribute to be used in GraphWFC
  • edge_attr – the attribute used to decide whether two edges should be considered to be of the same type
Returns:

the patterns found in GI per LG and how often they were found

Module contents

A python implementation of GraphWaveFunctionCollapse

This algorithm is based on WaveFunctionCollapse. It colors an output graph GO such that all patterns used are from the example input graph GI. A pattern is a colored subgraph which shape is determined by a small graph GL. Some usage examples can be found on the GitHub page. We use ‘iso’ in the API as a short form of ‘subgraph isomorphism’.

Example code:

>>> import networkx as nx
>>> import graphwfc
>>> GI = nx.Graph([(1,2),(2,3),(3,4)]).to_directed()
>>> GI.add_nodes_from([(1,{'c':1}),(2,{'c':1}),(3,{'c':2}),(4,{'c':3})])
>>> GL = nx.Graph([(1,2)]).to_directed()
>>> GO = nx.random_tree(1000).to_directed()
>>> S = graphwfc.GraphWFCState(GO=GO,GLs=[GL],GI=GI,node_attr='c')
>>> while not S.run():
...     S.reset()
...
>>> nx.write_graphml(S.GO, "out.graphml")

GI is the graph 1 – 1 – 2 – 3 and GL is a – b where a and b have no color. We extract the patterns 1 – 1, 1 – 2 and 2 – 3. GO will only contain the extracted patterns. As such the out.graphml will contain a tree with 1000 nodes colored in a way such that no node with color 2 has a neighbour colored 2 and no node colored 3 has a neighbour with color 3 or 1. The color will be stored in the node attribute ‘c’.