Home

Welcome to the elm-dagre wiki!

Introduction

This elm package implements the Sugiyama framework for graph drawing, using dagrejs as a reference. The wiki only gives details about dagre. To learn more about render, please see the source files. The wiki is aimed to help people who want to implement sugiyama style drawing in any other language.

Preliminaries

1. Read about Array inversions, it will be helpful in solving the crossing count problem, No literature is available or will be suggested by google, if you do not know what to search. I learned it the hard way. I almost deciphered the idea, but was presented with the exact same solution when I thought I made a breakthrough xD.
2. Revise Set theory, especially Posets and Precedence and Succeeding operators. It will be used in the research paper that assigns the coordinates.

Required Reading for Understanding the Whole Framwork

Short Notes To get an overview of the algorithm

1. Lecture-5 : Layer-Based Drawing from Automatic Graph Drawing WS-19/20 course by Prof. Dr. Reinhard von Hanxleden, Christoph Daniel Schulze, Sören Domrös und Niklas Rentz (Institut Fur Informatik).
2. Chapter-13 : Hierarchical drawing algorithms from Handbook of Graph Drawing and Visualization By CRC Press

To Understand all the phases in detail

The following research paper’s were referenced before implementation, most of the paper and literature is taken from the wiki page of Dagre.js.

1. Gansner, et al., “A Technique for Drawing Directed Graphs” to understand the basic skeleton.
2. Brandes and Köpf, “Fast and Simple Horizontal Coordinate Assignment” for Horizontal Coordinate Assignment (Phase 4)

Additional Notes

For Crossing Reduction Phase

1. BaryCenter Heuristic can be understood using the following research paper
   1. Markus et. al. An Efficient Implementation of Sugiyama’s Algorithm for Layered Graph Drawing
2. The barycenter as well as the median heuristic give a solution without crossings if one exists from Markus et. al..

Compatibility of doing it in elm

1. I searched the whole dagre implementation for any code with side effects to check if I could do it using a pure functional language like Elm. I did not find any side effect causing code, like use of random Numbers, timestamps or even Http requests.
2. I concluded that it is indeed possible to do it in the Elm.**
   1. ** : The dagrejs implementation will always be fast for large graphs since all the papers discussed above use Imperative Coding, and optimisations for Imperative Data structures, This means we can have a slower but a native version of the code, which I think can be improved if we reference the books like “Purely Functional Data Structures”

Current State Of Implementation

1. [X] Preprocessing : Removing Cycles
2. [X] Rank (Layer) Assignment
3. [X] Normalize (Adding Dummy Nodes for Long Edges)
4. [X] Vertex Ordering
   1. [X] Crossing Edges Counting
   2. [X] Crossing Minimisation (Median/BaryCenter)
5. [X] Coordinate Assignment
   1. [X] Horizontal Coordinate Assignment

1. [X] Preprocessing : Assigning priority to edges
2. [X] Vertical Alignment
3. [X] Horizontal Compaction
4. [X] Balancing
   1. [X] Vertical Coordinate Assignment

What can we expect as the output from this package

1. A Dictionary of Nodes and their coordinates, along with the coordinates for bend points (Control Points of long edges).
2. A Dictionary of all the edges and their maps to the Control Points.

Limitations

1. Only Simple Graphs Can be processed for layout.
   1. i.e. No Self Loops
   2. No Parallel edges
2. a->b and b->a edges is drawn as a single edge a <-> b.

Future Work / RoadMap

1. [ ] Add support for the following types of edges (both are useful for representing Finite State Automatons)
   1. [ ] Self loops (self arcs). Useful resource : Dagrejs v0.4.5.
   2. [ ] Bidirectional Edges as 2 separate edges .
2. Add Test Suit to the package.
3. [X] Improve Preprocessing Steps by adding a default cycle removal algorithm, for now only DAG (defined as AcyclicGrpah in elm-community/graphs) are assigned coordinates. All other graphs get an empty Dictionary.
4. [-] Implement other Rank/Layering assignment algorithm, currently we use Topological Sort (from elm-community/graph) for Rank Assignment. we can implement the following algorithms
   1. [ ] Network-Simplex
   2. [-] Longest Path Layering (Need to add support for weighted edges)
   3. [ ] Tight Tree
5. Improve Crossing Edge Count algorithm. The current implementation uses Insertion Sort for counting Edge crossing between Layers (O|E|^2). Tree accumulator based cross-count algorithm given in Barth, et al., “Simple and Efficient Bilayer Cross Counting”. It is an improvement over algorithm by Malhotra et. al. in paper An E log E Line Crossing Algorithm for Levelled Graphs.
6. Improve the Horizontal Compaction Algorithm. The current implementation uses Brandes and Köpf, “Fast and Simple Horizontal Coordinate Assignment”. It has some corner cases. use the one defined in DagreJs issue update in v0.7.0.