Concept lattice drawings are an important tool to visualize complex relations in data in a simple manner to human readers. Many attempts were made to transfer classical graph drawing approaches to order diagrams. Although those methods are satisfactory for some lattices they unfortunately perform poorly in general. In this work we present a novel tool to draw concept lattices that is purely motivated by the order structure.
lattice order as its intersection. From this family we derive coordinates for our lattice drawing. In fact, our tool does not only work on concept lattices but also on arbitrary orders.
Related Work and Basics from Formal Concept Analysis. We rely on notations from [4], i.e., (G; M; I) is a formal context with sets G and M , and I G M . Furthermore, 0 : P(G) ! P(M ); A 7! A0 := fm 2 M j 8g 2 A : (g; m) 2 Ig and 0 : P(M ) ! P(G); B 7! B0 := fg 2 G j 8m 2 B : (g; m) 2 Ig are derivation operators enabling B(G; M; I) = f(A; B) P(G) P(M ) j A0 = B ^ B0 = Ag, the set of all formal concepts. This set can be ordered through the inclusion order on G. Various approaches for drawing line diagrams can be found: The author in [5] employs an order approach which lays the foundation for our work. In [2] a rank function and a force-directed approach was used and the author in [3] focuses on additive diagrams. 2
Before introducing the algorithm behind DimDraw we need to recollect some basic notions on order dimension. Let (X; P ) be an ordered set, i.e., P X X is an order relation. Two elements x; y 2 X are called incomparable in P , if neither x P y nor y P x, otherwise they are called comparable. If (X; L) is an ordered set with P L, such that no two elements are incomparable in
L, then L is called a linear extension of P . The intersection of two order relations L1 and L2 on X is also an order relation on X. Let L be a set of linear extensions of P with T L2L L= P . Then L is called a realizer of
P . The order dimension of an order relation P is the cardinality of a minimal realizer of P .
A Ferrers relation is a relation F G M , such that for all g; h 2 G and m; n 2 M the following condition holds: (g; m) 2 F and (h; n) 2 F ) (g; n) 2 F or (h; m) 2 F . Following [4, Proposition 103] we know that F G M is a Ferrers relation if and only if B(G; M; F ) is a chain, i.e., all elements of B(G; M; F ) are pairwise comparable. Those chains are essential for our drawing approach. The Ferrers dimension of a formal context is the smallest number k, such that there exists a set of k Ferrers relations with their intersection being I. The Ferrers dimension of a context is equal to the order dimension of its concept lattice, see [4, Theorem 46]. We further know that the order dimension of B(G; M; I) for some context (G; M; I) is at most d, if there are Ferrers relations F1; : : : ; Fd G M with G M nI = Sid=1 Fi. This fact gives a handy way to compute the order dimension of a concept lattice. One has to cover all empty cells of the cross table of a concept with Ferrers relations. Note that those do not have to be disjoint. Unfortunately deciding the order dimension and the Ferrers dimension are N P-complete if the dimensions are three or higher. Computing Coordinates using a Realizer. First we have to compute a minimal realizer of the order relation of the concept lattice. This can be done with an algorithm described in [6]. Note that the algorithm described there is only exact for certain ordered sets. Alternatively one can use the Ferrers dimension: Try to cover all the empty spaces in a cross-table by as few Ferrers relations as possible. Then take the inverse Ferrers relations, compute the chains given by these relations and extend them to cover every element of B(G; M; I).
Given a linear extension of a lattice, let the position of each concept in the linear extension be the cardinality of the set of sub-concepts. Embed the concept lattice into Rd with d being its order dimension. The coordinates of concept C are given as (c1; : : : ; cd), such that ci is the position of concept C in the linear extension Li. Note that for each pair of concepts X; Y it holds that X is a sub-concept of Y , if and only if, for the coordinates X = (x1; : : : ; xd) and Y = (y1; : : : ; yd), it holds that xi yi for all 1 i d. By rotating the resulting embedding we obtain a valid embedding of the concept lattice in Rd. We have to carefully project this embedding to the plane to obtain our drawing. The theory we developed for the projection is based on work of [1]. It is very extensive and will be presented in a later work due to space constraints.
Example. Take the “Life in water” context from [4], and consider the three Ferrers-relations that cover all free spaces in the cross table: These Ferrers relations give rise to the following (not unique) realizer: S 1Q 1O 1R 1P 1N 1H 1L 1K 1C 1M 1I 1G 1F 1J 1E 1B 1D 1A S 2P 2O 2M 2J 2H 2F 2B 2R 2K 2I 2D 2N 2G 2Q 2L 2E 2C 2A S 3R 3Q 3N 3I 3L 3G 3E 3P 3M 3K 3J 3D 3O 3H 3F 3C 3B 3A
Note that this context is in fact 3-dimensional as the elements fE; C; D; L; I; Kg
form the ordered set S3, which is well-known to be 3-dimensional. Now we embed
the concepts based on their positions in the linear extensions as described above:
A(18,18,18), B(16,7,17), C(9,17,16), D(15,16,7), E(15,16,7), F(
We obtain the following embedding (left) which is quite close to the hand drawn version (right):
Another example, that is also taken from [4] is the “Drive concepts for motorcars” context. Here the embedding generated with our tool (left) is further away from the hand-drawn version (right), however it is again easy to read:
As another example we present the contra nominal scales on n objects and attributes, i.e., ([n]; [n]; 6=) where [n] := f1; 2; : : : ; ng. It is easy to see that these exhibit order dimension n. We show line diagrams of the concept lattices computed by DimDraw for the two, three, and four dimensional contra nominal scales:
We conclude this section by comparing our tool to previous results in [3]. There the author employed an approach to generate additive line diagrams (left). We may note that our drawing (middle) is not additive, however, it resembles the hand drawn additive diagram (right) more accurately.
Outlook In this work we demonstrated a novel approach for drawing lattice diagrams automatically, which resulted in the work-in-progress software DimDraw. This tool will be part of the upcoming version of conexp-clj (https://github. com/exot/conexp-clj). The ongoing research for more sophisticated projection theories, as used by this tool, will be extended in future publications.