Drawing Directed Graphs (?) in Elm

[Michael Jones]

Hi,

I am interested in exploring the automatic layout of flow-chart-like-structures in Elm. I'm not sure of the exact terminology. I think directed graphs covers it.

Perhaps a solution like the one presented in this paper: http://www.graphviz.org/Documentation/TSE93.pdf

I would be happy to try to tackle it myself but I'm also curious if anyone is already looking into it? I have done some searching and have found various graph libraries but not tackle the idea of doing an automatic layout.

I am not so interested in force-layouts as they product more organic results which do not match my use case.

Related results:

- Fixed diagrams: https://github.com/vilterp/elm-diagrams

- Drawing tree structures: https://github.com/brenden/elm-tree-diagram

- Drawing arc diagrams: https://github.com/justinmimbs/elm-arc-diagram/tree/1.0.0

- Graph editor with dot export: https://github.com/jhrcek/elm-graph-editor

- Visualisation library which includes Force Layouts: https://github.com/gampleman/elm-visualization

Cheers,

Michael

[Ambrose Laing]

This may be helpful.

https://github.com/mdaines/viz.js/

It should give you exactly the solution you cited.  But I believe you need to figure out hooking it up to elm using ports.
I have no experience with this particular project myself, but I do use graphviz and had heard of this one.

[Ambrose Laing]

There is also this one:

https://github.com/mstefaniuk/graph-viz-d3-js

[Jakub Hampl]

In principle this sort of thing would be in scope for elm-visualisation to implement. However, as that particular approach entails a lot of work, I would like to hear about the details of the use case and whether the force layout approach could not be adapted to work.

[Steve Schafer]

Force-directed layouts become difficult to interpret if there are more than a hundred nodes or so, or if there are a lot of multi-way relationships. A large number of generally hierarchical nodes (such as In many directed acyclic graphs) is often easier to interpret using a hierarchical layout (as described in the OP's linked paper). A graph with numerous multi-way relationships can be easier to interpret with a chord diagram or similar.

A force-directed layout that allows you to drag and "pin" nodes could be made to work, but then you're just being forced to do manually what the computer ought to be able to do for you.

Here's the central portion of a complex DAG I happen to be working with right now, rendered as a force-directed graph in D3: http://imgur.com/a/lBP6i

The nodes are actually almost strictly hierarchical, but you'd never know that looking at this image.

[Michael Jones]

Thank you for the suggestions. My concerns are inline with Steve Schafer's. I would like a dominantly vertical alignment with a clear structured hierarchy spreading evenly left & right rather than an organic circular spread. I'm not well versed in any of this but my impression is the that force-layout approach is less controlled. 

I have had a chance to read through that paper a bit and it is more trouble than I would like but I haven't ruled out attempting it at some point. I should also explore the links that Ambrose kindly provided. I'm initially put off by the idea of using a library compiled from C++ to Javascript, mostly on some fear of bloat, but perhaps that is my ignorance speaking.

Kind regards,

Michael 

[Michael Jones]

As a further update, a colleague found this implementation of the algorithm in Javascript: https://github.com/cpettitt/dagre

It is no longer maintained but there is an active fork here: https://github.com/ciena-blueplanet/dagre

So I'm using that via ports to get the layout & then drawing the graph myself in SVG. I haven't finished yet but it is looking very promising.

Kind regards,

Michael

[Rupert Smith]

On Monday, August 7, 2017 at 2:34:37 PM UTC+1, Michael Jones wrote:

Thank you for the suggestions. My concerns are inline with Steve Schafer's. I would like a dominantly vertical alignment with a clear structured hierarchy spreading evenly left & right rather than an organic circular spread. I'm not well versed in any of this but my impression is the that force-layout approach is less controlled.

Hi Michael,

It is something that I am looking into too. The graphs I am laying out are more like entity-relationship diagrams or UML class diagrams descirbing a data model. Force directed also does not quite cut it for my use case, so I was thinking of trying something along the lines of fitting the graph nodes into a grid and using search to try and search for optimal layouts evaluated against criteria such as avoiding overlaps, crossing edges, having connected nodes be neighbours and so on.

Towards this end I wrote an AI search library to use to drive the search for the best solutions:

http://package.elm-lang.org/packages/the-sett/ai-search/latest

Unfortunately that is about as far as I have gotten so far, too many other distractions. But you may also be interested in taking a search based approach?

[Erkal Selman]

Hi, 

so happy to see so many interested people here in graph drawing with elm.

Here is the project that I am working on https://erkal.github.io/kite/

It is written entirely in elm, except I use D3.js for force layout.

But the project is kind of frozen because I don't have time for it.

But you may use the code. 

You may copy the code for the ports to D3-force-layout and use it in your apps.

I am sure that you will find some other useful stuff too.

[Erkal Selman]

Here is a renderer written in elm for dagre https://github.com/erkal/elm-dagre

[Daniel García]

Hi Michael,

I am also interested

Did you make some progress ? Also do you have a public repository I can take a loot at ?

Best regards.

[Michael Jones]

Hi Daniel,

I settled on using the https://github.com/ciena-blueplanet/dagre library I highlighted above.

I already have the graph details in a Javascript object so I feed them into dagre and then extract the resulting layout. I send that back into elm via a port which decodes to these types:

import Json.Decode exposing (bool, field, float, int, list, maybe, string)

import Json.Decode.Pipeline exposing (decode, hardcoded, optional, required, requiredAt)

type NodeType

    = QuestionNode Int

    | EndNode

    | NewSectionNode String

type alias NodeLayout =

    { type_ : NodeType

    , x : Float

    , y : Float

    }

type alias EdgeLayout =

    { x : Float

    , y : Float

    , label : String

    , points : List { x : Float, y : Float }

    }

type alias GraphLayout =

    { nodes : List NodeLayout

    , edges : List EdgeLayout

    , width : Float

    , height : Float

    , offsetX : Float

    }

graphLayoutDecoder : Json.Decode.Decoder GraphLayout

graphLayoutDecoder =

    let

        nodeTypeDecoder =

            let

                decodeType type_ =

                    case type_ of

                        "node" ->

                            Json.Decode.map QuestionNode (field "id" int)

                        "new-section" ->

                            Json.Decode.map NewSectionNode (field "name" string)

                        "end-of-process" ->

                            Json.Decode.succeed EndNode

                        _ ->

                            Json.Decode.fail "Unknown Node Type"

            in

            field "type" string |> Json.Decode.andThen decodeType

        nodeLayoutDecoder =

            decode NodeLayout

                |> required "type" nodeTypeDecoder

                |> required "x" float

                |> required "y" float

        pointDecoder =

            decode (\x y -> { x = x, y = y })

                |> required "x" float

                |> required "y" float

        edgeLayoutDecoder =

            decode EdgeLayout

                |> required "x" float

                |> required "y" float

                |> required "label" string

                |> required "points" (list pointDecoder)

    in

    decode GraphLayout

        |> required "nodes" (list nodeLayoutDecoder)

        |> required "edges" (list edgeLayoutDecoder)

        |> required "width" float

        |> required "height" float

        |> required "offsetX" float

But I'm afraid the project is commercial and not open sourced so I can't share much more. Happy to answer questions if I can.

Kind regards,

Michael

[Daniel García]

Thanks Michael !