Package COM.INFORMATIMAGO.COMMON-LISP.CESARUM.BRELATION


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.