IZP/Cviko6_3/main.c

#include "types.h"
#include <stdio.h>

const int UNIVERSUM[MAXITEMS] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

#ifndef TEST_BUILD

int main(void) {
  Set set = {.items = {1, 3, 5}, .cardinality = 3};

  const int pairCount = 7;
  // TODO: 2. staticky inicializujte pole struktur Pair
  Pair pairs[pairCount] = {
      {1, 1}, {1, 3}, {3, 1}, {3, 3}, {3, 5}, {5, 3}, {5, 5},
  };

  // TODO: 3., 4., 5. zavolejte implementované funkce a vypište své výsledky
  if (rel_isFunction(pairs, pairCount, &set)) {
    printf("Relation is a function\n");
  } else {
    printf("Relation is NOT a function\n");
  }

  int min, max;
  rel_minMax(pairs, pairCount, &min, &max);
  printf("Minimum and maximum values are %d and %d respectively.\n", min, max);

  if (rel_isEquivalence(pairs, pairCount, &set)) {
    printf("Relation is equivalent\n");

  } else {
    printf("Relation is NOT equivalent\n");
  }

  return 0;
}

#endif

bool exists_on_set(Pair pairs[], int pairCount, Set *set) {
  for (int setIndex = 0; setIndex < set->cardinality; setIndex++) {
    bool exists = false;
    for (int pairIndex = 0; pairIndex < pairCount; pairIndex++) {
      if (set->items[setIndex] == pairs[pairIndex].first ||
          set->items[setIndex] == pairs[pairIndex].second) {
        exists = true;
        break;
      }
    }

    if (!exists) {
      return false;
    }
  }
  return true;
}

/**
 * @param pairs      Prvky nějaké binární relace (pole dvojic)
 * @param pairCount  Počet položek (dvojic) v relaci
 * @param set        Množina nad kterou je relace definována
 *
 * @returns hodnotu true pokud relace je funkcí, false jinak
 */
bool rel_isFunction(Pair pairs[], int pairCount, Set *set) {
  if (pairCount == 0 || !exists_on_set(pairs, pairCount, set)) {
    return false;
  }
  int existing[pairCount];
  bool ok = true;
  for (int pairIndex = 0; pairIndex < pairCount; pairIndex++) {
    for (int existingIndex = 0; existingIndex < pairCount; existingIndex++) {
      if (existing[existingIndex] == pairs[pairIndex].first) {
        ok = false;
        break;
      }
      existing[existingIndex] = pairs[pairIndex].first;
    }
  }
  return ok;
}

/**
 * @param pairs      Prvky nějaké binární relace (pole dvojic)
 * @param pairCount  Počet položek (dvojic) v relaci
 * @param relMin     Ukazatel na proměnnou minimální hodnoty relace
 * @param relMax     Ukazatel na proměnnou maximální hodnoty relace
 *
 * @returns hodnotu true pokud bylo hledání úspěšné, false jinak
 */
bool rel_minMax(Pair pairs[], int pairCount, int *relMin, int *relMax) {
  if (pairCount == 0)
    return false;

  *relMin = pairs[0].second;
  *relMax = pairs[0].second;
  for (int i = 1; i < pairCount; i++) {
    if (pairs[i].second < *relMin) {
      *relMin = pairs[i].second;
    }
    if (pairs[i].second > *relMax) {
      *relMax = pairs[i].second;
    }
  }
  return true;
}

/**
 * @param pairs      Prvky nějaké binární relace (pole dvojic)
 * @param pairCount  Počet položek (dvojic) v relaci
 * @param set        Množina nad kterou je relace definována
 *
 * @returns hodnotu true pokud relace je relací ekvivalence, false jinak
 */
bool rel_isEquivalence(Pair pairs[], int pairCount, Set *set) {
  if (pairCount == 0 || !exists_on_set(pairs, pairCount, set)) {
    return false;
  }
  // Relace je ekvivalence, pokud je reflexivní, symetrická a tranzitivní.

  // Reflexivní = pro každý prvek 'a' z množiny A platí aRa
  for (int setIndex = 0; setIndex < set->cardinality; setIndex++) {
    bool reflexive = false;
    for (int pairIndex = 0; pairIndex < pairCount; pairIndex++) {
      if (pairs[pairIndex].first == set->items[setIndex] ||
          pairs[pairIndex].second == set->items[setIndex]) {
        reflexive = true;
        break;
      }
    }
    if (!reflexive) {

      return false;
    }
  }

  // Symetrická = Pro každé aRb platí i bRa
  for (int pairIndex = 0; pairIndex < pairCount; pairIndex++) {
    bool symmetrical = false;
    for (int secondRoundIndex = 0; secondRoundIndex < pairCount;
         secondRoundIndex++) {
      if (pairs[pairIndex].first == pairs[secondRoundIndex].second &&
          pairs[pairIndex].second == pairs[secondRoundIndex].first) {
        symmetrical = true;
        break;
      }
    }
    if (!symmetrical) {
      return false;
    }
  }

  // Tranzitivní = platí: (aRb ^ bRc) => aRc
  for (int pairIndex = 0; pairIndex < pairCount; pairIndex++) {
    bool transitive = false;
    for (int secondRoundIndex = 0; secondRoundIndex < pairCount;
         secondRoundIndex++) {
      if (pairs[pairIndex].second == pairs[secondRoundIndex].first) {
        // máme aRb ^ bRc
        for (int thirdRoundIndex = 0; thirdRoundIndex < pairCount;
             thirdRoundIndex++) {
          if (pairs[pairIndex].first == pairs[thirdRoundIndex].first &&
              pairs[secondRoundIndex].second == pairs[thirdRoundIndex].second) {
            // printf("%dR%d ^ %dR%d => %dR%d\n\n", pairs[pairIndex].first,
            //        pairs[pairIndex].second, pairs[secondRoundIndex].first,
            //        pairs[secondRoundIndex].second, pairs[thirdRoundIndex].first,
            //        pairs[thirdRoundIndex].second);
            transitive = true;
            break;
          }
        }
        if (!transitive) {
          return false;
        }
      }
    }
  }

  return true;
}