Study On Layout Algorithms For Hasse Diagram Of Concept Lattices

Concept Lattices Theory is called Formal Concept Analysis, which is used indiscovery, sorting and display of concepts. As a kind of formal tool for dataorganization and data analysis, concept lattices is important in both theoretical researchand practical application, and it has been succeeded applied in several areas. Being thecore data structure in formal concept analysis concept lattice essentially described thecontact between the objects and the attributes, shown the generalization andspecialization relationship among concepts. In corresponding, the Hasse diagramsrealize the visualization of data. The layout of concepts nodes plays an important rolein the readability and time efficiency of concept lattice drawings.This paper studies the classic layout algorithms of lattices drawings, analysis thetraditional additive line diagram which has used backtracking search method, pointsout that the part of low efficiency. The paper proposes an advanced additive linediagram algorithm: Direct Assign Additive Line Diagram, which rejects traditionalretrospective search method, assign attributes directly, uses the vector of conceptindirectly. The advanced algorithm effectively reduces the process of seeking vectorfor attributes, improve the efficiency of lattice drawings layout. In addition, the ideaof adjacent of related concepts increases the readability of concept lattices drawings.The paper also puts out a new layout optimization strategy for lattice drawings: getconcepts through the layer, exchange the position of concept nodes, compute edgecrossings, and determine the position of concept node according to the edge crossingssituation. This strategy makes concept lattices diagram to be in a state, in which theedge crossings is the least.Through the experiments on the same data of layout algorithms and layoutoptimization, the direct assign additive line diagram proposed in this paper is provedbetter than the traditional additive line diagram in time efficiency and artistic aspects,and the optimization strategy plays a positive role.This paper mainly includes the following four aspects:1. Propose a kind of advanced additive line layout algorithm.2. Propose a lattice layout optimization algorithm based on linear exchange.3. Perform layout algorithms experiments, analysis and compare the result data,verifies the effectiveness of the presented algorithm.