/* Header file for Math 3012: Applied Combinatorics Updated: January 25, 2007 */ /* Declarations */ int test_reflexive(int **P, int n); int test_antisymmetric(int **P, int n); int test_transitive(int **P, int n); int test_poset (int **P, int n); void create_linear_ext(int **P, int *L, int n); int test_intorder (int **P, int n); int minimal_interval_rep(int **P, int *LEP, int *REP, int n); void sort_segment(int *s, int i1, int i2); void sort_labels_by_weights(int *s, int *w, int i1, int i2); void merge_segments(int *s, int i1, int i2, int i3); void merge_segments_by_weights(int *s, int *w, int i1, int i2, int i3); /* Definitions */ int test_reflexive(int **P, int n) { int i; for (i = 1; i <= n; i++) { if (P[i][i] != 1) { return(0); } } return(1); } int test_antisymmetric(int **P, int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if ((i != j) && (P[i][j] == 1) && (P[j][i] == 1)) { return(0); } } } return(1); } int test_transitive(int **P, int n) { int i, j,k; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { for (k = 1; k <= n; k++) { if ((P[i][j] == 1) && (P[j][k] == 1) && (P[i][k] == 0)) { return(0); } } } } return(1); } int test_poset(int **P, int n) { return((test_reflexive(P,n))*(test_antisymmetric(P,n))*(test_transitive(P,n))); } void create_linear_ext(int **P, int *L, int n) { int i,j,k; int no_remaining; int no_minimals; int *R; /* array of elements not yet inserted */ int *Save_R; /* dummy array to store R */ int *M; /* indicates whether entry is minimal */ R = (int *)malloc((n+2)*sizeof(int)); if (R == NULL) { printf("Failed to allocate memory for R.\n"); exit(1); } Save_R = (int *)malloc((n+2)*sizeof(int)); if (Save_R == NULL) { printf("Failed to allocate memory for Save_R.\n"); exit(1); } M = (int *)malloc((n+2)*sizeof(int)); if (M == NULL) { printf("Failed to allocate memory for M.\n"); exit(1); } for (i = 0; i <= n; i++) { R[i] = i; Save_R[i] = i; M[i] = 1; } no_remaining = n; while (no_remaining >= 1) { no_minimals = 0; for (i = 1; i <= no_remaining; i++) { M[i] = 1; for (j = 1; j <= no_remaining; j++) { if ((i != j) && (P[R[j]][R[i]] == 1)) { M[i] = 0; // j = no_remaining; } } if (M[i] == 1) { no_minimals++; L[n-no_remaining+no_minimals] = R[i]; } } j = 0; for (i = 1; i <= no_remaining; i++) { if (M[i] == 0) { j++; R[j] = Save_R[i]; } } no_remaining = no_remaining- no_minimals; for (i = 1; i <= no_remaining; i++) { Save_R[i] = R[i]; } } } int test_intorder (int **P, int n) { /* return 0 if no and 1 if yes */ int i,j,k; int below_i, below_j; for (i = 1; i < n; i++) { for (j = i+1; j <= n; j++) { below_i = 0; below_j = 0; for (k = 1; k <= n; k++) { if ((k != i) && (P[k][i] == 1) && (P[k][j] == 0)) { below_i = k; } if ((k != j) && (P[k][j] == 1) && (P[k][i] == 0)) { below_j = k; } } if(below_i != 0 && below_j != 0) { return(0); } } } return(1); } int minimal_interval_rep(int **P, int *LEP, int *REP, int n) { int i,j,k; int no_endpoints; /* integer end points of representation */ int downset_size; int upset_size; int save_int; int below_i; int below_j; int good_so_far; int *D; /* Counts the size of the down sets */ int *U; /* Counts the size of the up sets */ int *L; /* Used to store D and U */ int *sizeof_downset; int *sizeof_upset; D = (int *) malloc((n+1)*sizeof(int)); if (D == NULL) { printf("Unable to allocate memory for D.\n"); exit(1); } U = (int *) malloc((n+1)*sizeof(int)); if (U == NULL) { printf("Unable to allocate memory for U.\n"); exit(1); } L = (int *) malloc((n+1)*sizeof(int)); if (L == NULL) { printf("Unable to allocate memory for L.\n"); exit(1); } sizeof_downset = (int *) malloc((n+1)*sizeof(int)); if (sizeof_downset == NULL) { printf("Unable to allocate memory for sizeof_downset.\n"); exit(1); } sizeof_upset = (int *) malloc((n+1)*sizeof(int)); if (sizeof_upset == NULL) { printf("Unable to allocate memory for sizeof_upset.\n"); exit(1); } for (i = 1; i <= n; i++) { D[i] = 0; U[i] = 0; } for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (i != j && P[i][j] == 1) { U[i] = 1 + U[i]; D[j] = 1 + D[j]; } } } for (i = 1; i <= n; i++) { L[i] = D[i]; } sort_segment(L, 1, n); no_endpoints = 1; downset_size = 0; sizeof_downset[1] = 0; for(i = 2; i <= n; i++) { if(L[i] > downset_size) { downset_size = L[i]; no_endpoints++; sizeof_downset[no_endpoints] = downset_size; } } for (i = 1; i <= n; i++) { L[i] = U[i]; } sort_segment(L, 1, n); upset_size = 0; sizeof_upset[1]=0; no_endpoints = 1; for(i = 1; i <= n; i++) { if(L[i] > upset_size) { upset_size = L[i]; no_endpoints++; sizeof_upset[no_endpoints] = upset_size; } } for (i = 1; i <= n; i++) { for (j = 1; j <= no_endpoints; j++) { if(D[i] == sizeof_downset[j]) { LEP[i] = j; } if(U[i] == sizeof_upset[j]) { REP[i] = no_endpoints+1-j; } } } return(no_endpoints); } void sort_segment(int *s, int i1, int i2) { int j1, j2, j3; int k; if (i1 < 0 || i1 > i2) { printf("Error: Bad values for sort_segment call.\n"); exit(1); } if (i1 == i2) { return; } else { k = (i1 + i2)/2; sort_segment(s, i1, k); sort_segment(s, k+1, i2); merge_segments(s, i1, k, i2); } } void sort_labels_by_weights(int *s, int *w, int i1, int i2) { int j1, j2, j3; int k; if (i1 < 0 || i1 > i2) { printf("Error 0: Bad values for sort_labels_by_weights call.\n"); exit(1); } if (i1 == i2) { return; } else { k = (i1 + i2)/2; sort_labels_by_weights(s, w, i1, k); sort_labels_by_weights(s, w, k+1, i2); merge_segments_by_weights(s, w, i1, k, i2); } } void merge_segments(int *s, int i1, int i2, int i3) { int j1 = i1; int j2 = i2 + 1; int j3 = 0; long* temp_s = malloc(5+sizeof(long)*(i3-i1)); while ((j1 <= i2) && (j2 <= i3)) { if (s[j1] <= s[j2]) { temp_s[j3++] = s[j1++]; } else { temp_s[j3++] = s[j2++]; } } while (j1 <= i2) { temp_s[j3++] = s[j1++]; } while (j2 <= i3) { temp_s[j3++] = s[j2++]; } for (j3 = 0; j3 <= i3 - i1; j3++) { s[i1+j3] = temp_s[j3]; } free(temp_s); return; } void merge_segments_by_weights(int *s, int *w, int i1, int i2, int i3) { int j1 = i1; int j2 = i2 + 1; int j3 = 0; long* temp_s = malloc(5+sizeof(long)*(i3-i1)); while ((j1 <= i2) && (j2 <= i3)) { if (w[s[j1]] <= w[s[j2]]) { temp_s[j3++] = s[j1++]; } else { temp_s[j3++] = s[j2++]; } } while (j1 <= i2) { temp_s[j3++] = s[j1++]; } while (j2 <= i3) { temp_s[j3++] = s[j2++]; } for (j3 = 0; j3 <= i3 - i1; j3++) { s[i1+j3] = temp_s[j3]; } free(temp_s); return; }