Constraint Networks

A constraint network represents a mathematical relationship between several variables, and is able to compute the value of any one of these variables given the values of all the others.

There are two types of nodes in a constraint network: cells and constraints. Cells represent variables (read-only cells represent constants) and constraints represent primitive mathematical relationships such as z = x + y and z = x * y. The neighbors of a constraint are the cells that it constrains. The neighbors of a cell are the constraints that constrain it.

A number can be saved to or erased from a cell. In either case, the cell's neighboring constraints will be notified. Upon notification that a neighboring cell has been erased, a constraint erases all of its neighbors. Upon notification that a number has been stored in a neighboring cell, a constraint attempts to compute new values for its remaining neighbors. In either case, cells updated by a constraint notify the other constraints they are connected to. In this way cell updates cascade through the network.

For example, assume x, y, and z are cells connected to an addition constraint. If a number is stored in x, and if y already holds a number, then the adder constraint stores x + y in z. However, if y doesn't hold a value, but z does, then the adder constraint stores z – x in y. Contrast this "bi-directional" behavior with the "uni-directional" behavior of the ordinary assignment statement:

z = x + y;

which only assigns x + y to z.

As a more complex example, consider the relationship:

z = 3x + 4y

We can represent this as a constraint network consisting of three constraints and seven cells:

In this network the cells labeled 3 and 4 are constant or read-only cells. The cells labeled 3x and 4y hold 3 * x and 4 * y. The nodes labeled + and * are constraints.

Assume x = 2 and y is undefined. In this case 3x = 6 and 4y is undefined. Assume 26 is stored in z. The adder constraint stores 26 – 6 = 20 in 4y. At this point the right multiplier constraint stores 20/4 = 5 in y.

ConNet

Our constraint network is called ConNet. The implementation is based on [AbS].[1] ConNet's console executes the following commands:

-> help­
help (displays this message)­
quit (terminates session)­
set NAME VALUE (update a variable cell)­
addVar NAME (add a variable cell)­
addConst NAME VALUE (add a constant cell)­
display NAME (display a cell)­
undisplay NAME (undisplay a cell)­
addAdder ARG1 ARG2 RESULT (add an adder constraint)­
addMult ARG1 ARG2 RESULT (add a multiplier constraint)­
clear (get rid of all cells & constraints)­
forgetAll (forget all cell values)­
forget NAME (forget a cell value)

Let's program ConNet to solve the equation:

z = 3x + 4y

We begin by creating three cells representing the variables x, y, and z:

-> addVar x­
done­
-> addVar y­
done­
-> addVar z­
done

Next, we create two cells that hold the constants 3 and 4, as well as two cells to hold the intermediate values of 3x and 4y:

-> addConst 3 3­
done­
-> addConst 4 4­
done­
-> addVar 3x­
done­
-> addVar 4y­
done

We create three constraints. The first asserts that 4y holds the product of 4 and y, the second asserts that 3x holds the product of 3 and x, and the third asserts that z holds the sum of 3x and 4y:

-> addMult y 4 4y­
done­
-> addMult x 3 3x
done
-> addAdder 3x 4y z­
done

Normally, cells are updated quietly. If we want a cell to display itself when it is updated, we must explicitly ask it to do so. In our example, we are only interested in the values held by x, y, and z:

-> display x­
done­
-> display y­
done­
-> display z­
done

Suppose we want to compute y assuming x = 3.14 and z = 9. In this case

y = (z – 3x)/4 = (9 – 3 * 3.14)/4 = -0.105

To do this, we simply set x to 3.14 and z to 9:

-> set x 3.14­
x = 3.14­
done­
-> set z 9­
z = 9­
y = -0.105­
done

Next, let's compute z assuming x = 5 and y = 3. In this case:

z = 3x + 4y = 3 * 5 + 4 * 3 = 27

We begin by erasing the current values held by x, y, z, 3x, and 4y:

-> forgetAll­
forgetting x­
forgetting y­
forgetting z­
done

Of course only x, y, and z inform us that they have forgotten their values. This is because we have display turned off for 3x and 4y. Finally, we set x to 5 and y to 3:

-> set x 5­
x = 5­
done­
-> set y 3­
y = 3­
z = 27­
done

Design

A constraint network is an instance of the ConNet class. A constraint network maintains a collection of cells and a collection of constraints. There can be many types of constraints: adders, multipliers, subtractors, dividers, etc. Each constraint maintains a collection of links to its neighboring cells and controls the values those cells may hold. However, a cell has no direct knowledge of its neighboring constraints. Instead, the Publisher-Subscriber pattern is used. Cells are publishers and neighboring constraints are subscribers. The user interface is provided through a command line console linked to the constraint network:

For example, a constraint network representing the equation:

z = x + y

would look like this in memory:

The following sequence diagram shows the constraint network setting the value of x then the value of y:

After the value of x is set, the adder is updated, but the adder does nothing because neither y nor z holds a value. After y is set, the adder is again updated. Now two of its three neighbors holds values, so the adder sets the value of z to x + y.