Community
Participate
Working Groups
The current implementation of BarycentricCrossingReducer inserts PADDING NodeWrappers to the list of layers (i.e. List<List<NodeWrapper>>) passed in as argument to crossReduction(List<List<NodeWrapper>>) during its crossing calculations. In detail this is performed inside padLayers(), where the PADDING NodeWrappers are added to the local layers list that gets assigned from the passed in parameter inside crossReduction(List<List<NodeWrapper>>). These PADDING NodeWrappers do not get removed after the crossing calculation is completed. Within applyLayout(boolean) inside the SugiyamaAlgorithm, these PADDING NodeWrappers get ignored by sort of a side effect. That is, when iterating over the layers after the CrossingResolver has processed them, all contained NodeWrappers are added to the local map of NodeLayouts to NodeWrappers via map.put(nw.node, nw). As for PADDING NodeWrappers nw.node will be null, these Wrappers get added to the local map under the null key. The same side effect happens when updating the local NodeLayout to NodeWrapper list inside BarycentricCrossingReducer#updateIndex(List<NodeWrapper>). That is the map returned as a result of crossReduction(List<List<NodeWrapper>>) already contains such a null key, and as this map is assigned to the local map inside SugiyamaLayoutAlgorithm#applyLayout(boolean) this will as well contain such a null key even before adding the layer nodes via map.put(nw.node, nw). I am actually not sure what these padding NodeWrappers are good for anyway (as far as I understand the original barycenter crossing reducing algorithm these do not seem to be needed), but they should IMHO remain local to the BarycentricCrossingReducer, i.e. they should not be added as a side effect to the passed in layers of crossReduction(List<List<NodeWrapper>>) and they should be ignored when building the local map inside BarycentricCrossingReducer#updateIndex(List<NodeWrapper>), so that no null key is added to the map that gets returned by crossReduction(List<List<NodeWrapper>>). I also ask myself, why the crossing reducers actually have to return a map at all. If I understand the code inside SugiyamaLayoutAlgorithm#applyLayout(boolean) correctly, then the passed in layers are evaluated and added to the local map anyway, even after having consumed the map that gets returned by the crossing reducer. As such, we might IMHO change the return value of CrossingReducer#reduceCrossing(List<List<NodeWrapper>>) to be void. Also, as the PADDING NodeWrappers are only used within BarycentricCrossingReducer, we should IMHO remove the concept from the NodeWrapper and deal with it locally inside the crossing reducer.
I will take a look at cleaning it up. I should have taken a deeper look before integrating it, as you write, it really does not not sound clean.
Thanks. I came across this when Matthias and I investigated the current GEF4 Layout component a bit closer. In general, I think we will have to take a deeper look at which core abstractions (i.e. layout interfaces) we really need to serve as input and output for the layout algorithms and what properties these are going to provide specifically (like position, size, etc., which are used by all algorithms) and which generically (we will probably need a mechanism to store and retrieve algorithm-specific properties via the interfaces as well, otherwise they will only be usable by a specific set of algorithms). That things like the NodeWrapper have been added for Sugiyama indicates IMHO that the current set of abstractions was not quite sufficient (as the required properties were not delivered via the interfaces). We could for instance think about using the SubgraphLayout, which is used by the other algorithms to represent grouped-together nodes, also to represent layers (or rather ranks of nodes) as used by the Suyigama algorithm instead of the special NodeWrapper representations, which has been introduced to capture the layer index and index properties that are needed by this algorithm. Matthias is currently gathering information on how the different layout interfaces are actually used by the different algorithms, and which properties they use in particular. He will report his findings in bug #372365, and we can discuss a more general refactoring there, dealing with things like I have reported here in advance to make a potential larger scale refactoring a bit more easy.
Sorry for disappearing for a while, I finally had time to take a deeper look. I have added a lot of fixes to the crossingreducer and layerprovider implementations to make it more usable, but a working solution is still further away. About the unnecessary abstractions: the NodeWrapper is used to collect the graph layering information (more specifically, both the layer identifier and the layer-relative position of the nodes) together with helper lists to access the neighboring layers. For layer-based algorithms this helps a lot in keeping the code understandable, but for other algorithms (e.g. the spring layout), this information is completely unnecessary. On the other hand, the LayerProvider should be clearly reusable in tree-based algorithms (that is why it was proposed as a separate interface). SubgraphLayout is different: it represents collapsible subtrees, while the nodewrappers manage information on a more global level (and the crossing reducer has to calculate edge crossings based on this implementation quite often). In other words, the work Matthias has reported in bug #372365 is important for this aspect, as it provides great input to which way to continue. I try to do some more work about this in the near future, but so far I have a bad track record of such promises, but lets hope for the best.
Zoltan, do you see a chance we can cleanup this for Neon? If we aim at releasing GEF4 as 1.0.0, I think we should try to clean up the algorithm implementations as well.
(In reply to Alexander Nyßen from comment #4) > Zoltan, do you see a chance we can cleanup this for Neon? If we aim at > releasing GEF4 as 1.0.0, I think we should try to clean up the algorithm > implementations as well. Sorry for not answering before. I try my best to come up with something shortly, but I have been away from Zest for a while. I agree that this should be cleaned up as soon as possible.
Zoltan, can we expect something here for Neon?
(In reply to Alexander Nyßen from comment #6) > Zoltan, can we expect something here for Neon? I did have a short look at the issue, and while I have a quick fix available for keeping the padding nodes internal, I did not have time enough to test it. At the very least, I will find some time to test this fix this week or next, as it causes externally visible problems. About the other stuff, (larger internal cleanups), I am afraid I cannot promise anything (especially until M6). I am sorry, but I am in the process of finishing my PhD, and it takes a lot of time and energy on my side.
I have uploaded a simple removal of unpadded nodes to BarycentricCrossingProvider. In my limited testing, it seemed to work as expected. However, as multiple issues were mentioned it this issue, I would still keep it open. And I am sorry, but I most likely will not have time to do further cleanup here before Neon.
