Chromatic Polynomials 14 – Generating Code

Just like we can translate CPs to SAT, we can also translate CPs to code. I added the ability for my CP engine to export C-like code, compatible with C, C++, and C#, only because those are the languages I was most commonly working in when I wrote it.

I’ll cover the how to convert CPs to code first, then I’ll talk about why you might want to do this.

How to Convert CPs to Code

The addition, subtraction, and multiplication operations in CPs can be directly converted into C or C-like code. The Extended Kronecker Delta needs just a little special treatment:

Expression	C code
δσ1σ2	(sigma1 == sigma2) For C#, which returns boolean types for comparison and logical operators, we have to use: ((sigma1 == sigma2) : 1 : 0) Out of laziness, I used this form for exporting CPs to both C and C#. If I find the need to speed up my exported C code, I’ll have to add a switch to use the more efficient form for C/C++ code.
δσ1σ2σ3	((sigma1 == sigma2) && (sigma1 == sigma3)) Here, we can use the transitive property as a shortcut and omit (sigma2 == sigma3). Of course, this example can be extended to any number of vertices.
δσ1{1}	(sigma1 == 1)
δσ1{1,3}	((sigma1 == 1) || (sigma1 == 3))
δσ1{1-5}	((sigma1 >= 1) && (sigma1 <= 5))
δσ1σ2σ3{2-5,6,8-11}	((sigma1 == sigma2) && (sigma1 == sigma3) && (((sigma1 >= 2) && (sigma1 <= 5)) || (sigma1 == 6) || ((sigma1 >= 8) && (sigma1 <= 11)))

For negation of EKDs, we can encode a shortcut:

Expression	C code
(1 - δσ1σ2)	(sigma1 != sigma2)

Sample Conversion

Here is the CP for !5(Q), from the article on subfactorials and subpermutations:

Here is the C code generated by my CP engine:

uint subpermutation5of5(uint s1, uint s2, uint s3, uint s4, uint s5)
{
    return (((s1 >= 2) && (s1 <= 5)) ? 1 : 0) * (((s2 == 1) || ((s2 >= 3)
            && (s2 <= 5))) ? 1 : 0) * (((s3 == 1) || (s3 == 2)
            || (s3 == 4) || (s3 == 5)) ? 1 : 0) * ((((s4 >= 1)
            && (s4 <= 3)) || (s4 == 5)) ? 1 : 0) * (((s5 >= 1)
            && (s5 <= 4)) ? 1 : 0) * (1 -((s1 == s2) ? 1 : 0))
            * (1 -((s1 == s3) ? 1 : 0)) * (1 -((s1 == s4) ? 1 : 0))
            * (1 -((s1 == s5) ? 1 : 0)) * (1 -((s2 == s3) ? 1 : 0))
            * (1 -((s2 == s4) ? 1 : 0)) * (1 -((s2 == s5) ? 1 : 0))
            * (1 -((s3 == s4) ? 1 : 0)) * (1 -((s3 == s5) ? 1 : 0))
            * (1 -((s4 == s5) ? 1 : 0));
} 

Since this function takes one concrete value for every vertex, it is a checker function, returning 1 if the values define a derangement and 0 if they don’t.

We can generate a completing function by summing over the vertices that we don’t want to provide values for. Let’s say that σ₁, σ₂, and σ₃ will be given, and σ₄ and σ₅ are unknown. We sum over them with:

Tip: You don’t have to read this whole thing - or the code that follows. I didn’t even write it. I just wrote the SubPermutation5 expression above, and let my CP Engine generate the rest. It's okay to say, "That's a lot" and skip to the next section.

And the corresponding code. This function will take three values, s1, s2, and s3, and tell how many ways there are to complete the subpermutation:

uint SubPermutation3of5InQ(uint s1, uint s2, uint s3, uint Q)
{
    return (1 -((s1 == 1) ? 1 : 0)) * (1 -((s1 == s2) ? 1 : 0)) * (1 -((s1 == s3) ? 1 : 0)) * (1 -((s2 == 2) ? 1 : 0)) * (1 -((s2 == s3) ? 1 : 0)) * (1 -((s3 == 3) ? 1 : 0)) * (21 -9 * Q + pow(Q, 2) -5 * ((s1 == 5) ? 1 : 0) -4 * ((s1 == s2) ? 1 : 0) + 5 * ((s1 == s2) && (s1 == 5) ? 1 : 0) + 4 * ((s1 == s2) && (s1 == s3) ? 1 : 0) -5 * ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) -4 * ((s1 == s3) ? 1 : 0) + 5 * ((s1 == s3) && (s1 == 5) ? 1 : 0) -5 * ((s2 == 5) ? 1 : 0) -4 * ((s2 == s3) ? 1 : 0) + 5 * ((s2 == s3) && (s2 == 5) ? 1 : 0) -5 * ((s3 == 5) ? 1 : 0) + ((s1 == 4) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) + ((s1 == s2) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) -((s1 == s2) && (s1 == 4) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) -((s1 == s2) && (s1 == s3) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) + ((s1 == s2) && (s1 == s3) && (s1 == 4) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) + ((s1 == s3) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) -((s1 == s3) && (s1 == 4) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) + ((s2 == 4) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) + ((s2 == s3) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) -((s2 == s3) && (s2 == 4) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) + ((s3 == 4) ? 1 : 0) * (-5 + Q + ((s1 == 5) ? 1 : 0) + ((s1 == s2) ? 1 : 0) -((s1 == s2) && (s1 == 5) ? 1 : 0) -((s1 == s2) && (s1 == s3) ? 1 : 0) + ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + ((s1 == s3) ? 1 : 0) -((s1 == s3) && (s1 == 5) ? 1 : 0) + ((s2 == 5) ? 1 : 0) + ((s2 == s3) ? 1 : 0) -((s2 == s3) && (s2 == 5) ? 1 : 0) + ((s3 == 5) ? 1 : 0)) + Q * ((s1 == 5) ? 1 : 0) + Q * ((s1 == s2) ? 1 : 0) -Q * ((s1 == s2) && (s1 == 5) ? 1 : 0) -Q * ((s1 == s2) && (s1 == s3) ? 1 : 0) + Q * ((s1 == s2) && (s1 == s3) && (s1 == 5) ? 1 : 0) + Q * ((s1 == s3) ? 1 : 0) -Q * ((s1 == s3) && (s1 == 5) ? 1 : 0) + Q * ((s2 == 5) ? 1 : 0) + Q * ((s2 == s3) ? 1 : 0) -Q * ((s2 == s3) && (s2 == 5) ? 1 : 0) + Q * ((s3 == 5) ? 1 : 0));
}

