#include
/*
* This program generates every thrackle embedding of a cycle of given order
* and lists the types of sequences of 4-paths that occur.
*
* The code compiles with cc and gcc.
*
* Envocation: 1. a.out -- prompts for order 2. a.out n -- order is n
*
* Possibly necessary changes: Definition of defines
* short_int
* long_int
* INLINE
* following this comment. Also, with a powerful machine, max_n can be
* increased to look at the types for cycles of order > 12 (current value).
* My machine takes several days with n=12.
*
*
* Method:
*
* High level: A backtracking search is conducted, starting off with two lines
* drawn in the plane. Line after line is being added, until n many lines are
* drawn. Each line is drawn to intersect the previous lines just once.
* Obviously the immediate predecessor of a line is already intersected in
* the shared point. After each intersection there is a number of
* possibilities for continuing the line. This defines the search tree.
*
* Lower level: With a thrackle embedding associate a planar embedding of the
* following simple graph: The set of vertices is the collection of spots
* plus the collection of intersections. Two vertices are connected by an
* edge, if in the embedding the corresponding spots/intersections are
* adjacent.
*
* With this planar embedding associate a rotation scheme. A rotation scheme
* assigns to every vertex a cyclic permutation of its neighbours. This
* permutation specifies the arrangement in a fixed orientation (e.g.
* counterclockwise) of the edges incident on the vertex in the embedding.
*
* The search mentioned above is a search for the rotation schemes of thrackle
* embeddings of the cycle of given order. Once one is found, it is evaluated
* in respect to the sequence of 4-paths it realizes.
*
* The possiblities of continuation of a line are given by the face in which the
* current end of the line is situated. Intersecting an edge of this face
* constitutes a branch in the search tree.
*
* Note: The vertices here either have degree 2 (if they correspond to a spot)
* or degree 4 (if they correspond to an intersection).
*/
#define short_int short int
#define long_int long int
#define INLINE inline
short_int n; /* The cycle order */
#define TRUE (1==1)
#define FALSE !TRUE
/* For dimensions of arrays: */
#define max_n 12
#define max_intersections (max_n*max_n-3*max_n)/2 + 1
#define max_vertices max_n+max_intersections
#define max_types 500
short_int vertex_sees[max_vertices][4]; /* gives rotation scheme.
* Convention: Spots have
* numbers less than n,
* intersections of lines
* have numbers >= n. Line x
* goes from spot x to spot
* x+1. */
short_int line_between_vertices[max_vertices][max_vertices];
/* Two vertices that are adjacent lie on one line. */
long_int embedding_counter;
/* Subroutine prototypes */
void generate_and_evaluate_cycles (void);
void pass_through (void);
void define_new_spot(void);
void check_if_cycle_found(void);
void pull_back (void);
void evaluate_type_of_cycle (void);
/* To determine i such that vertex_sees[x][i]=y : */
INLINE short_int
index_of_vertex_sees(x, y)
short_int x;
short_int y;
{
short_int i;
for (i = 0; vertex_sees[x][i] != y; i++);
return (i);
}
/* Variables for keeping track of the types found */
short_int types[max_types][max_n]; /* store types found */
long_int type_count[max_types]; /* how often each type occurs */
long_int first_cycle_of_type[max_types]; /* to be able to find
* examples of types */
short_int last_type = 0;
/* The variables for the search for embeddings: */
short_int last_intersection; /* refers to the extension of lines. */
short_int present_line, partial_line; /* which line is presently
* being drawn; how many
* lines have been
* intersected by this line
* so far */
short_int left, right; /* give left vertex and right vertex of the
* line to be intersected. */
short_int line; /* The line on which left and right lie */
short_int right_end_vertex[max_n][max_n];
short_int left_end_vertex[max_n][max_n];
/*
* Once a line is intersected the search is continued through each edge of
* the face entered. The variables left and right "walk around this face".
* right_end_vertex and left_end_vertex are used to store when this "walk" is
* completed. Indexed by present_line and partial_line (backtrack search)
*/
short_int is_not_finished = TRUE; /* refers to the complete search */
short_int pull_back_counter = 0; /* refers to pulling line back out of
* the current face. Might have to
* pull back once or twice. */
short_int intersected_lines[max_n]; /* which lines have been
* intersected by the current
* line */
/****************************************************************************/
void
main(argc, argv)
int argc;
char *argv[];
{
int i, j;
/* read n either from command line or stdin */
if (argc < 2) {
int nn;
printf("Enter order (5..%d):", max_n);
scanf("%d", &nn);
n = (short_int) nn;
} else
n = atoi(argv[1]);
/* Catch too large input */
if (n > max_n) {
printf("\n Error:Order is too large; recompile with greater max_n\n");
exit();
} else
printf("Order is %d\n", n);
if (n < 5) {
printf("Error: Order must be greater than 4\n");
exit();
}
generate_and_evaluate_cycles();
/* Give summary of findings: */
printf("Embeddings of cycles with %d lines: %d\n", n, embedding_counter);
printf("Types of sequences of 4-paths: %d\n", last_type);
for (i = 0; i < last_type; i++) {
printf("Cycle %5d of type %3d (occuring %5d times)",
first_cycle_of_type[i], i + 1, type_count[i]);
for (j = 0; j < n; j++)
switch (types[i][j]) {
case -1:
printf(" -");
break;
case 0:
printf(" 0");
break;
case 1:
printf(" +");
break;
default:
printf("ERROR");
break;
}
printf("\n");
}
} /* end of main() */
/****************************************************************************
* For the "walk around a face"
Set left and right accordingly.
Special case is when left or right are endpoints of a line.
*/
#define DETERMINE_NEXT_PARTIAL_LINE { short_int i; \
i = index_of_vertex_sees(left,right); \
if (i==0) \
{if (left < n) \
{ right=left; left = vertex_sees[left][1];} \
else \
{ right=left; left = vertex_sees[left][3];}} \
else \
{ right=left; left = vertex_sees[left][i-1];} \
} \
/****************************************************************************/
void
generate_and_evaluate_cycles(void)
{
short_int i, j;
/* initialization */
embedding_counter = 0;
/* To start, actually set up two connected lines to start with */
vertex_sees[0][0] = 1;
vertex_sees[0][1] = 1;
vertex_sees[1][0] = 0;
vertex_sees[1][1] = 2;
vertex_sees[2][0] = 1;
vertex_sees[2][1] = 1;
line_between_vertices[0][1] = 0;
line_between_vertices[1][0] = 0;
line_between_vertices[1][2] = 1;
line_between_vertices[2][1] = 1;
present_line = 2;
partial_line = 0;
last_intersection = n - 1; /* So the first (real) intersection
* of the search is n */
for (i = 0; i < n; i++)
intersected_lines[i] = 0;
intersected_lines[2] = 1;
intersected_lines[1] = 1; /* line 2 is being drawn, and so
* don't want to intersect it. Line 1
* is intersected in point 2 */
left = 0; /* First edge to pass through */
right = 1;
right_end_vertex[2][0] = 1; /* specifies Last edge to pass
* through */
left_end_vertex[2][0] = 2;
/* The main loop! */
while (is_not_finished) {
line = line_between_vertices[left][right];
/* is it possible to pass through */
if (intersected_lines[line] == 0)
/* yes: */
pass_through();
else { /* cannot cross the stretch (left, right) */
if ((left == left_end_vertex[present_line][partial_line]) &&
(right == right_end_vertex[present_line][partial_line]))
/*
* have reached the end of the current
* walk around the face.
*/
pull_back_counter = 1;
else /* walk around the face */
DETERMINE_NEXT_PARTIAL_LINE;
} /* end else (crossing not possible) */
/*
* note : pull_back_counter is either set 4 lines above, or within
* pass_through(), when the last line has been completed, and either an
* embedding was found, or the impossibility of being able to extend to
* anembedding was detected.
*/
if (pull_back_counter > 0) {
while (pull_back_counter)
pull_back();
DETERMINE_NEXT_PARTIAL_LINE;
}
} /* end while is not finished */
} /* end generate_and_evaluate_cycles */
/****************************************************************************/
void
pass_through(void)
{ /* Updates the tables for passing through the
* stretch between vertex left and vertex
* right on the line specified by the variable line */
short_int i, j;
/*
* adjust the list for the right/left vertex of the crossed line
*/
#define index_left_right index_of_vertex_sees(left,right)
#define index_right_left index_of_vertex_sees(right,left)
vertex_sees[left][index_left_right] = last_intersection + 1;
vertex_sees[right][index_right_left] = last_intersection + 1;
if ((left == 0) || (right == 0)) vertex_sees[0][1] = vertex_sees[0][0];
/* Special treatment necessary */
/*
* adjust the list of the previous and present intersection if
* necessary
*/
if (partial_line > 0)
vertex_sees[last_intersection][3] = last_intersection + 1;
vertex_sees[last_intersection + 1][0] = left;
if (partial_line == 0) {
vertex_sees[last_intersection + 1][1] = present_line;
vertex_sees[present_line][1] = last_intersection + 1;
} else
vertex_sees[last_intersection + 1][1] = last_intersection;
vertex_sees[last_intersection + 1][2] = right;
line_between_vertices[last_intersection + 1][left] = line;
line_between_vertices[last_intersection + 1][right] = line;
line_between_vertices[left][last_intersection + 1] = line;
line_between_vertices[right][last_intersection + 1] = line;
if (partial_line == 0) {
line_between_vertices[last_intersection + 1][present_line] = present_line;
line_between_vertices[present_line][last_intersection + 1] = present_line;
} else if (partial_line < present_line - 1) {
line_between_vertices[last_intersection + 1][last_intersection] =
present_line;
line_between_vertices[last_intersection][last_intersection + 1] =
present_line;
}
partial_line++;
intersected_lines[line] = 1;
/*
* adjust list of which line an intersection belongs to
*/
/* special case is when we define a new spot: */
if ((partial_line == present_line - 1) && (present_line < n - 1))
define_new_spot();
else { /* we don't define a new spot. */
/*
* store when the next walk around the face will be complete.
*/
left_end_vertex[present_line][partial_line] = last_intersection + 1;
right_end_vertex[present_line][partial_line] = left;
}
if ((partial_line == present_line - 2) && (present_line == n - 1))
/*
* the current scheme is a candidate for a cycle, provided we
* can connect the two, still open, ends.
*/
check_if_cycle_found();
last_intersection++;
/* initialize last/right for new search.. */
left = right;
right = last_intersection;
} /* end pass_through */
/****************************************************************************/
void
define_new_spot(void)
{ short_int i;
line_between_vertices[last_intersection + 1][present_line + 1] = present_line;
line_between_vertices[present_line + 1][last_intersection + 1] = present_line;
/*
* first adjust what the last_intersection and the new vertex sees
*/
vertex_sees[last_intersection + 1][3] = present_line + 1;
vertex_sees[present_line + 1][0] = last_intersection + 1;
vertex_sees[present_line + 1][1] = last_intersection + 2;
/* then other vars */
present_line++;
partial_line = 0;
/*
* store when the next walk around the face will be complete.
*/
left_end_vertex[present_line][partial_line] = present_line;
right_end_vertex[present_line][partial_line] = last_intersection + 1;
/*
* which lines are to be intersected by the next one?
*/
for (i = 0; i < n; i++)
intersected_lines[i] = 0;
intersected_lines[present_line] = 1;
intersected_lines[present_line - 1] = 1;
if (present_line == n - 1)
intersected_lines[0] = 1;
}
/******************************************************************************/
void
check_if_cycle_found(void)
{
short_int i, l, r;
l = last_intersection + 1;
r = vertex_sees[l][2];
/*
* determine whether we can close by identifying the present line and
* 0
*/
/* Another face walk! */
while ((r != last_intersection + 1)
&& (r != 0)) {
i = index_of_vertex_sees(r, l);
if (i == 0) {
if (r < n) {
l = r;
r = vertex_sees[r][1];
} else {
l = r;
r = vertex_sees[r][3];
}
} else {
l = r;
r = vertex_sees[r][i - 1];
}
}
if (r == 0)
/*
* identification possible. Evaluate cycle.
*/
{
embedding_counter++;
/*
* complete the table first ! Has to be undone after
* completion of evaluate_type_of_cycle
*/
vertex_sees[0][1] = last_intersection + 1;
vertex_sees[last_intersection + 1][3] = 0;
line_between_vertices[last_intersection + 1][0] = n - 1;
line_between_vertices[0][last_intersection + 1] = n - 1;
evaluate_type_of_cycle();
vertex_sees[0][1] = vertex_sees[0][0];
pull_back_counter = 2;
} else
pull_back_counter = 1; /* Failed. */
}
/*****************************************************************************/
void
pull_back(void)
{
short_int i, j;
while (pull_back_counter) /* pull back as often as
* pull_back_counter says. */
if ((present_line == 2) && (partial_line == 0)) { /* The end of the search
* for cycles of order n
* is reached when we
* want to pull back the
* line 1. */
is_not_finished = FALSE;
pull_back_counter = 0; /* No need to work anymore.*/
} else { /* first find left and right vertexs of the
* last intersection */
left = vertex_sees[last_intersection][0];
right = vertex_sees[last_intersection][2];
/* adjust vertex_sees - table */
#define indexllast index_of_vertex_sees(left,last_intersection)
#define indexrlast index_of_vertex_sees(right,last_intersection)
vertex_sees[left][indexllast] = right;
vertex_sees[right][indexrlast] = left;
/*
* different assignments when pulling back close to
* 0!
*/
if (left == 0) {
vertex_sees[0][0] = right;
vertex_sees[0][1] = vertex_sees[0][0];
}
if (right == 0) {
vertex_sees[0][0] = left;
vertex_sees[0][1] = vertex_sees[0][0];
}
/*
* determine the line of the left-right vertex
*/
line = line_between_vertices[left][last_intersection];
line_between_vertices[left][right] = line;
line_between_vertices[right][left] = line;
/* intersected_lines has to be changed: */
intersected_lines[line] = 0;
if (partial_line > 0) { /* we are only deleting an
* intersection */
partial_line--;
} else
/* we are deleting a spot! */
{
present_line--;
partial_line = present_line - 2;
/* set up intersected lines */
for (i = 0; i < present_line - 1; i++)
intersected_lines[i] = 1;
intersected_lines[line] = 0;
intersected_lines[present_line] = 1;
intersected_lines[present_line - 1] = 1;
if (present_line == n - 1)
intersected_lines[0] = 1;
}
last_intersection--;
if ((left != left_end_vertex[present_line][partial_line]) ||
(right != right_end_vertex[present_line][partial_line]))
/*
* When we pull back such that the previous
* face walk is finished we pull back once
* more, by not decreasing pull_back to 0
*/
pull_back_counter--;
} /* end else */
} /* end pull_back */
/****************************************************************************/
void
evaluate_type_of_cycle(void)
{
short_int i, j, previous, next, line;
short_int t[max_n]; /* for the current type */
short_int behind[max_intersections]; /* as one follows the
* embedding starting at
* point 0, following
* the first line, then
* the second etc. one
* passes all
* intersections in a
* certain order. This
* information is stored
* in this array. */
short_int oriented_line_between_vertices[max_vertices][max_vertices]; /* as one follows the
* embedding starting at
* point 0, following
* the first line, then
* the second etc. one
* passes all stretches
* between two
* neighbouring
* vertices. If a,b are
* neighbours, does one
* first pass a or b?
* Information stored in
* this array. */
short_int o;
short_int first, first_orientation, second_orientation;
short_int different, different_from_this_type, offset;
short_int store_type;
/* initialization */
for (i = 0; i < max_intersections; i++)
behind[i] = -1;
/*
* First set up the array "oriented_line_between_vertices."
*/
for (i = 0; i < n; i++) {
line = i;
previous = i;
for (j = 0; j < 2; j++)
if (line_between_vertices[i][vertex_sees[i][j]] == line) {
next = vertex_sees[i][j];
break;
}
while (next >= n) {
if (behind[next] != -1) {
if (vertex_sees[next][(index_of_vertex_sees(next, previous) + 1) % 4] ==
behind[next]) {
oriented_line_between_vertices[next]
[line_between_vertices[next][behind[next]]] =
1 + line_between_vertices[next][previous];
oriented_line_between_vertices[next]
[line_between_vertices[next][previous]] =
(-1) * (1 + line_between_vertices[next][behind[next]]);
} else {
oriented_line_between_vertices[next]
[line_between_vertices[next][behind[next]]] =
(-1) * (1 + line_between_vertices[next][previous]);
oriented_line_between_vertices[next]
[line_between_vertices[next][previous]] =
(1 + line_between_vertices[next][behind[next]]);
}
}
behind[next] = previous;
for (j = 0; j < 4; j++)
if ((line_between_vertices[next][vertex_sees[next][j]] == line) &&
(vertex_sees[next][j] != previous)) {
previous = next;
next = vertex_sees[previous][j];
break;
}
}
}
/*
* Now find out what type every part-line has. E.g. whether it is if
* type 0,+ or -.
*/
for (i = 0; i < n; i++) {
first_orientation = 0;
second_orientation = 0;
previous = i;
line = i;
first = 0;
for (j = 0; j < 2; j++)
if (line_between_vertices[i][vertex_sees[i][j]] == line) {
next = vertex_sees[i][j];
break;
}
while ((next > n - 1)) {
if (oriented_line_between_vertices[next]
[line_between_vertices[next][previous]] > 0)
o = 1;
else
o = -1;
if (abs(oriented_line_between_vertices[next]
[line_between_vertices[next][previous]]) == (1 + ((i + 2) % (n))))
/* crossing 2nd line from present */
{
if (first != -1) {
first = 1;
first_orientation = o;
} else
second_orientation = o;
}
if (abs(oriented_line_between_vertices[next]
[line_between_vertices[next][previous]]) == (1 + ((i + 3) % (n))))
/* crossing 3rd line from present */
{
if (first != 1) {
first = -1;
first_orientation = o;
} else
second_orientation = o;
}
for (j = 0; j < 4; j++)
if ((line_between_vertices[next][vertex_sees[next][j]] == line) &&
(vertex_sees[next][j] != previous)) {
previous = next;
next = vertex_sees[previous][j];
break;
}
}
/*
* now first = -1 if the fourth line is crossed first, and 1
* if the third line is crossed first. first_orientation
* gives the orientation of the first crossing
* second_orientation the orientation of the second crossing.
*/
if ((first == 1) && (first_orientation == 1) && (second_orientation == 1)) {
/*
* print every sequence means for every cycle
* found priont out what type it has.
*/
t[i] = -1;
}
if ((first == 1) && (first_orientation == -1) && (second_orientation == 1)) {
t[i] = 0;
}
if ((first == 1) && (first_orientation == 1) && (second_orientation == -1)) {
t[i] = 0;
}
if ((first == 1) && (first_orientation == -1) && (second_orientation == -1)) {
t[i] = -1;
}
if ((first == -1) && (first_orientation == -1) && (second_orientation == 1)) {
t[i] = 1;
}
if ((first == -1) && (first_orientation == 1) && (second_orientation == -1)) {
t[i] = 1;
}
}
/* The type of the current cycle is determined and given in the array t.
* Now determine whether the type of the current cycle is in fact a
* new one. The array types contains the ones found so far.
*/
/*
* Assume it is different, and once we find out it is not, change
* different to FALSE.
*/
different = TRUE;
for (i = 0; (different) && (i < last_type); i++) {
store_type = i; /* This is so that we can count how often
* every type occurs. See below
* type_count..++ */
/*
* Now we compare the new type with the i-th type shifted by
* offset.
*/
different_from_this_type = TRUE;
for (offset = 0; (different_from_this_type) && (offset < n); offset++)
for (j = 0; (j < n); j++) {
if (t[(j + offset) % n] != types[i][j]) {
different_from_this_type = TRUE;
break;
}
different_from_this_type = FALSE;
}
if (!different_from_this_type)
different = FALSE;
else { /* we compare the newly found type with the
* i-th type walked backwards. */
for (offset = 0; (different_from_this_type) && (offset < n); offset++)
for (j = 0; (j < n); j++) { /* compare backwards */
if (((-1) * t[(j + offset) % n]) != types[i][(2 * n - j) % n]) {
different_from_this_type = TRUE;
break;
}
different_from_this_type = FALSE;
}
if (!different_from_this_type)
different = FALSE;
} /* end else */
} /* end for i.. */
if ((different) || (last_type == 0)) {
if (last_type == max_types) {
printf("\n-----------\nToo many types\n----------\n");
exit();
} else {
printf("Type %2d Cycle %6d:", last_type + 1, embedding_counter);
for (i = 0; i < n; i++) {
types[last_type][i] = t[i];
switch (t[i]) {
case -1:
printf(" -");
break;
case 0:
printf(" 0");
break;
case 1:
printf(" +");
break;
default:
printf("ERROR");
break;
}
}
first_cycle_of_type[last_type] = embedding_counter;
type_count[last_type] = 1;
printf("\n");
last_type++;
}
/* Print how to draw every new type of cycle.. */
for (i = 0; i < n; i++) {
line = i;
printf("For vertex %2d, along line %2d: ", i + 1, i + 1);
previous = i;
for (j = 0; j < 2; j++)
if (line_between_vertices[i][vertex_sees[i][j]] == line) {
next = vertex_sees[i][j];
break;
}
while ((next > n - 1)) {
printf(" %3d ",
oriented_line_between_vertices[next][line_between_vertices[next][previous]]);
for (j = 0; j < 4; j++)
if ((line_between_vertices[next][vertex_sees[next][j]] == line) &&
(vertex_sees[next][j] != previous)) {
previous = next;
next = vertex_sees[previous][j];
break;
}
}
printf("\n");
} /* end for.. */
printf("----------------------------------\n");
} else /* count the type. */
type_count[store_type]++;
/* end for difference */
}