Welcome to yEd Q&A!
Here you can ask questions and receive answers from other members of the community and yEd developers. And you can tell us your most wanted feature requests.

Specification of the algorithm used for Hierarchical Layout - Optimal

0 votes
Hi there, congratulations for an excellent tool we have been using since 2006 for our research.

Generally, we use it for "just visualization", but sometimes we would need a better specification of the algorithms behind it.

We were using version  3.14.4 of the software and some small graphs present a four-level layout that has four independent sets in each layout, of different cardinality, in each layer (when we are using Hierarchical Layout - Optimal). The BFS option creates a layout of three layers but two of them are not independent sets.

In version 3.17.2 both layout options give the same layout, the one of BFS of the previous version.

We are interested to know more about the changes. We particularly enjoy the layout that has independent sets in each layer and we would like to know if there is a polynomial-time algorithm that creates these layouts, or any other formal detail that can allow us to understand the procedure in formal mathematical terms. The online information could not help to cover this gap.

In addition, we would like to know what may have happened between the two versions. If there was an optimal result before, why we are getting the BFS result now in the new version of the software.

We can facilitate to you some small graphs in case you need it, or if some debugging seems to be necessary to address the question.

Kind regards,

P.
asked Apr 3, 2018 in Help by Pablo Moscato (120 points)

1 Answer

0 votes

Well, yEd 3.16 introduced a new option for Hierarchical Layout that deduces the edge direction from the edge style's arrow decorations (see "Layout" -> "Hierarchical", tab "Edges", option "Arrows define Edge Direction") which is enabled by default. With this option enabled, some edges (e.g. those without any arrows) may be considered undirected edges. Undirected edges may lead to layering results similar to BFS layering. If you turn "Arrows define Edge Direction" off, the layering algorithm should produce the same results as in yEd 3.14.4.

Regarding the second question, yes, the algorithm for calculating layers is a polynomial-time algorithm. However, I cannot give you a formal mathematical description of the algorithm. The best I can offer is the corresponding chapter in the  yFiles for Java Developer's Guide and API documentation.

answered Apr 3, 2018 by thomas.behr [yWorks] (122,690 points)
Imprint | Privacy Policy