Why convert to code?

Any function that the CP math can perform can be converted to code to run more efficiently. If an application needs to perform a single CP function multiple times given different inputs, exporting the CP to code is an efficient way to do this.

Let’s see how this can apply to each of the CP functions.

Counting

The counting function of a CP uses the polynomial after all summations have been performed. If summing over a fixed range, the sum is a constant. For example, the subfactorial CP above, when its vertices are summed from 1 to 5, yields 44. There’s not much use in converting this to code:

int SubfactorialOf5 { return 44; } // This could have been a #define

If summed from 1 to Q, this would produce Q⁵ - 15Q⁴ + 95Q³ - 325Q² + 609Q - 501. That’s marginally more useful:

Int SubPermutation5InQ(int Q) {

    return Q < 5 ? 0 : (((((Q - 15)* Q + 95)*Q - 325)*Q + 609)Q - 501);

}

In general, though, once a CP has been summed, there isn’t much to be gained by converting it to code.

Completing

The completing function uses some vertices set to fixed values and sums over the remaining vertices. The result is the number of ways that the CP can be completed. As shown above, we can select any vertices to sum over and export a function for the remaining vertices:

uint SubPermutation5of5 (uint s1, uint s2, uint s3, uint s4, uint s5);
uint SubPermutation4of5InQ (uint s1, uint s2, uint s3, uint s4, uint Q);
uint SubPermutation3of5InQ (uint s1, uint s2, uint s3, uint Q);
uint SubPermutation2of5InQ (uint s1, uint s2, uint Q);
uint SubPermutation1of5InQ (uint s1, uint Q);
uint SubPermutationQ(uint Q);

We can use these functions to test any incomplete selection of vertices. If the result is 0, then the selection is invalid. If the result is greater than zero, it tells us how many ways there are to select values for the remaining vertices.

Checking

As shown above, when we fill in all of the vertices with fixed values, we get a checking function.

