Skip to main content

Edge Separation

This tutorial will walk you through developing a process that simply separate edges when there are multiple edges between two nodes.


 

What we want to do is pretty simple:

When we have lots of edges between two nodes, it is pretty hard to keep track of them, especially since the default behavior piles them up and you really see one edge.

This would typically be called as a post-treatment after another layout algorithm.


 

In order to do this, we will just need the graph itself, and we will change the position of the edges.

To make it simple we will completely ignore the position of the edges before treatment, so we will lose any special layout done to the edges before applying the algorithm.

 

#ifndef EDGESEPARATION_H
#define EDGESEPARATION_H

#include <tulip/TulipPlugin.h>

class EdgeSeparation : tlp::LayoutAlgorithm
{
  public:
    EdgeSeparation(const tlp::PropertyContext& context);
    virtual bool run();
  private:
    //we keep in memory the nodes we have treated, so we do no treat them twice
    std::set<tlp::node> _treatedNodes;
};

#endif //EDGESEPARATION_H


 

This will get us started.

Now we only need to define the body of the run method.

So basically, we will walk through the edges, and move them a bit so we see we have more than one edge.


 

The default behavior we will apply is:

  • Do not move the first edge

  • move every even edge “over”

  • move every odd edge “under”

Over and under being relative to the first edge and its direction, that is.

For the rest of the tutorial, we will let the code speak, as it is pretty self-explanatory, and commented especially for the occasion :)

 

bool EdgeSeparation::run() {
  //Using an Iterator is a tad faster, but you HAVE TO DELETE the Iterator, or it will eat your memory.
  //If you tend to forget about deleting stuff, use the forEach macro
  Iterator<node>* nodeIterator = graph->getNodes();
  //Iterate over all the nodes, 
  while(nodeIterator->hasNext()) {
    const node currentNode = nodeIterator->next();
    
    //first we copy the existing layout into the resultLayout
    LayoutProperty* viewLayout = graph->getProperty<LayoutProperty>("viewLayout");
    layoutResult->setNodeValue(currentNode, viewLayout->getNodeValue(currentNode));
    
    //if this node has not been treated before we proceed
    if(_treatedNodes.find(currentNode) == _treatedNodes.end()) {
      
      //mark this node as treated
      _treatedNodes.insert(currentNode);
      
      //this will hold the subset of edges connected to a node we are interested in.
      //as key we have the nodes that are linked to the current node by at least one edge
      //as value we have the set of edges linking the current node and the key node 
      map<node, set<edge> > nodesEdges;
      
      //we iterate over all the edges of this node
      Iterator<edge>* edgeIterator = graph->getInOutEdges(currentNode);
      while(edgeIterator->hasNext()) {
        const edge currentEdge = edgeIterator->next();
        //we get the node at the other end of the current edge
        const node opposite = graph->opposite(currentEdge, currentNode);
        //and mark it as treated
        _treatedNodes.insert(opposite);
        
        //check whether a set has already been inserted, if not insert it.
        if(nodesEdges.find(opposite) == nodesEdges.end()) {
          std::set<edge> temp;
          nodesEdges.insert(pair<node, std::set<edge> >(opposite, temp));
        }
        //add this edge to the list of edges linked to this node
        nodesEdges.at(opposite).insert(currentEdge);
      }
      delete edgeIterator;
      
      //now we look at each of these edges
      for(map<node, set<edge> >::const_iterator mapIterator = nodesEdges.begin(); mapIterator != nodesEdges.end(); ++mapIterator) {
        //we get the coordinates of the current node and its opposite
        Coord currentNodecoord = viewLayout->getNodeValue(currentNode);
        Coord oppositeNodecoord = viewLayout->getNodeValue(mapIterator->first);
        
        //we normalize this vector, so we will be able to use the scalar product to determine the ways the edges will go
        Coord vector = currentNodecoord - oppositeNodecoord;
        vector /= vector.norm();
        Coord normal(-vector.getY(), vector.getX(), vector.getY());
        
        //initialize how far from the original edge the edges will go
        float xPlus = 0.5;
        float xMinus = -0.5;
        
        //for each edge linking these two nodes (the current node and the current key of the nodesEdges map), we separate the edges
        for(set<edge>::const_iterator processingEdge = mapIterator->second.begin(); processingEdge != mapIterator->second.end(); ++processingEdge) {
          bool isInEdge = graph->target(*processingEdge) == mapIterator->first;
          //if this edge is an in edge, it will go "up", else it will go "down" of the current edge.
          float x = isInEdge ? xPlus : xMinus;
          std::vector<Coord> newEdge;
          
          //we add control points, or waypoints to the edge at 1/4 of its length, and another one at 3/4 (so we will see more clearly than if we used only one control point)
          //also, this is way prettier when using bezier curves :)
          Coord quarterControlPoint(currentNodecoord + (oppositeNodecoord - currentNodecoord)/4 + normal * x); 
          Coord threeQuartersControlPoint(currentNodecoord + (oppositeNodecoord - currentNodecoord)*3/4 + normal * x); 
          
          //depending which kind of edge we encountered, we increment the distance the next edge will be from the original edge.
          if(isInEdge)
            xPlus += 0.5;
          else
            xMinus -= 0.5;
          
          //we add the control points in the right order, so that we don't get an adge going to the 3/4 waypoint, then the 1/4 waypoint, then to the opposite node.
          if(currentNode == graph->source(*processingEdge)) {
            newEdge.push_back(quarterControlPoint);
            newEdge.push_back(threeQuartersControlPoint);
          }
          else {
            newEdge.push_back(threeQuartersControlPoint);
            newEdge.push_back(quarterControlPoint);
          }
          
          //now we can finally set the value on the edge.
          layoutResult->setEdgeValue(*processingEdge, newEdge);
        }
      }
    }
  }
  
  //Don't forget to delete iterators !
  delete nodeIterator;
  return true;
}

Let's just not forget to use the Tulip macro to add this plugin ;)

LAYOUTPLUGIN(EdgeSeparation, "Edge Separation", "Charles Huet", "10/06/10", "This plugin separates edges between two nodes.", "1.0")