Home » Eclipse Projects » GEF » Zest tree algorithms
| Zest tree algorithms [message #242818] |
Fri, 09 May 2008 09:00  |
Eclipse User |
|
|
|
Originally posted by: ftordi.smaeur.com
Hi,
I have currently some problem with tree and horizontal tree layout
algorithms. The problem is when there is multiple path to join a node some
nodes are placed exactly at the same place and overlapped.
Is there a way to change it?
Must I have to browse my nodes and replace it ?
Cheers Fabien
|
|
|
| Re: Zest tree algorithms [message #243011 is a reply to message #242818] |
Sun, 18 May 2008 05:17  |
| Eclipse User |
|
|
|
Originally posted by: irbull.cs.uvic.ca
Removing overlapping nodes is a hard problem. I have tried a number of
different solutions, but each have their drawbacks. The best approach I
found is to combine the tree layout with the horizontal shift:
viewer.setLayoutAlgorithm(new
CompositeLayoutAlgorithm(LayoutStyles.NO_LAYOUT_NODE_RESIZIN G, new
LayoutAlgorithm[] { new
DirectedGraphLayoutAlgorithm(LayoutStyles.NO_LAYOUT_NODE_RES IZING), new
HorizontalShift(LayoutStyles.NO_LAYOUT_NODE_RESIZING) }));
Cheers,
Ian
Fabien wrote:
> Hi,
>
> I have currently some problem with tree and horizontal tree layout
> algorithms. The problem is when there is multiple path to join a node
> some nodes are placed exactly at the same place and overlapped.
> Is there a way to change it? Must I have to browse my nodes and replace
> it ?
>
> Cheers Fabien
>
|
|
|
| Re: Zest tree algorithms [message #243087 is a reply to message #243011] |
Thu, 22 May 2008 15:58 |
| Eclipse User |
|
|
|
Originally posted by: ftordi.smaeur.com
Ian Bull wrote:
> Removing overlapping nodes is a hard problem. I have tried a number of
> different solutions, but each have their drawbacks. The best approach I
> found is to combine the tree layout with the horizontal shift:
> viewer.setLayoutAlgorithm(new
> CompositeLayoutAlgorithm(LayoutStyles.NO_LAYOUT_NODE_RESIZIN G, new
> LayoutAlgorithm[] { new
> DirectedGraphLayoutAlgorithm(LayoutStyles.NO_LAYOUT_NODE_RES IZING), new
> HorizontalShift(LayoutStyles.NO_LAYOUT_NODE_RESIZING) }));
> Cheers,
> Ian
> Fabien wrote:
>> Hi,
>>
>> I have currently some problem with tree and horizontal tree layout
>> algorithms. The problem is when there is multiple path to join a node
>> some nodes are placed exactly at the same place and overlapped.
>> Is there a way to change it? Must I have to browse my nodes and replace
>> it ?
>>
>> Cheers Fabien
>>
Hi,
Thank you for your answer but when I use the Horizontal Shift on a Tree
layout it makes a column with my nodes. So I don't found another solution
for my problem. I'm using a DirectedGraphLayoutAlgorithm and I must use a
composite layout with horizontal shift but I would like to know if their
is another method with the directed graph to display it without
overlapping because I must have more spaced nodes than with the directed
graph.
I just use the layouts with GEF so may be it's a reason for some problems
that I have.
Cheers,
Fabien
|
|
|
| Re: Zest tree algorithms [message #243318 is a reply to message #243087] |
Mon, 02 June 2008 14:24 |
 Michelle Tadmor
Messages: 23
Registered: July 2009 |
Junior Member |
|
|
------=_Part_2125_5666164.1212416712697
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Hey Fabien,
I had similiar trouble and i wrote a tree layout algorithm
I've attatched the file with the code.
cheers
michelle
------=_Part_2125_5666164.1212416712697
Content-Type: application/octet-stream; name=gxtreelayoutalgorithm.java
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename=gxtreelayoutalgorithm.java
package com.softwareag.applinx.workbench.views.map;
import java.util.*;
import org.eclipse.zest.layouts.algorithms.AbstractLayoutAlgorithm;
import org.eclipse.zest.layouts.dataStructures.InternalNode;
import org.eclipse.zest.layouts.dataStructures.InternalRelationship ;
/**
* A layout algorithm that spreads the directed graph as a tree from top down
* first a root is chosen (we offer a default way that may be overridden)
* then a tree is first spread from that root down in a grid fashion
* after which it is laid out bottom up to horizontally shift nodes.
* if the graph contains non connected subgraphs then the process of
* choosing a root and spreading it's child tree is continued.
*
* @author ilmta
*/
public class GXTreeLayoutAlgorithm extends AbstractLayoutAlgorithm {
private double horSpacing = 40;
private double verSpacing = 60;
public GXTreeLayoutAlgorithm(int styles) {
super(styles);
}
protected void applyLayoutInternal(InternalNode[] entitiesToLayout, InternalRelationship[] relationshipsToConsider,
double boundsX, double boundsY, double boundsWidth, double boundsHeight) {
List<InternalNode> entitiesList = asList(entitiesToLayout);
List<InternalRelationship> relationshipsList = asList(relationshipsToConsider);
// --- build the node matrix without laying out first ---//
List<List<GXMoreThanNode>> rows = buildNodeMatrix(entitiesList, relationshipsList);
// --- layout the nodes --- //
// we're going to put them together bottom - up.
Collections.reverse(rows);
// the vertical size of a node line
int verticalLineSize = (int)(entitiesToLayout[0].getLayoutEntity().getHeightInLayou t() + verSpacing);
// the vertical location we begin placing the nodes from
int heightSoFar = (int) (((rows.size()-1) * verticalLineSize) + verSpacing);
// place bottom most row first - just center it.
List<GXMoreThanNode> childRow = rows.get(0);
int nodeSpacing = (int) (horSpacing + childRow.get(0).getNode().getLayoutEntity().getWidthInLayout ());
int x = (int) ((boundsWidth / 2) - ((childRow.size()/2) * nodeSpacing));
placeStrand(childRow, x, heightSoFar, nodeSpacing);
// place parent rows
List<GXMoreThanNode> parentRow;
// run through all parent rows
for (int i = 1; i < rows.size(); i++) {
// initialize stuff we'll need
parentRow = rows.get(i);
heightSoFar -= verticalLineSize;
placeRow(parentRow, heightSoFar);
}
}
/**
* Lays out row with respect to it's children.
*
* @param yLocation - the vertical location to start placing the nodes.
* @param row - the row who's nodes we'd like to lay out.
*/
private void placeRow(List<GXMoreThanNode> row, int yLocation) {
List<GXMoreThanNode> childlessStrand = new ArrayList<GXMoreThanNode>();
GXMoreThanNode parentLeft = null;
// for each parent in this parent row
for (int j = 0; j<row.size(); j++) {
GXMoreThanNode parentRight = row.get(j);
// if the node has children
if (!parentRight.getChildren().isEmpty()) {
// place the node in the center above his children
int parentX = 0;
for (GXMoreThanNode child:parentRight.getChildren()) {
parentX+=child.getX();
}
parentX /= parentRight.getChildren().size();
parentRight.setLocation(parentX, yLocation);
// and layout the childless strand
if (!childlessStrand.isEmpty()) {
placeChildless(childlessStrand, parentLeft, parentRight, yLocation);
childlessStrand.clear();
}
parentLeft = parentRight;
} else { // accumulate the childless nodes
childlessStrand.add(parentRight);
}
}
// place childless who are extra on the right. as in did not get taken care of when
// the parents were laid out.
if (!childlessStrand.isEmpty()) {
placeChildless(childlessStrand, parentLeft, null, yLocation);
}
}
/**
* Builds the matrix of nodes. each node will be wrapped with necessary innformation
* such as who are the direct children and parent (only visually in the graph not the
* actual relationships) the returned matrix is organized more or less as the real tree.
*
* @param entitiesList - entities to place in the matrix
* @param relationshipsList - the relationships between the entities given
*
* @return the matrix - (a list of rows of nodes)
*/
private List<List<GXMoreThanNode>> buildNodeMatrix(List<InternalNode> entitiesList,
List<InternalRelationship> relationshipsList) {
List<List<GXMoreThanNode>> rows = new ArrayList<List<GXMoreThanNode>>();
while (!entitiesList.isEmpty()) {
InternalNode root = getFirstEntity(entitiesList, relationshipsList);
// add root row if necessary
if (rows.isEmpty()) {
rows.add(new ArrayList<GXMoreThanNode>());
rows.add(new ArrayList<GXMoreThanNode>());
}
// lay out the current root node and remove it from the list of entities left
entitiesList.remove(root);
GXMoreThanNode moreThanRoot = new GXMoreThanNode(root, null);
rows.get(0).add(moreThanRoot);
// build the tree that spreads from this current root.
builtTreeFromRoot(moreThanRoot, entitiesList, relationshipsList, rows.get(1), rows);
}
trimEmptyRows(rows);
return rows;
}
/**
* Remove rows that are empty. This should only be the last row but since it's not too expensive
* better safe than sorry.
*
* @param rows - to trim
*/
private void trimEmptyRows(List<List<GXMoreThanNode>> rows) {
List<List<GXMoreThanNode>> rowsCopy = new ArrayList<List<GXMoreThanNode>>(rows);
for (List<GXMoreThanNode> row:rowsCopy) {
if (row.isEmpty()) {
rows.remove(row);
}
}
}
/**
* A childless stran is a "problem" in general because they break the evenness of the tree
* There are three types of such strands,
* extra nodes to the left, extra to the right, or extra in between parents.
* This method places those strands in spot.
*
* @param childlessStrand - the childless node to be laid out.
* @param parentLeft - the nearest parent on the left (or <value>null</value> if none such exists)
* @param parentRight - the nearest parent on the right (or <value>null</value> if none such exists)
* @param yLoc - the vertical location to lay out the nodes on.
*/
private void placeChildless(List<GXMoreThanNode> childlessStrand,
GXMoreThanNode parentLeft, GXMoreThanNode parentRight, int yLoc) {
int startMark = 0;
int spacing = (int)(childlessStrand.get(0).getNode().getLayoutEntity().get WidthInLayout() + horSpacing);
// There's only a parent on the right
if (parentLeft==null && parentRight!=null) {
startMark = parentRight.getX() - (spacing *childlessStrand.size());
} // there's a parent on the left
else if ( parentLeft!=null) {
startMark = parentLeft.getX() + spacing;
// there's a parent on the right as well meaning the childless are between two parents
// we need to make there's enough room to place them
if (parentRight != null) {
int endMark = startMark + (spacing*childlessStrand.size());
// if there isn't enough room to place the childless between the parents
if (endMark > parentRight.getX()) {
// shift everything on the right to the right by the missing amount of space.
shiftTreesRightOfMark(parentRight, endMark - parentRight.getX());
}
}
}
// now the room has been assured, place strand.
placeStrand(childlessStrand,startMark , yLoc, spacing);
}
/**
* Shifts the trees right of mark node
*
* @param mark to shift from
* @param shift - factor by which to move right by.
*/
private void shiftTreesRightOfMark(GXMoreThanNode mark, int shift) {
mark.setLocation(mark.getX() + shift, mark.getY());
GXMoreThanNode leftMostChild = getRightMostChild(mark);
List<GXMoreThanNode> treeRoots = leftMostChild.getRow().subList(leftMostChild.getRow().indexO f(leftMostChild), leftMostChild.getRow().size());
for (GXMoreThanNode root : treeRoots) {
shiftTree(root, shift);
}
}
/**
* Returns the right most child of parent
*
* @param parent
*
* @return the right most child of parent given.
*/
private GXMoreThanNode getRightMostChild(GXMoreThanNode parent) {
GXMoreThanNode rightMost = parent.getChildren().get(0);
// run through children
for (GXMoreThanNode child:parent.getChildren()) {
if (child.getX() < rightMost.getX()) {
rightMost = child;
}
}
return rightMost;
}
/**
* Shifts the given tree by the shift factor given to the right.
*
* @param root - root of tree to shift
* @param shift - factor to shirt by
*/
private void shiftTree(GXMoreThanNode root, int shift) {
root.setLocation(root.getX() + shift, root.getY());
for (GXMoreThanNode child : root.getChildren()) {
shiftTree(child, shift);
}
}
/**
* Places the list of nodes horizontally at the given point and
* spaced on horizontally by given spacing.
*
* @param strand - list of nodes to be laid out.
* @param x - location to begin the placing
* @param y - vertical location to lay out the entire list.
* @param spacing the horizontal spacing between nodes.
*/
private void placeStrand(List<GXMoreThanNode> strand,
int x, int y, int spacing) {
for (GXMoreThanNode item : strand) {
item.setLocation(x, y);
x += spacing;
}
}
/**
* follows the root by all its children to wrap the all up with all the
* extra info needed and adds the tree to the matrix.
*
* @param currRoot - root to go over tree from
* @param entitiesList - entities available
* @param relationshipsList - relationship between the given entities
* @param currRow - the current row in the matrix we are working on
* @param rows - the matrix.
*/
private void builtTreeFromRoot(GXMoreThanNode currRoot, List<InternalNode> entitiesList,
List<InternalRelationship> relationshipsList,
List<GXMoreThanNode> currRow, List<List<GXMoreThanNode>> rows) {
// this is the first node that comes from the currRoot
// we'll use the mark to know where to continue laying out from
GXMoreThanNode mark = null;
List<InternalRelationship> relationshipsListCopy = new ArrayList<InternalRelationship>(relationshipsList);
// Orders the children of the currRoot in the given row (the row under it)
for (InternalRelationship rel: relationshipsListCopy) {
if (currRoot.getNode().equals(rel.getSource())) {
InternalNode destNode = rel.getDestination();
// if the destination node hasn't been laid out yet
if (entitiesList.contains(destNode)){
// place it in the row (as in lay it out)
GXMoreThanNode currNode = new GXMoreThanNode(destNode, currRoot.getNode());
currRoot.addChild(currNode);
currRow.add(currNode);
currNode.addedToRow(currRow);
entitiesList.remove(destNode);
// if this is the first node, save it as a mark.
if (mark == null) {
mark = currNode;
}
// remove the relationship since both of its ends have been laid out.
relationshipsList.remove(rel);
}
}
}
// if new children have been added
if (mark != null) {
// Create a next row if necessary
if (rows.size()-1 <= rows.indexOf(currRow)) {
rows.add(new ArrayList<GXMoreThanNode>());
}
List<GXMoreThanNode> nextRow = rows.get(rows.indexOf(currRow)+1);
for (int i = currRow.indexOf(mark); i<currRow.size(); i++ ) {
builtTreeFromRoot(currRow.get(i), entitiesList, relationshipsList, nextRow, rows);
}
}
}
/**
* Currently we will arbitrarily choose the first node that is not a destination i.e. it's a starting point\
* if none such exists we will choose a random node.
*
* @param entitiesList
* @param relationshipsList
*/
private InternalNode getFirstEntity(List<InternalNode> entitiesList, List<InternalRelationship> relationshipsList) {
List<InternalNode> entitiesLeft = new ArrayList<InternalNode>(entitiesList);
// go through all the relationships and remove destination nodes
for (InternalRelationship rel:relationshipsList) {
entitiesLeft.remove(rel.getDestination());
}
if (!entitiesLeft.isEmpty()) {
// throw in random for fun of it
// return entitiesLeft.get((int)(Math.round(Math.random()*(entitiesLef t.size()-1))));
return entitiesLeft.get(0);
}
// if all the nodes were destination nodes then return a random node.
// return entitiesList.get((int)(Math.round(Math.random()*(entitiesLis t.size()-1))));
return entitiesList.get(0);
}
/**
* Returns an ArrayList containing the elements from the given array.
* It's in a separate method and to make sure a new ArrayList is created
* since Arrays.asList(T ...) returns an unmodifiable array and throws runtime
* exceptions when an innocent programmer is trying to manipulate the resulting list.
*
* @param <T>
* @param entitiesToLayout
* @return
*/
private <T> List<T> asList(T[] entitiesToLayout) {
return new ArrayList<T>(Arrays.asList(entitiesToLayout));
}
protected int getCurrentLayoutStep() {
// do nothing
return 0;
}
protected int getTotalNumberOfLayoutSteps() {
// do nothing
return 0;
}
protected boolean isValidConfiguration(boolean asynchronous, boolean continuous) {
// do nothing
return true;
}
protected void postLayoutAlgorithm(InternalNode[] entitiesToLayout, InternalRelationship[] relationshipsToConsider) {
// do nothing
}
protected void preLayoutAlgorithm(InternalNode[] entitiesToLayout, InternalRelationship[] relationshipsToConsider,
double x, double y, double width, double height) {
// do nothing
// entitiesToLayout[0].getLayoutEntity().
}
public void setLayoutArea(double x, double y, double width, double height) {
// do nothing
}
public double getHorSpacing() {
return horSpacing;
}
public void setHorSpacing(double horSpacing) {
this.horSpacing = horSpacing;
}
public double getVerSpacing() {
return verSpacing;
}
public void setVerSpacing(double verSpacing) {
this.verSpacing = verSpacing;
}
/**
* wraps a node with useful info like parent and children etc.
*/
private class GXMoreThanNode {
private InternalNode m_node;
private InternalNode m_parent;
private List<GXMoreThanNode> m_children;
private List<GXMoreThanNode> m_row;
private boolean m_located = false;
private int m_y;
private int m_x;
public GXMoreThanNode(InternalNode node, InternalNode parent) {
m_node = node;
m_parent = parent;
m_children = new ArrayList<GXMoreThanNode>();
}
public void addedToRow(List<GXMoreThanNode> row) {
m_row = row;
}
public void setLocation(int x, int y) {
m_x = x;
m_y = y;
m_node.setLocation(x, y);
setLocated(true);
}
public void addChild(GXMoreThanNode currNode) {
m_children.add(currNode);
}
public List<GXMoreThanNode> getChildren() {
return m_children;
}
public void setLocated(boolean located) {
m_located = located;
}
public boolean isLocated() {
return m_located;
}
public InternalNode getNode() {
return m_node;
}
public InternalNode getParent() {
return m_parent;
}
public int getY() {
return m_y;
}
public void setY(int y) {
m_y = y;
}
public int getX() {
return m_x;
}
public void setX(int x) {
m_x = x;
}
public List<GXMoreThanNode> getRow() {
return m_row;
}
}
}
------=_Part_2125_5666164.1212416712697--
|
|
|
| Re: Zest tree algorithms [message #243339 is a reply to message #243318] |
Tue, 03 June 2008 10:48 |
| Eclipse User |
|
|
|
Originally posted by: ftordi.smaeur.com
Hi Michelle,
Thank you very much,
It works well and I don't have to change anything.
Some links are going to the top of figure but it stay understandable.
The nodes don't overlaps and it make clearer the view.
Is there some tips to make an horizontal tree layout with the same method?
Or have you ever develop an horizontal tree?
If not it don't matters.
Cheers,
Fabien
|
|
| |
| Re: Zest tree algorithms [message #243359 is a reply to message #243355] |
Tue, 03 June 2008 14:32 |
| Eclipse User |
|
|
|
Originally posted by: ftordi.smaeur.com
In fact I don't really know how to send a file into the newgroup
but I give you a link to show what I told.
http://dl.free.fr/eVrc5ViVZ/Capture.png
as you can see there is a link which point to the gray box and it comes
from the bottom of the graph. It's a big tree with complicated
dependencies.
I'm sorry if I'm not clear. So I'll try to talk clearer.
|
|
|
Goto Forum:
Current Time: Wed Apr 24 18:32:43 GMT 2024
Powered by FUDForum. Page generated in 0.03514 seconds |
] 
Search
Help
Register
Login
Home
