I’d like to define elegant interfaces for a binary relation and for a transitive relation. I consider a binary relation as a set of pairs, a subset of some set X × Y. In fact I intend to work mainly with transitive relations, but I occasionally need general binary relations. This is mainly for my own usage but I may end-up publishing this as a FLOSS library for other users. I would like my definitions to make sense on a general level as I do not have yet precise requirements about usage of these classes: I need them for experimental work related to scientific research, I have some ideas right now but it is unclear yet what kind of experiments I will need as more ideas come while doing the research.
General idea
The core of what I (think I) need is as follows.
/**
* @param <F>
* the type used for the “from” elements.
* @param <T>
* the type used for the “to” elements.
*
*/
public interface BinaryRelationTentative<F, T> {
/**
* @return a view of the domain of this relation: all the elements x such that for some y, (x, y) is in the
* relation.
*/
public Set<F> getFromSet();
/**
* @return a view of the range of this relation: all the elements y such that for some x, (x, y) is in the relation.
*/
public Set<T> getToSet();
/**
* @return the number of pairs that this relation contains.
*/
public int size();
/**
* @return <code>true</code> iff the relation has empty from and to sets.
*/
public boolean isEmpty();
/**
* A binary relation equals an other one iff they have equal from and to sets and for each (x, y) contained in one,
* (x, y) is contained in the other one.
*/
@Override
public boolean equals(Object obj);
/**
* @return whether the given <code>from</code> element is in relation with the <code>to</code> element.
*/
public boolean contains(F from, T to);
/**
* Optional operation.
*/
public boolean add(F from, T to);
}
(This is only the core features, so that you see what I mean — nicer features for traversal and so on would be welcome, see below.) Then I would define a TransitiveRelation<E> that extends BinaryRelation<E, E>, that does not implement add but rather provides addTransitive(F from, T to).
Re-using classical collections
Now of course, I want to re-use classical collection interfaces as much as possible. It seems Guava’s SetMultimap (javadoc, user guide) has the core features I need and more. The user guide even mentions the use case of an unlabeled directed graph. One problem I see with using directly SetMultimap is that the terminology is not exactly right: speaking of “keys” and “values” in case of a binary relation is strange. Moreover, it misses something. There is an asymetry that makes sense in a SetMultimap (designed to go from key to values), that makes less sense in a binary relation. The SetMultimap has an interface (and implementations) that allows one to, given a “from” element, iterate efficiently (i.e. without traversing the whole relation) through the ”to” elements in relation to it. Similarly, I would like to be able to, having a “to” element, iterate over the corresponding “from” elements efficiently. So I need something that could be called a BiSetMultimap (corresponding to both a Map<K, Set<V>> and a Map<V, Set<K>>). I have not been able to find such thing in the Java world.
I am currently, thus, thinking about defining BinaryRelation<F, T> as a facade to SetMultimap<F, T>. I can then create better-named methods in the interface (conceptually equivalent to the methods in SetMultimap), and I can add a method getInverselyRelated(T to): Set<F> that gives the “from” elements. I could provide implementations based on two SetMultimaps kept in sync, one representing the relation and one representing its inverse.
There’s numerous alternative approaches to this problem. I could for example define BinaryRelation as extending SetMultimap. Or I could avoid hiding completely SetMultimap and provide access to it through BinaryRelation#asSetMultimap(). That way I get all their nice method interfaces. Or I could give up entirely the idea of a specific interface and use a SetMultimap instead of a BinaryRelation, considering then the reverse-traversal operation as an optimisation feature available in specific classes but not on the interface level. Or I could perhaps use something else than SetMultimap as a basis for the design.
Therefore, my question (finally!): what do you think about my approach? Can you think about other approaches? Some problems I overlooked? An existing solution I could use?
Possible links
I thought about using some Graph library (JUNG, JGraphT, Blueprint), but I do not think they fit my needs. All these have an Edge class (or an Edge type parameter) which adds complexity and none provide interfaces and implementations as nice as SetMultimap, in my humble opinion. Grph does not provide objects for vertices, as the user manual says. I may have missed something though so tell me if you disagree.
(Edit.) As mentioned by Xaerxess, this guava issue suggests to add what I call here a BiSetMultimap to Guava.
