This package implements a relation abstract data type based on an array of bset. It can represent only relations between two positive and bounded integers. (Inspired by Modula-2 cocktail-9309/reuse/src/Relations.md). See also: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.BSET License: AGPL3 Copyright Pascal J. Bourguignon 2004 - 2012 This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>

( assign rel1 rel2) |
function |

POST: REL1 is a copy of REL2. RETURN: REL1

( assign-element rel e1 e2) |
function |

POST: REL contains only (E1,E2). RETURN: REL

( assign-empty rel) |
function |

POST: REL is the empty relation. RETURN: REL

brelation |
structure |

The Binary Relation Class.

( cardinal rel) |
function |

RETURN: The number of couples in the relation REL.

( closure rel) |
function |

POST: REL is the transitive closure of the old REL. RETURN: REL

( complement rel) |
function |

POST: REL is the complement of old REL. RETURN: REL

( difference rel1 rel2) |
function |

POST: REL1 is the difference of old REL1 and REL2. RETURN: REL1

( exclude rel e1 e2) |
function |

DO: Remove (E1 E2) from the relation REL. POST: ¬ REL(E1,E2)

( exists rel proc) |
function |

DO: Calls PROC on couples of the relation REL until it returns true. PROC: A predicate of two elements. RETURN: Whether PROC returned true for at least one couple.

( exists-1 rel proc) |
function |

DO: Calls PROC on each couples of the relation REL. PROC: A predicate of two elements. RETURN: Whether PROC returned true for exactly one couple.

( extract rel) |
function |

DO: Selects a couple in the relation REL, exclude it from REL, and return it. PRE: (not (is-empty rel)) POST: ¬REL(i,j) RETURN: (values i j) such as old REL(i,j), or NIL if REL is empty.

( for-all rel proc) |
function |

DO: Calls PROC on couples of the relation REL while it returns true. PROC: A predicate of two elements. RETURN: Whether PROC returned true for all couples.

( for-all-do rel proc) |
function |

DO: Calls PROC on each couple of the relation REL. PROC: A function of two elements. RETURN: REL

( get-cyclics rel bset) |
function |

RETURN: The set of elements that are in cycles.

( has-reflexive rel) |
function |

RETURN: ∃i∈[0,SIZE1-1], REL(i,i)

( include rel e1 e2) |
function |

DO: Adds (E1 E2) to the relation REL. POST: REL(E1,E2)

( intersection rel1 rel2) |
function |

POST: REL1 is the intersection of old REL1 and REL2. RETURN: REL1

( is-cyclic rel) |
function |

RETURN: Whether the relation REL is cyclic.

( is-element e1 e2 rel) |
function |

RETURN: Whether REL(E1,E2).

( is-empty rel) |
function |

RETURN: Whether REL is empty.

( is-equal rel1 rel2) |
function |

RETURN: Whether REL1 is equal to REL2.

( is-equivalence rel) |
function |

RETURN: Whether REL is an equivalence relation. Ie. REL is reflexive, symetric and transitive.

( is-not-equal rel1 rel2) |
function |

RETURN: Whether REL1 is not equal to REL2.

( is-reflexive rel) |
function |

RETURN: Whether the relation REL is reflexive. Ie. ∀i∈[0,SIZE1-1], REL(i,i)

( is-reflexive-1 e1 rel) |
function |

RETURN: Whether REL(E1,E1)

( is-related e1 e2 rel) |
function |

RETURN: Whether REL(E1,E2).

( is-strict-subset rel1 rel2) |
function |

RETURN: Whether REL1 is a strict subset of REL2.

( is-subset rel1 rel2) |
function |

RETURN: Whether REL1 is a subset of REL2.

( is-symmetric rel) |
function |

RETURN: Whether the relation REL is symetric. Ie. ∀(i,j)∈[0,SIZE1-1]², REL(i,j) ⇒ REL(j,i)

( is-transitive rel) |
function |

RETURN: Whether the relation REL is transitive. Ie. ∀(i,j,k)∈[0,SIZE1-1]³, REL(i,j) ∧ REL(j,k) ⇒ REL(i,k)

( is-transitive-1 e1 e2 e3 rel) |
function |

RETURN: Whether (REL(E1,E2) ∧ REL(E2,E3)) ⇒ REL(E1,E3) NOTE: Tests the transitivity of the relation REL only on the elements E1, E2, and E3. This doesn't mean the relation REL is transitive (but it's a necessary condition).

( make-brelation size-1 size-2) |
function |

RETURN: A new BRELATION between sets of sizes SIZE-1 and SIZE-2.

( project-1 rel e1 bset) |
function |

POST: BSET is the set of all elements I that are in relation REL(I,E2). RETURN: BSET

( project-2 rel e1 bset) |
function |

POST: BSET is the set of all elements E2 that are in relation REL(E1,E2). RETURN: BSET

( read-brelation stream rel) |
function |

DO: Read a relation from the STREAM. POST: REL is the relation read. RETURN: REL. NOTE: The serialization format is that of a list of adjacency lists. ((1 (2 3)) (2 (3)) (4)) = ({1 2 3 4} {(1 2) (1 3) (2 3)})

( select rel) |
function |

RETURN: (values i j) such as REL(i,j), or NIL if REL is empty.

( sym-diff rel1 rel2) |
function |

POST: REL1 is the symetric difference of old REL1 and REL2. RETURN: REL1

( union rel1 rel2) |
function |

POST: REL1 is the union of old REL1 and REL2. RETURN: REL1

( write-brelation stream rel) |
function |

DO: Write the relation REL to the STREAM. RETURN: REL.