[elm-discuss] 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.

Post by 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.
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.
- Fixed diagrams: https://github.com/vilterp/elm-diagrams
- Drawing tree structures: https://github.com/brenden/elm-tree-diagram
https://github.com/justinmimbs/elm-arc-diagram/tree/1.0.0
- Graph editor with dot export: https://github.com/jhrcek/elm-graph-editor
https://github.com/gampleman/elm-visualization
Cheers,
Michael

[Ambrose Laing]

There is also this one:

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

Post by 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.

Post by 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.
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.
- Fixed diagrams: https://github.com/vilterp/elm-diagrams
- Drawing tree structures: https://github.com/brenden/elm-tree-diagram
https://github.com/justinmimbs/elm-arc-diagram/tree/1.0.0
https://github.com/jhrcek/elm-graph-editor
https://github.com/gampleman/elm-visualization
Cheers,
Michael

[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.

Post by 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.

[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' via Elm Discuss]

Post by 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.

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.

Post by 'Rupert Smith' via Elm Discuss

Post by 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.

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
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]

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

Post by 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.

Post by 'Rupert Smith' via Elm Discuss

Post by 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.

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
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?

[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.

Post by 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.
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.
- Fixed diagrams: https://github.com/vilterp/elm-diagrams
- Drawing tree structures: https://github.com/brenden/elm-tree-diagram
https://github.com/justinmimbs/elm-arc-diagram/tree/1.0.0
- Graph editor with dot export: https://github.com/jhrcek/elm-graph-editor
https://github.com/gampleman/elm-visualization
Cheers,
Michael

[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 !