Built-in Tasks

Graph Coloring

class PottsPlayground.Tasks.GraphColoring(ncolors, p=None, nnodes=None, G=None, seed=None)

Models the Graph Node coloring problem as a Potts model, which is just about the simplest possible model. Rather than asking how many colors are needed to color a graph, which is the typical framing of graph coloring, the simple Potts model form asks if a coloring with a set number of colors is possible.

DisplayState(state)

graphically represents the solution given by the supplied state.

__init__(ncolors, p=None, nnodes=None, G=None, seed=None)

Either construct a random Erdos-Renyi graph, or use a graph given by G.

Parameters for either initialization:

Parameters:

• ncolors (int) – How many colors are to be used.

• seed (int) – Optional seed for random graph construction, for repeatable results.

Parameters for coloring a random Erdos-Renyi graph:

Parameters:

• p (float) – Edge probability for random graph construction (i.e. edge density)

• nnodes – Number of graph nodes for random graph construction

• nnodes – int

Parameters for coloring a given graph:

Parameters:

G (undirected networkx graph) – The graph to be colored.

Traveling Salesman

class PottsPlayground.Tasks.TravelingSalesman(ncities=None, costs=None, ConstraintFactor=1, seed=None)

Potts model representation of the Traveling Salesman Problem (TSP).

DisplayState(state)

If the regular euclidean TSP was used, this plots the city locations and connects them with line segments to show the tour represented by the given state.

Parameters:

state (1-D Numpy int) – Vector of spin magnetizations.

__init__(ncities=None, costs=None, ConstraintFactor=1, seed=None)

Two initializations are possible. Either a regular euclidean traveling salesman on a plane is randomly generated, bounded in the coordinate box (0,1)x(0,1); or a matrix of segment costs is passed.

For generating a regular euclidean TSP instance:

Parameters:

• ncities (int) – The number of cities to randomly generate.

• seed – Optional, define a seed to make the process repeatable.

For using an arbitrary set of costs:

Parameters:

costs (NxN Numpy float) – Matrix where each element i,j is the cost to travel from i to j.