uint subpermutation5of5(uint s1, uint s2, uint s3, uint s4, uint s5)
{
    return (((s1 >= 2) && (s1 <= 5)) ? 1 : 0)  (((s2 == 1) || ((s2 >= 3) && (s2 <= 5))) ? 1 : 0)  (((s3 == 1) || (s3 == 2) || (s3 == 4) || (s3 == 5)) ? 1 : 0)  ((((s4 >= 1) && (s4 <= 3)) || (s4 == 5)) ? 1 : 0)  (((s5 >= 1) && (s5 <= 4)) ? 1 : 0)  (1 -((s1 == s2) ? 1 : 0))  (1 -((s1 == s3) ? 1 : 0))  (1 -((s1 == s4) ? 1 : 0))  (1 -((s1 == s5) ? 1 : 0))  (1 -((s2 == s3) ? 1 : 0))  (1 -((s2 == s4) ? 1 : 0))  (1 -((s2 == s5) ? 1 : 0))  (1 -((s3 == s4) ? 1 : 0))  (1 -((s3 == s5) ? 1 : 0))  (1 -((s4 == s5) ? 1 : 0));
}

This function returns either a 0, meaning that vertices do not meet the criteria set by the CP, or a 1, meaning they do.

Solving

Solving a CP programmatically involves iteratively calling various Completion functions. Solving code could look something like this:

bool Solve(int Q, int s1, int s2, int s3, int s4, int *s5) {
    if (!SubPermutationQ (Q))
       return false; // No solution exists.
 
    // Find a value for s1.
    for (*s1 = 1; (*s1 <= Q) && !SubPermutation1of5InQ (*s1, Q); ++*s1);
 
    // Find a value for s2, given s1.
    for (*s2 = 1; (*s2 <= Q) && !SubPermutation2of5InQ (*s1, s2, Q); ++s2);
 
    // Find a value for s3, given s1 and s2.
    for (*s3 = 1; (*s3 <= Q) && !SubPermutation3of5InQ (*s1, s2, s3, Q); ++*s3);
 
    // Find a value for s4, given s1, s2, and s3.
    for (*s4 = 1; (*s4 <= Q) && !SubPermutation4of5InQ (*s1, s2, s3, s4, Q); ++s4);
 
    // Find a value for s5, given s1, s2, s3, and s4.
    for (*s5 = 1; (*s5 <= Q) && !SubPermutation4of5InQ (*s1, s2, s3, s4, s5, Q); ++*s5);

     return true; // s1 through s5 are set to a solution.
}

Iterating

Iterating on all solutions in a CP requires the same Completion functions that the Solving function uses, but nested rather than called sequentially:

void Iterate(int Q) {
  int s1, s2, s3, s4, s5;
 
  if (!SubPermutationQ (Q))
     return; // No solutions exist.

  // Try all values for s1.
  for (s1 = 1; s1 <= Q; ++s1) {
    // If this value works, explore further.
    if (SubPermutation1of5InQ (s1, Q)) {
 
      // Try all values for s2.
      for (s2 = 1; s2 <= Q; ++s2) {
        // If this value works, explore further.
        if (SubPermutation2of5InQ (s1, s2, Q)) {

          // Try all values for s3.
          for (s3 = 1; s3 <= Q; ++s3) {
            // If this works, explore further.
            if (SubPermutation3of5InQ (s1, s2, s3, Q)) {

              // Try all values for s4.
              for (s4 = 1; s4 <= Q; ++s4) {
                // If this value works, explore further.
                if (SubPermutation4of5InQ (s1, s2, s3, s4, Q)) {
 
                  // Try all values for s5.
                  for (s5 = 1; s5 <= Q; ++s5) {
                    // If this value works, explore further.
                    if (SubPermutation5of5(s1, s2, s3, s4, s5)) {
                      ReportSolution(s1, s2, s3, s4, s5);
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

This shows how a few coded implementations of a CP can be used to programmatically implement the Counting, Completing, Checking, Solving, and Iterating functions of CP. A compiled program will run much faster than a symbolic chromatic polynomial interpreter.

Previous Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 13 – Knot Tricolorability

Tricolorability is a property used to classify and distinguish different knots. Under the rules of tricolorability, a strand is a section of a knot that goes from one undercrossing to another.The Trefoil KnotFor example, the simple trefoil knot consists of 3 strands and 3 crossings:To “tricolor” a knot, we assign a color to each strand such that in each crossing, all three strands are the same color or all three strands are a different color. There is one more constraint – that we must use at le

Next Post:

Chromatic Polynomials 15 - Coming soon