Chromatic Polynomials 04 – My CP Symbolic Math Engine

I debated whether I should write anything about my CP application and came to realize that I need this article to provide context for formulas and scripts in later articles. You might see some large CPs later and think “There’s no way he did this by hand.” … and you would be right. I love studying CPs, but I’m too lazy and too impatient to do it all on paper. I wrote my own symbolic math engine to process Chromatic Polynomials for a few reasons:

1)     I didn’t expect an existing math application to support my newly-invented syntax.

2)     I had certain features in mind that I wanted done a certain way.

3)     I wanted the satisfaction of fully implementing the CP engine myself.

The CP Engine

I wrote a symbolic CP engine .dll that handles the core CP operations. It implements CPs as programmatic objects:

iCPTerm - The interface that every object in a CP expression must support. This includes informational methods like:

CountTerms - Tells how many terms a term contains.

SumOver - The summation operation, e.g. sum σ₁ through σ₃ from 1 to 10.

ContainsVertex - Tells if this term contains a vertex being summed over.

CPBase - A base implementation that provides functions common to all types of terms in a CP expression.

Then there are specific types of terms which complete the iCPTerm interface:

IntegerTerm - a standalone integer in a CP expression, e.g. 5.

VariableTerm - a variable, like Q. Contains a power property to represent, e.g. Q^5.

ExtendedKroneckerDelta - an EKD. Contains a collection of vertices and a collection of constants.

ProductTerm - a collection of terms multiplied together. e.g. 5Q^3*δ_σ1σ3.

SumTerm - a collection of terms added together, e.g. (1 -  δ_σ1σ3).

All of the higher-level functions deal solely with iCPTerm. I can sum any iCPTerm over a given vertex and range without having to know what type of term it is.

The core .dll provides an interface that supports functions such as:

Expand - Expand all terms containing a specific vertex, to prepare it for summing.

Sum - The sum operation that is the core of CPs.

Add - Add two expressions (two iCPTerms).

Multiply - Multiply two expressions.

Solve - Finds a solution value for each of the vertices, which satisfies the original CP.

ExportC - Exports a C function equivalent to the given CP.

The scripting interface

To allow me to write CPs in text and specify commands to perform on them, I wrote the world’s worst scripting interface. It supports the following syntax:

VARIABLE = TEXT - This lets me write a CP as text and assign it a name. I’m a programmer by trade, so I’m used using variable to say-what-I-mean.

VARIABLE = FUNCTION() – This calls the core CP engine to perform a function and stores the result as a variable. The most common functions are GetExpression(), which cues the scripting interface to convert a text CP expression to programmatic objects and SumOver(), which performs a summation on the given vertices.

PRINT … - Prints text and expressions.

INCLUDE filename - Inserts the contents of another file in this location.

Function() - I can add functions to a dictionary of keywords and associated functions, such as expand(), solve(), multiply(), etc.

The scripting interface takes a text file and turns it into a stream of tokens. Then a higher level process interprets the tokens and converts them to named variables to be stored and commands to be executed on them.

The scripting interface can understand the δ and σ characters, but since it can be tedious to try to write special characters in plaintext, it also accepts “delta” or “d” for “δ” and “sigma” or “s” for “σ”.

Both the CPE engine and the scripting interface are available as .dlls. One wrapper application, CPECommand, will take command-line arguments and execute a CP script.

Another application, CPETests, runs all my unit tests.

This leaves the solution open for additional projects which use the CP engine or scripting interface for one-off applications like poker, or logic puzzles.

Sample script

I give my CP script files the .cps extension (“Chromatic Polynomial Script”). This isn’t required, since they are plaintext files. This sample script takes the expression δσ_2{1,2}  (1 - δ_σ1σ2) (1 - δ_σ1σ3) * (1 - δ_σ2σ3) and sums all vertices from 1 to 3:

Formula = GetExpression( δσ2{1,2} * (1 - δσ1σ2) * (1 - δσ1σ3) * (1 - δσ2σ3));
Solutions = SumOver(Formula, σ1-σ3, 3);
Print "Formula =" Formula;
Print "Solutions =" Solutions;

Will produce this output:

Formula = ds2{1,2}(1 - ds1s2)(1 - ds1s3)(1 - ds2s3)
Solutions = 4

Previous Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 03 – Expanding the Capabilities

This article outlines modifications that I came up with to expand Chromatic Polynomials into a fully-capable language of logic.Constants instead of variablesThe traditional Kronecker Delta compares two variables, e.g. δij compares i and j. We could just as easily replace one of those variables with a constant value:This changes the rules for summation a little bit:That is, of all the values that i can take, only one will be 3. This allows us to specify that a vertex must match a specific value,

Next Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 05 – Counting Quoridor Fence Arrangements

In this article, I showed how to calculate the number of ways that walls can be placed in the game of Quoridor (please see that article for a description of the game). Now I will show how to do it with CPs.We will define one vertex for each intersection where a wall can be placed, σ0 through σ63. The first row contains σ0 through σ7, from left to right. The second row contains σ8 through σ15, and so on:Named ConstantsEach vertex can take one of three values – no fence (or an empty intersection),