Lab 5 Relations

Purpose

The purpose of this lab is to familiarize the student with the concept of determining the properties of relations and programming using a functional programming style. In addition, the extra credit introduces the student to the evaluation of trees using the properties of relations.

Process

Implement the following functions in Rust. Each of the functions should be created with a functional programming style (no side effects, no global values, immutable variables, etc.). Implement the managing code in any style. The managing code should provide facilities for the use to exercise each of these functions.

Reflexive

Input: a list of pairs, L, and the set S over which the relation is defined. Interpreting the input as a binary relations, return True if it is reflexive and False otherwise.

Symmetric

Input: a list of pairs, L, and the set S over which the relation is defined. Interpreting the input as a binary relation, return #T if it is symmetric and False otherwise.

Transitive

Input: a list of pairs, L. Interpreting the input as a binary relation, return True if it is Transitive and False otherwise

4. Antisymetric

Input: a list of pairs, L. Interpreting the input as a binary relation, return True if it is Transitive and False otherwise

5. Equivalence

Input: a list of pairs, L. Interpreting the input as a binary relation, return True if it is an equivalence relation and False otherwise

For extra credit:

Tree that takes as input two lists, representing the vertices and edges of a graph. The function should output True if the input graph represents a tree and False otherwise.

The vertices will be represented as a list of vertex names and the edges will be represented as a list of two-element lists of vertices.

For example, a call to

Tree ( [a,b,c,d,e], [ [a,b], [a,e],[b,c],[c,d],[d,f] ])

should return True, because it is connected and has no cycles; and a call to

Tree( [a,b,c,d,e],[ [a,b], [a,c], [d,e] ] )

should return False, because it is not connected. Finally, a call to

Tree( [a,b,c],[ [a,b], [a,c], [b,c] ] )

should return False, because it has a cycle.

Example Sets and Pairs

Students must evaluate the following sets and pairs, as well as create and test at least two sets and pairs of their own creation:

[a,b,c,d,e], [ [a,b], [a,e],[b,c],[c,d],[d,f] ]

[1, 3, 5, 7, 8, 12, 13], [[1,8],[1,12],[3,8],[3,12],[5,8],[5,12],[7,8],[7,12]]

[(),!, *, +, <<, <, &], [[+,*],[*,()],[*,!],[+,<<],[<<,<],[<<, &]]

[m,d,b,s,g,f], [[m,b],[m,s],[d,b],[d,s],[g,m],[f,m]]