Finally!! check for node overlap in FDL!

Help
2011-05-21
2013-05-29
  • Jason D'Silva

    Jason D'Silva - 2011-05-21

    Ok,
    I am actually surprised it took me so long to come up with this method -_-.
    This partially addresses the issue in https://sourceforge.net/projects/prefuse/forums/forum/343013/topic/4536279.

    The main issue is the stopping criteria for a Force Directed Layout.  As we all know, for the FDL, the FDLs keep moving even after each node has its own space.  To prevent this, we need some sort of stopping condition.  This can be done by forcefully making the visualization to stop.  However, this requires the developer to specify a time AFTER which the FDL stops.
    The time taken for an FDL to properly spread out will vary upon the number of nodes, forces, etc.  Hence, we cannot "hardocde" a specific time to stop the FDL.  Another stopping criteria can be the percentage of overlapping nodes.  This percentage can be tweaked to the user's satisfaction.  The following method allows the user to stop the movement of the nodes after a certain percentage of overlap is reached,

    import java.util.Iterator;
    import prefuse.Visualization;
    import prefuse.action.Action;
    import prefuse.visual.NodeItem;
    import prefuse.visual.VisualItem;
    public class CustomStoppingAction extends Action{
        private int _totalNodes;
        private double _stoppingOverlapPercentage;
        public CustomStoppingAction(Visualization p_vis, int totalNodes, double stoppingOverlapPercentage)
        {
            //super(duration, stepTime);
            m_vis = p_vis;
            _totalNodes = totalNodes;
        }
    
        @Override
        public void run(double arg0) {
            // TODO Auto-generated method stub
            try
            {
                Iterator outerIter = m_vis.visibleItems();
                int outerCount = 0;
                int intersectCount = 0;
                while (outerIter.hasNext())
                {
                    VisualItem outerItem = (VisualItem)outerIter.next();
                    if (outerItem instanceof NodeItem)
                    {
                        Iterator innerIter = m_vis.visibleItems();
                        int innerCount = 0;
    
                        while(innerIter.hasNext())
                        {
                            VisualItem innerItem = (VisualItem)innerIter.next();
                            if (innerItem instanceof NodeItem)
                            {
                                if(outerCount < innerCount)
                                {
                                    if(outerItem.getBounds().intersects(innerItem.getBounds()))
                                    {
                                        intersectCount++;
                                    }
                                }
                            }
                            innerCount++;
                        }
                    }
                    outerCount++;
                }
    
                if((intersectCount/(float)_totalNodes) <= _stoppingOverlapPercentage)
                {
                    m_vis.setValue("graph.nodes", null, VisualItem.FIXED, true);
                }
    
            }
            catch(Exception ex)
            {
                System.out.println(ex.getMessage());
            }
        }
    }
    

    From observation, this action is quite costly.  Hence, it cannot be run with the normal steptime.  Hence, we define the following action list, for this particular action,

    ActionList stoppingList = new ActionList(m_vis, Activity.INFINITY);
            stoppingList.setStepTime(7000);
            stoppingList.add(new CustomStoppingAction(m_vis, g.getNodeCount(), 0.2));
    

    This action list can be added to the visualization and run.  The action will run every 7 seconds.  The downside to this action, is its cost.  Suggestions to improve this method are welcome :).

     
  • Jason D'Silva

    Jason D'Silva - 2011-05-21

    Edit to above post:

    Modify the constructor to the following:

    public CustomStoppingAction(Visualization p_vis, int totalNodes, double stoppingOverlapPercentage)
        {
            m_vis = p_vis;
            _totalNodes = totalNodes;
            _stoppingOverlapPercentage = stoppingOverlapPercentage;
        }
    
     
  • Jason D'Silva

    Jason D'Silva - 2011-05-21

    Ok, I just realized that the criteria is not actually a percentage.  Its more of a ratio between numberOfIntersections and total number of nodes.  That still works though.  An additional condition can be added as follows,

    if((currentIntersectPercentage <= _stoppingOverlapPercentage) || Math.abs(_prevPercentage-currentIntersectPercentage) <= 0.02)
                {
                    m_vis.setValue("graph.nodes", null, VisualItem.FIXED, true);
                }
    
     
  • Amendra

    Amendra - 2012-12-23

    Dear jasonnovember,

    I am also having the same problem as the user who posted the question. And i tried your solution to solve my problem. But I think I am missing currentIntersectPercentage and _prevPercentage variable for my if condition. How can we calculate those variables. It would be great if I could get some ideas from you.
    Thank You.

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks