Fun with edges!

Show and Tell
1

Did you know that it takes all the Graphviz engines at least 4 points to define an edge, even a straight edge? (splineType | Graphviz)
Not being a mathematician, I don’t know much (anything) about cubic B-spline, so I decided to let Graphviz show me how these splines are defined. I wrote a small GVPR program (what else) to add a point-shaped node on top of every point included in an edge pos for any graph.
What did I learn?

  • After staring at hundreds of augmented graphs, splines start to make some sense
  • A straight line spline is 4 (or more) points, that all fall on a straight line (algebraically) (poor definition)
  • circo & twopi use very different routines to define their edges (see below)
  • with some care, you can tweak the points that define an edge

The program:

//
//  show the points that define an edge (all edges are splines)
//
BEGIN{
  int i, cnt, c=0, maxc, pointNum=0;
  string st, Color="", colors[int], tok[int];
  graph_t Root;

  string nextColor(){
    string C;
    C="#" + colors[c++];
    if (c==maxc)c=0;
    return(C);
  }

  void addPt(string Pos){
    string pname, nameStr="__splinePt__";
    node_t pn;

    pname=nameStr + (string)pointNum;
    pointNum++;
    pn=node(Root,pname);
    pn.pos=Pos;
    pn.shape="point";
    pn.color="red";  // if you want all points to be red
    pn.color=Color;  // multi-colored
    pn.width=.05;
    pn.label="";
  }
}
BEG_G{
  Root=$G;
  maxc=split("CC0000 CC6600 CC0066 00BB66 00BB00 000099 770000 007700 000077",colors);
}
E{
    Color=nextColor();
    cnt=tokens($.pos, tok);
    for (i=0;i<cnt;i++){
      st=gsub(tok[i],"[	 ]"); // remove tabs and spaces !!
      if (st=="[es]*"){  
	  st=substr(st,2);
      }
      addPt(st);
    }
}

Command line (Linux):
dot/circo/neato/twopi -Tdot myfile.gv | gvpr -cf showSplinePoints.gvpr | neato -n2 -Tpng >myfile.png
Some examples:
d
edgeFlip0
b786
multiLoop1

twopi did this! (graph below)
clusterPlacement2

2 Likes
2

Interesting. We generated all those way out control points, to draw nearly straight lines? Weird.

We used splines to describe lines because we didn’t want to start defining different types of curves so it was easier to just use piecewise cubic Beziers, which we got straight from the Adobe Postscript definition. I’m a little surprised we choose 4 distinct points, and not just repeat the endpoints, which is perfectly valid (i.e. [x0,y0,x0,y0,x1,y1,x1,y1]) but maybe we wanted to avoid that particular kind of degeneracy.

3

Very interesting, indeed. Thanks for sharing!

So when parsing the “plain” output, can one safely assume that the 4th element (“n” == number of control points) will always be >= 4, and that there will be at least 4 pairs of coordinates? If so, it would help to add that fact to the documentation, e.g. in “libguide.pdf” and presumably in other places as well.

Since the tail and head are given, one would imagine that for a straight line, there wouldn’t be any control points at all (but I am also not a mathematician).

4

Yep, head (optional) tail (optional) 4 points (X/Y pairs) 0 or more sets of 3 points.
If there are any triples (3 points), the spline algorithm uses the last preceeding point before the triple to make a set of 4 points. (awkward sentence , let’s try again)
The spline algorithm works in sets of 4 points, so the last point in one set of 4 points is also the first point in the next set of 4.