#include #include bool debug_create = false; bool debug_norm_compare = false; class VertexLabeledGraph { public: VertexLabeledGraph() : vertices(0) {} class Edge; class Vertex { public: char label; char context; int nr; Edge *out; Edge *in; Vertex *next; Vertex *first; Vertex *second; Vertex(char n_label, char n_context, int n_nr) : label(n_label), context(n_context), nr(n_nr), out(0), in(0), next(0), first(0), second(0) {} }; class Edge { public: Vertex *from; Vertex *to; Edge *next_out; Edge *next_in; bool mark; Edge(Vertex *n_from, Vertex *n_to) : to(n_to), from(n_from), mark(false) { next_out = from->out; from->out = this; next_in = to->in; to->in = this; } }; Vertex *createVertex(char label, char context) { Vertex **ref_vertex = &vertices; int nr = 0; while (*ref_vertex != 0) { ref_vertex = &(*ref_vertex)->next; nr++; } *ref_vertex = new Vertex(label, context, nr); if (debug_create) printf(" Vertex %d-%c%c\n", nr, label, context); return *ref_vertex; } Edge *addEdge(Vertex *from, Vertex *to) { for (Edge *edge = from->out; edge != 0; edge = edge->next_out) if (edge->to == to) return edge; if (debug_create) printf(" Edge %d-%c%c %d-%c%c\n", from->nr, from->label, from->context, to->nr, to->label, to->context); return new Edge(from, to); } void removeDeadEnds() { for (bool go = true; go; ) { go = false; // find dead-end vertices for (Vertex *vertex = vertices; vertex != 0; ) { Vertex *next = vertex->next; if ( vertex->out == 0 || (vertex->out->to == vertex && vertex->out->next_out == 0) || vertex->in == 0 || (vertex->in->from == vertex && vertex->in->next_in == 0)) removeVertex(vertex); vertex = next; } } } void normalize() { for (bool go = true; go; ) { go = false; // find vertices that can be merged for (Vertex *first = vertices; first != 0; first = first->next) for (Vertex *second = first->next; second != 0; second = second->next) if (second->label == first->label) { if (debug_norm_compare) printf("%d %d\n", first->nr, second->nr); char in = '='; for (Edge *edge1 = first->in; edge1 != 0 /*&& in != 'X'*/; edge1 = edge1->next_in) { bool eq = false; bool same = false; for (Edge *edge2 = second->in; edge2 != 0; edge2 = edge2->next_in) if (edge1->from->label == edge2->from->label) { same = true; if (edge1->from->nr == edge2->from->nr) eq = true; } if (debug_norm_compare) printf("first.in %d-%c %c\n", edge1->from->nr, edge1->from->label, eq ? '=' : same ? 's' : 'X'); if (!same) in = 'X'; else if (in != 'X' && !eq) in = 's'; } for (Edge *edge1 = second->in; edge1 != 0 /*&& in != 'X'*/; edge1 = edge1->next_in) { bool eq = false; bool same = false; for (Edge *edge2 = first->in; edge2 != 0; edge2 = edge2->next_in) if (edge1->from->label == edge2->from->label) { same = true; if (edge1->from->nr == edge2->from->nr) eq = true; } if (debug_norm_compare) printf("second.in %d-%c %c\n", edge1->from->nr, edge1->from->label, eq ? '=' : same ? 's' : 'X'); if (!same) in = 'X'; else if (in != 'X' && !eq) in = 's'; } char out = '='; for (Edge *edge1 = first->out; edge1 != 0 /*&& out != 'X'*/; edge1 = edge1->next_out) { bool eq = false; bool same = false; for (Edge *edge2 = second->out; edge2 != 0; edge2 = edge2->next_out) if (edge1->to->label == edge2->to->label) { same = true; if (edge1->to->nr == edge2->to->nr) eq = true; } if (debug_norm_compare) printf("first.out %d-%c %c\n", edge1->to->nr, edge1->to->label, eq ? '=' : same ? 's' : 'X'); if (!same) out = 'X'; else if (out != 'X' && !eq) out = 's'; } for (Edge *edge1 = second->out; edge1 != 0 /*&& out != 'X'*/; edge1 = edge1->next_out) { bool eq = false; bool same = false; for (Edge *edge2 = first->out; edge2 != 0; edge2 = edge2->next_out) if (edge1->to->label == edge2->to->label) { same = true; if (edge1->to->nr == edge2->to->nr) eq = true; } if (debug_norm_compare) printf("second.out %d-%c %c\n", edge1->to->nr, edge1->to->label, eq ? '=' : same ? 's' : 'X'); if (!same) out = 'X'; else if (out != 'X' && !eq) out = 's'; } if (debug_norm_compare) printf("%d %d %c %c\n", first->nr, second->nr, in, out); //if (in != 'X' && out != 'X' && (in == '=' || out == '=')) if (in == '=' || out == '=') { printf("Merge %d and %d%s%s\n", first->nr, second->nr, in == '=' ? " same in" : "", out == '=' ? " same out" : ""); mergeWith(second, first); //print(); go = true; } } } } void product(VertexLabeledGraph *first, VertexLabeledGraph *second) { for (Vertex *f = first->vertices; f != 0; f = f->next) for (Vertex *s = second->vertices; s != 0; s = s->next) if (f->label == s->label) { Vertex *vertex = createVertex(f->label, ' '); vertex->first = f; vertex->second = s; } for (Vertex *vertex = vertices; vertex != 0; vertex = vertex->next) for (Edge *f_out = vertex->first->out; f_out != 0; f_out = f_out->next_out) for (Edge *s_out = vertex->second->out; s_out != 0; s_out = s_out->next_out) for (Vertex *to_vertex = vertices; to_vertex != 0; to_vertex = to_vertex->next) if (to_vertex->first == f_out->to && to_vertex->second == s_out->to) { addEdge(vertex, to_vertex); break; } } void checkUsage(VertexLabeledGraph *first, VertexLabeledGraph *second) { printf("Check ussage:\n"); for (Vertex *vertex = vertices; vertex != 0; vertex = vertex->next) for (Edge *f_out = vertex->first->out; f_out != 0; f_out = f_out->next_out) for (Edge *s_out = vertex->second->out; s_out != 0; s_out = s_out->next_out) for (Vertex *to_vertex = vertices; to_vertex != 0; to_vertex = to_vertex->next) if (to_vertex->first == f_out->to && to_vertex->second == s_out->to) { f_out->mark = true; s_out->mark = true; } first->checkMarks("first"); second->checkMarks("second"); printf("Done\n"); } void checkMarks(const char *text) { for (Vertex *vertex = vertices; vertex != 0; vertex = vertex->next) for (Edge *edge = vertex->out; edge != 0; edge = edge->next_out) if (!edge->mark) printf("Not used %d-%c -> %d-%c in %s\n", vertex->nr, vertex->label, edge->to->nr, edge->to->label, text); } void print() { for (Vertex *vertex = vertices; vertex != 0; vertex = vertex->next) { printf("%2d-%c%c", vertex->nr, vertex->label, vertex->context); if (vertex->first != 0 && vertex->second != 0) printf(" [%2d, %2d]", vertex->first->nr, vertex->second->nr); printf(": "); for (Edge *edge = vertex->out; edge != 0; edge = edge->next_out) printf(" %2d-%c%c", edge->to->nr, edge->to->label, edge->to->context); printf("\n"); } } void mergeWith(Vertex *source, Vertex *target) { for (Edge *out_edge = source->out; out_edge != 0; out_edge = out_edge->next_out) addEdge(target, out_edge->to); for (Edge *in_edge = source->in; in_edge != 0; in_edge = in_edge->next_in) addEdge(in_edge->from, target); removeVertex(source); } void removeVertex(Vertex *vertex) { for (Vertex **ref = &vertices; *ref != 0; ref = &(*ref)->next) if (*ref == vertex) { *ref = vertex->next; break; } for (Edge *out_edge = vertex->out; out_edge != 0; out_edge = out_edge->next_out) for (Edge **ref = &(out_edge->to)->in; *ref != 0; ref = &(*ref)->next_in) if (*ref == out_edge) { *ref = out_edge->next_in; break; } for (Edge *in_edge = vertex->in; in_edge != 0; in_edge = in_edge->next_in) for (Edge **ref = &(in_edge->from)->out; *ref != 0; ref = &(*ref)->next_out) if (*ref == in_edge) { *ref = in_edge->next_out; break; } } Vertex *vertices; private: }; struct Piece { char name; char left; char top[3]; char bottom[3]; char right; char bottoml() { return bottom[0]; } char bottomr() { return bottom[1] != '\0' ? bottom[1] : bottom[0]; } }; Piece pieces[8] = { { 'a', '|', "2", "4", '.' }, { 'b', '.', "3", "15", '.' }, { 'c', '.', "4", "2", '|' }, { 'd', '.', "", "3", '.' }, { 'e', '|', "3", "3", '|' }, { 'f', '.', "41", "14", '.' }, { 'g', '.', "52", "25", '.' }, { '-', '.', "3", "3", '.' }, }; #define KINDINDEX(C) ((C) == '-' ? 7 : (C) - 'a') struct Connection { bool possible; char top[4]; char bottom[4]; }; Connection connections[8][8]; void buildConnections() { for (int li = 0; li < 8; li++) for (int ri = 0; ri < 8; ri++) connections[li][ri].possible = false; for (int li = 0; li < 8; li++) { Piece &l = pieces[li]; if (l.name == 'd') continue; for (int ri = 0; ri < 8; ri++) { Piece &r = pieces[ri]; if (r.name == 'd') continue; Connection &c = connections[li][ri]; if (l.right != r.left) continue; if (l.bottomr() == '5' && r.bottoml() == '3') continue; if (l.bottomr() == '3' && r.bottoml() == '1') continue; c.possible = true; strcpy(c.top, r.top); char *t = c.bottom; char *f = r.bottom; if (l.bottomr() == '5') { if (*f == '1') { *t++ = '3'; f++; } else *t++ = '5'; } for (; *f != '\0' && *f != '5'; f++) *t++ = *f; *t = '\0'; } } printf(" "); for (int ri = 0; ri < 8; ri++) printf(" %c", pieces[ri].name); printf("\n"); for (int li = 0; li < 8; li++) { printf(" %c ", pieces[li].name); for (int ri = 0; ri < 8; ri++) { Connection &c = connections[li][ri]; if (c.possible) printf(" %2s/%-2s", c.top, c.bottom); else printf(" - "); } printf("\n"); } } struct Tree { VertexLabeledGraph::Vertex *vertex; Tree *children; Tree *next; }; VertexLabeledGraph *createGraph(bool use_top) { VertexLabeledGraph *graph = new VertexLabeledGraph; Tree *trees[8]; for (int i = 0; i < 8; i++) trees[i] = 0; for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) { Connection &c = connections[i][j]; if (c.possible) { const char *labels = use_top ? c.top : c.bottom; if (debug_create) printf("%d-%d %s\n", i, j, labels); Tree *parent = 0; Tree **ref = &trees[j]; for (; *labels != '\0'; labels++) { for (; *ref != 0; ref = &(*ref)->next) if ((*ref)->vertex->label == *labels) break; if (*ref == 0) { *ref = new Tree; (*ref)->vertex = graph->createVertex(*labels, pieces[j].name); (*ref)->children = 0; (*ref)->next = 0; if (parent != 0) graph->addEdge(parent->vertex, (*ref)->vertex); } parent = *ref; ref = &(*ref)->children; } } } //graph->print(); for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) { Connection &c = connections[i][j]; if (c.possible) { const char *labels = use_top ? c.top : c.bottom; if (debug_create) printf("%d-%d %s\n", i, j, labels); Tree *from_tree = trees[j]; for (; *labels != '\0'; labels++) { while (from_tree->vertex->label != *labels) from_tree = from_tree->next; if (labels[1] != '\0') from_tree = from_tree->children; } for (int k = 0; k < 8; k++) { Connection &c2 = connections[j][k]; if (c2.possible) { //printf("T %d %d %d: %s - %s\n", i, j, k, use_top ? c.top : c.bottom, use_top ? c2.top : c2.bottom); for (Tree *to_tree = trees[k]; ; to_tree = to_tree->next) { if (to_tree->vertex->label == (use_top ? c2.top[0] : c2.bottom[0])) { //printf("L %c %d %d\n", to_tree->vertex->label, from_tree->vertex->nr, to_tree->vertex->nr); graph->addEdge(from_tree->vertex, to_tree->vertex); break; } } } } } } graph->print(); return graph; } int main(int argc, char *argv[]) { buildConnections(); printf("\n\nTop:\n\n"); VertexLabeledGraph *first = createGraph(true); printf("\n\nBottom:\n\n"); VertexLabeledGraph *second = createGraph(false); printf("\n\nProduct:\n\n"); VertexLabeledGraph *combined = new VertexLabeledGraph; combined->product(first, second); combined->removeDeadEnds(); combined->print(); printf("\n\n"); combined->checkUsage(first, second); printf("\n\nNormalize:\n"); combined->normalize(); printf("\n"); combined->print(); return 0; }