Skip to content

cgraph library out-edge ordering doesn't conform to the documentation

My Graphviz application generates a visualization of an attributed parse tree produced from an Attribute Grammar Evaluator, implemented on top of a bottom-up LR(k) Parser. The attributed parse tree visualization generation is implemented using the cgraph library as a strict directed graph where all nodes, save for the tree's root node, have exactly one in-edge. I use agwrite() to write the DOT-language representation of the attributed parse tree visualization into a file for off-line layout and rendering.

For this application, the left-to-right ordering of out-edges from an interior node is important. The Cgraph library tutorial (cgraph.pdf) contains the following statements that led me to believe this would be trivial:

  • At the end of Section 6, Traversals: "Traversals are guaranteed to visit the nodes of a graph, or edges of a node, in their order of creation in the root graph ..."
  • At the start of Section 16, Open Issues: "Node and Edge Ordering. The intent in Cgraph’s design was to eventually support user-defined node and edge set ordering, overriding the default (which is object creation timestamp order)."

In my initial implementation, the agwrite() function did not traverse the out-edges of my application's parse trees in edge-creation order in some cases, so the visualization did not always correspond to the left-to-right parse of the input sentence.

Inspecting the cgraph implementation, I found that the code for the edge compare function agedgeseqcmpf() in edge.c, used when adding a new out-edge, orders the edges by creation timestamp of the out-edge head node and not the out-edge itself (if both out-edges have the same head node, the out-edges are ordered by edge-creation order).

I was able to work-around this in my application by replacing the built-in edge compare function. Attached cgraph_edge_order.c is a trivial sample application that demonstrates the before and after result.

While it isn't clear to me why agedgeseqcmpf() is written as it is, it has been that way since edge.c was first added to the repository, so it must have some design rationale.