Reference no: EM133492444

Assignment: Linux tools, logic, regular expressions, induction

Introduction to awk

In an awk program, each line has the form
/pattern / { action }

where the pattern is a regular expression (or certain other special patterns) and the action is an instruction that specifies what to do with any line that contains a match for the pattern. The action (and the . . . around it) can be omitted, in which case any line that matches the pattern is printed. Once you have written your program, it does not need to be compiled. It can be executed di- rectly, by using the awk command in Linux:
$ awk -f programName inputFileName
Your program is then executed on an input file in the following way.
// Initially, we're at the start of the input file, and haven't read any of it yet.

If the program has a line with the special pattern BEGIN, then do the action specified for this pattern.
Main loop, going through the input file:

inputLine := next line of input file Go to the start of the program.
Inner loop, going through the program:

programLine := next line of program (but ignore any BEGIN and END lines) if inputLine contains a string that matches the pattern in programLine, then
if there is an action specified in the programLine, then
do this action
else
just print inputLine // it goes to standard output
}
}
If the program has a line with the special pattern END, then do the action specified for this pattern.
Any output is sent to standard output.
You should read about the basics of awk, including
• the way it represents regular expressions,
• the variables $1, $2, etc., and NR,
• the function printf(• • • ),
• for loops. For these, you will only need simple loops like

for (i = 1; i <= n; i++)
{
?body of loop?
}

This particular loop executes the body of the loop once for each i = 1, 2, . . . , n (unless the body of the loop changes the variable i somehow, in which case the behaviour may be different, but you should not need to do that). You can nest loops, so the body of the loop can be another loop. It's also ok to write loops more compactly,
for (i = 1; i <= n; i++) { ?body of loop? }
although you should ensure it's still clearly readable.
Any of the following sources should be a reasonable place to start:

• A. V. Aho, B. W. Kernighan and P. J. Weinberger, The AWK Programming Language, Addison-Wesley, New York, 1988.
(The first few sections of Chapter 1 should have most of what you need, but be aware also of the regular expression specification on p28.)
• https://www.grymoire.com/Unix/Awk.html
• the Wikipedia article looks ok
• the awk manpage
• the GNU Awk User's Guide.

Introduction to Problems

Many systems and structures can be modelled as graphs (abstract networks). Many problems on these structures require allocation of some scarce resources to the objects in a network in such a way that objects that are close together do not share the same resource. For example, in timetabling, two classes with some students in common should not be scheduled in the same timeslot; in commu- nications networks, two neighbouring cellphone towers should not be assigned the same transmission frequency (to minimise interference). This wide family of problems, drawn from many different do- mains, can be modelled abstractly by graph colouring. To keep things simple for the assignment, we will only use a few colours, but in real applications the numbers of colours used can be very large. Throughout, we use G to denote a graph, n denotes its number of vertices and m denotes its number of edges.

A 3-colouring of a graph G is a function f : V (G) Red, White, Black such that adjacent vertices are given different colours by f . Here, V (G) denotes the set of vertices of G. A graph is 3-colourable if it has a 3-colouring.

For example, the graph in Figure 1(a) is 3-colourable, and an actual 3-colouring is shown for it. Note that a 3-colouring does not have to use all three available colours. The graph in Figure 1(b) is shown with a 2-colouring, using just the colours Black and White, so it is 2-colourable. It is also 3-colourable, since every 2-colouring is also a 3-colouring.

The graph in Figure 1(c) is not 3-colourable. Study it carefully and check that this assertion is correct.

In Problems 1-4, you will write a program in awk that constructs, for any graph G, a Boolean expression φG in Conjunctive Normal Form that captures, in logical form, the statement that G is 3-colourable. This assertion might be True or False, depending on G, but the requirement is that G is 3-colourable ⇐⇒ you can assign truth values to the variables of φG to make it True. For each vertex i ∈ V (G) and each colour c ∈ {Red, White, Black}, we introduce a Boolean variable vi,c. It is our intention that this represents the statement that "vertex i gets colour c"
(which might be True or False). So, for example, we want the variable v2,Red to represent the

Figure 1: Three graphs. (a) A 3-colourable graph, with a 3-colouring. (b) Another 3-colourable graph. This one is also 2-colourable. It is shown with a 2-colouring, which is also a 3-colouring. (c) A non-3-colourable graph.

statement "vertex 2 gets colour Red". But we will need to build some logic, in the form of a CNF expression, to make this interpretation work.

When we write code, each variable vi,c is represented by a name in the form of a text string vic formed by concatenating v, i and c. So, for example, v2,Red is represented by the name v2Red.

If all we have is all these variables, then there is nothing to control whether they are each True or False. Their values might not bear any relation to their intended meaning. For example, we might have v4,Red = True and v4,Black = True, meaning that vertex 4 gets two colours instead of one. Or we might have v1,Red = v1,White = v1,Black = False, meaning that vertex 1 gets no colour at all. Or we might violate the constraint that adjacent vertices get different colours: if vertices 2 and 3 are adjacent, and v2,Red = v3,Red = True, then the interpretation is that both these vertices get colour Red even though they are adjacent, which breaks the rules.

So, we need to encode the definition of 3-colourability into a CNF expression using these variables. The expression we construct must depend on the graph. Furthermore, it must depend only on the graph. Think of the graph as uncoloured: you cannot assume that any vertex gets any specific colour.

We begin with a specific example (Problem 1) and then move on to general graphs (Problems 2-4).

Problem 1.

For the graph H shown on the right (Fig. 2), construct a Boolean expression φH using the variables vi,c which is True if and only if the assignment of truth values to the variables represents a 3-colouring of H.

Now type this expression φH into a one-line text file, using our text names for the variables (i.e., v1Red, v1White, v1Black, v2Red, etc.), with the usual logical operations replaced by text versions as follows:

