Comment 1 Li Ding 2006-05-18 11:58:53 EDT

GEF version: 3.2

Comment 2 Steven R. Shaw 2006-05-18 12:01:33 EDT

You'll need to provide a test case that demonstrates this in order for us to investiate...

Comment 3 Steven R. Shaw 2006-05-18 12:03:29 EDT

Potential candidate for RC4

Comment 4 Randy Hudson 2006-05-18 15:20:43 EDT

The graph layout algorithm is recursive in many places, removing the first place will probably just expose another overflow. I don't think eliminating recursion is a simple task.

Comment 5 Li Ding 2006-05-19 13:46:05 EDT

The error is reproduced with my plugins. Which data you need to investigate ? I added sever print statements in the first for loop of depthFirstCutValue(). The part of printout likes this:

inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@2e162e16 edge=org.eclipse.draw2d.graph.Edge@2daa2daa
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@13d813d8 (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@2e822e82 edge=org.eclipse.draw2d.graph.Edge@2e162e16
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@1c9e1c9e (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@2eee2eee edge=org.eclipse.draw2d.graph.Edge@2e822e82
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@25642564 (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@2f5a2f5a edge=org.eclipse.draw2d.graph.Edge@2eee2eee
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@2e2a2e2a (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@2fc62fc6 edge=org.eclipse.draw2d.graph.Edge@2f5a2f5a
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@36f436f4 (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@30323032 edge=org.eclipse.draw2d.graph.Edge@2fc62fc6
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@3fba3fba (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@309e309e edge=org.eclipse.draw2d.graph.Edge@30323032
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@48804880 (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@310a310a edge=org.eclipse.draw2d.graph.Edge@309e309e
in a new depthFirstCutValue, node=N(SystemNodeEditPart( org.eclipse.gmf.runtime.notation.impl.NodeImpl@51465146 (visible: true, type: null, mutable: true) ))
inside first for loop, list.size=1 i=0
inside first for loop,if e=org.eclipse.draw2d.graph.Edge@31763176 edge=org.eclipse.draw2d.graph.Edge@310a310a



Also noticed that the overflow did not happen if I run in debug mode.

Comment 6 Steven R. Shaw 2006-05-23 22:35:56 EDT

This doesn't help much... is there an example graph that you can construct that demonstrates this?  Is it possible there's a circular dependency in the edges that isn't being detected and reversed?

Comment 7 Li Ding 2006-05-25 15:21:04 EDT

I don't think there is circular dependency in the edges becuase if I run it in debug mode, the StackOverflow did not happen and diagram did show up although it took very long time.

I know it is hard to track down. I have model file but not sure if it is helpful for you by just looking the file. I will update this bug if I can reproduce with smaller model.

Comment 8 Randy Hudson 2006-05-25 15:44:33 EDT

Try creating a graph that is just a long chain of one node connected to the next. Cycles are not the problem, since this part of the algorithm does not consider direction of edges.

Comment 9 Steven R. Shaw 2006-05-29 10:55:15 EDT

Looks like the client is using GMF.

Comment 10 Mohammed Mostafa 2006-05-31 12:11:30 EDT

a Trick we can do to improve the situation, although it would not fix all cases, is to add a context member to the class and get ride of the 2 paramters in depthFirstCutValue. This could be applied in other recurtsive use cases as well. By doing that we will be able to handle depper use cases but eventually we will hit the problem again (unless we re-write the methods to use loop instead in recursion which i do not beileve is possible in this release)

Comment 11 Anthony Hunter 2006-07-14 09:00:02 EDT

Any further word on this defect, is this a 3.2.1 candidate?

Comment 12 Anthony Hunter 2006-08-11 14:45:48 EDT

Changing to RESOLVE REMIND based on the above comments.
Reporter to re-open with more information if enhancement is still required.

Comment 13 Mohammed Mostafa 2006-09-26 11:11:51 EDT

This is an actual problem; there are few places in the rank assignment solver where stack over flow error will happen when used with big graphs ; for example updateMinMax

Comment 14 Mohammed Mostafa 2006-10-12 11:23:38 EDT

2 implementatins for the updateMinMax usilng loop instead of recursion to avoid stack over flows 

1 - 

void updateMinMax(Node root, int min) {
    int count = min;
    final class ObjectData{
        ObjectData parent = null;
        Node node = null;
        int refCount = 0 ;
        public ObjectData(ObjectData parentNode,Node node){
            parent = parentNode;
            this.node = node;
        }
        
        public ObjectData getParentData(){
            return parent;
        }
        public Node getNode(){
            return node;
        }
        public void inc(){
            refCount++;
        }
       public void dec(){
            refCount--;
        }
       public int getRefCount(){
            return refCount;
        }
    }

    List data = new ArrayList();
    data.add(new ObjectData(null,root));
    do {
        ObjectData objectData = (ObjectData)data.get(data.size()-1);
        Node node = objectData.getNode();
        setTreeMin(node, count);
        data.remove(data.size()-1);
        EdgeList edges = getSpanningTreeChildren(node);
        for (int i = edges.size()-1; i >=0 ; i--){
            Node currentNode = getTreeTail(edges.getEdge(i));
            ObjectData childNode = new ObjectData(objectData,currentNode);
            data.add(childNode);
            objectData.inc(); 
        }
        if (objectData.getRefCount()==0){
            setTreeMax(node, count);
            ObjectData parentData = objectData.getParentData();
            count++;
            while (parentData!=null && parentData.getRefCount()>0 && objectData.getRefCount()==0){
                parentData.dec();
                if (parentData.getRefCount()==0){
                    setTreeMax(parentData.getNode(), count);
                    count++;
                }
                objectData = parentData;
                parentData = parentData.getParentData();
            }
        }
    }while (!data.isEmpty());
 }

2- void updateMinMax(final Node root, int count) {
	class Entry {
		Entry(Node node) {
			this.node=node;
		}
		Node node;
		boolean recursed;
	}
	Stack stack = new Stack();
	stack.push(new Entry(root));
	
	while (!stack.isEmpty()) {
		Entry current = (Entry) stack.peek();
		if (!current.recursed) {
			setTreeMin(current.node, count);
			current.recursed = true;
			EdgeList edges = getSpanningTreeChildren(current.node);
			for (int i = edges.size() - 1; i >= 0; i--)
				stack.push(new Entry (getTreeTail(edges.getEdge(i))));			
		} else {
			setTreeMax(current.node, count++);
			stack.pop();
		}
	}
}


we will invistigate the performance of each implementation and use the faster one, also we will try to re-write depthFirstCutValue using loops as well

Comment 15 Mohammed Mostafa 2007-05-24 11:41:31 EDT

move to inbox. 

The stack over flow issue is a generic issue in the GraphLayout algorit