Put your answer in a one-line text file called prob1.txt.

Figure 2: The graph H.

For the purposes of this assignment, every graph is encoded as an edge list in the following format:

• The first line specifies the number of vertices, as a single positive integer. Let n be the number of vertices. Then the vertices of the graph are assumed to be numbered 1, 2, . . . , n.

• Each subsequent line contains a single edge, represented as i -- j

where i and j are positive integers representing the two vertices linked by the edge (with 1 ≤ i ≤ n and 1 ≤ j ≤ n).

• We allow any number of spaces before, between, and after the numbers on each line, subject to the requirement that there be at least one space on either side of the double-hyphen --.

• For example, the graph in Figure 1(a) could be represented by the six-line file on the left below, or (less neatly) by the one on the right.

 

• Each graph is represented in a file of its own. Each input file contains exactly one graph represented in this way.

• Positive integers, for n and the vertex numbers, can have any number of digits. They must have no decimal point and no leading 0.

Problem 2.

Write an awk script that takes, as input, a graph G represented in the specified format in a text file, and produces, as output, a one-line file containing the text representation of a Boolean expression φG in CNF which uses the variables we have specified and which is True if and only if the variables describe a 3-colouring of G.

The text representation is the same as that described on p4 and used for Problem 1. Put your answer in a file called prob2.awk.

Problem 3.

Give, with brief justification, an expression for the number of clauses of φG in terms of n (the number of vertices of G) and m (the number of edges of G).

For full marks, the number of clauses produced by your awk program (prob2.awk) must be correct as well as equalling the expression you give here.

Put your answer in a PDF file called prob3.pdf.

We are now going to modify the awk script so that the output it produces can be taken as input by a program for testing satisfiability.

SageMath is software for doing mathematics. It is powerful, widely used, free, open-source, and based on Python. It is already available in your Ed Workspace.1 You don't need to learn SageMath for this assignment (although it's good to be aware of what it is); you only need to follow the instructions below on how to use a specific function in SageMath for a specific task. If you're interested, you may obtain further information, including tutorials, documentation and installation instructions.

In this part of the assignment, we just use one line of SageMath via the Linux command line in order to determine whether or not a Boolean expression in CNF is satisfiable (i.e., has an assignment of truth values to its variables that makes the expression True). Suppose we have the Boolean expression

(a ∨ b) ∧ (¬a ∨ ¬b) ∧ (¬a ∨ b),

which we note is satisfiable because it can be made True by putting a = False and b = True. We first translate the expression into text in the way described earlier (p4), replacing , , by ~,&,| respectively. This gives the text string

(a | b) & (~a | ~b) & (~a | b).

We ask SageMath if this is satisfiable by entering the following text at the Linux command line:
$sage -c 'print(propcalc.formula("(a | b) & (~a | ~b) & (~a | b)").is_satisfiable())'

True

You can see that SageMath outputs True on the next line to indicate that the expression is satisfiable. Insage -c, the "-c" instructs sage to execute the subsequent (apostrophe-delimited) Sage command and output the result (to standard output) without entering the SageMath environment.

This is all you need to do to use the SageMath satisfiability test on your expression. If you want to actually enter SageMath and use it interactively, you can do so:

$sage
sage:print(propcalc.formula("(a | b) & (~a | ~b) & (~a | b)").is_satisfiable()) True

Again, the output True indicates satisfiability.

Problem 4
Copy your awk script from Problem 3 and then modify it so that, when you run it on a graph

G (with same input file as before) it creates the following one-line command:

 

So, instead of just outputting φG, we now output φG with extra stuff before and after it. The new stuff before it is the text string " sage -c 'print(propcalc.formula(" ", and the new stuff after it is the text string " ").is satisfiable())' ". These new strings don't depend on φG; they just provide what is needed to make a valid Linux command that invokes sage to test whether or not φG is satisfiable.

Put your answer in a file called prob4.awk.

You should test your prob4.awk on several different graphs and, for each, use sage, as described above, to determine if it is satisfiable. You should ensure that satisfiability φG does indeed correspond to 3-colourability of G.

Figure 3 illustrates the relationships between the files and actions involved in Problem 4.

 

Introduction to Problem 5.

A Boolean expression in CNF is slithy if, for all k 1, every set of k clauses includes a variable that appears only once among those clauses. So this condition must hold for every possible set of clauses in the expression.In counting appearances of variables among a set of clauses, we don't mind whether the variable appears in its normal or negated form; we count them all.Examples:• The expression(a ∨ b) ∧ (b ∨ ¬c) ∧ (c ∨ ¬d)is slithy. To see this, consider each k and each set of k clauses. First, consider k = 1. Each clause in the expression includes a variable that appears once in that clause (in fact, both variables in each clause appear exactly once in that clause). They might appear in other clauses too, but that doesn't matter when we consider what happens in just one specific clause. Now consider k = 2. If we take the two clauses a b and b c, we see that a appears only once among those two clauses, and the same holds for c. You can check that the other pairs of clauses have the required property too. Finally, consider k = 3. Now we have to consider all three clauses. The variable a appears only once (as does the variable d), so the condition is satisfied.

• The expression

(a ∨ b) ∧ (b ∨ ¬c) ∧ (¬a ∨ ¬c) ∧ (a ∨ ¬d)

is not slithy. There are some sets of clauses that have the required property: for example, the first two clauses (being the same as before) still do. But consider the first, second and third clauses. Between them, they contain two appearances of a, two appearances of b, two appearances of c, and no appearances of any other variable. So this set of clauses does not have a variable that only appears once in those clauses.

Problem 5.

Prove, by induction on n, that a slithy Boolean expression in CNF with at most n variables has at most n clauses and is satisfiable.