[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Hartmut Goebel]

* guix/graph.scm ((emit-edge, emit-d3js-edge, emit-cypher-edge): New arguments
  label1 , label2.
  (emit-tg-progloug, mit-tgf-epilouge, emit-tgf-node, emit-tgf-edge): New
  variables.
  (%trivial-graph-backend): New variable.
  (%graph-backends): Add %trivial-graph-backend.
  (export-graph): Pass labels to emit-edge.
---
 guix/graph.scm | 40 ++++++++++++++++++++++++++++++++++------
 1 file changed, 34 insertions(+), 6 deletions(-)

diff --git a/guix/graph.scm b/guix/graph.scm
index d7fd5f3e4..650d577f6 100644
--- a/guix/graph.scm
+++ b/guix/graph.scm
@@ -46,6 +46,7 @@
             %graph-backends
             %d3js-backend
             %graphviz-backend
+            %trival-graph-backend
             graph-backend?
             graph-backend
             graph-backend-name
@@ -173,7 +174,7 @@ typically returned by 'node-edges' or 'node-back-edges'."
 (define (emit-node id label port)
   (format port "  \"~a\" [label = \"~a\", shape = box, fontname = Helvetica];~%"
           id label))
-(define (emit-edge id1 id2 port)
+(define (emit-edge id1 label1 id2 label2 port)
   (format port "  \"~a\" -> \"~a\" [color = ~a];~%"
           id1 id2 (pop-color id1)))
 
@@ -219,7 +220,7 @@ nodes[\"~a\"] = {\"id\": \"~a\", \"label\": \"~a\", \"index\": nodeArray.length}
 nodeArray.push(nodes[\"~a\"]);~%"
           id id label id))
 
-(define (emit-d3js-edge id1 id2 port)
+(define (emit-d3js-edge id1 label1 id2 label2 port)
   (format port "links.push({\"source\": \"~a\", \"target\": \"~a\"});~%"
           id1 id2))
 
@@ -245,7 +246,7 @@ nodeArray.push(nodes[\"~a\"]);~%"
   (format port "MERGE (p:Package { id: ~s }) SET p.name = ~s;~%"
           id label ))
 
-(define (emit-cypher-edge id1 id2 port)
+(define (emit-cypher-edge id1 label1 id2 label2 port)
   (format port "MERGE (a:Package { id: ~s });~%" id1)
   (format port "MERGE (b:Package { id: ~s });~%" id2)
   (format port "MATCH (a:Package { id: ~s }), (b:Package { id: ~s }) CREATE UNIQUE (a)-[:NEEDS]->(b);~%"
@@ -260,13 +261,32 @@ nodeArray.push(nodes[\"~a\"]);~%"
 
 \f
 ;;;
+;;; Trivial graph export.
+;;;
+
+(define (emit-tgf-prologue name port) #t)
+(define (emit-tgf-epilogue port) #t)
+(define (emit-tgf-node id label port) #t)
+(define (emit-tgf-edge id1 label1 id2 label2 port)
+  (format port "~a ~a~%" label1 label2))
+
+(define %trival-graph-backend
+  (graph-backend "tgf"
+                 "Generate graph in Trivial Graph Format."
+                 emit-tgf-prologue emit-tgf-epilogue
+                 emit-tgf-node emit-tgf-edge))
+
+
+\f
+;;;
 ;;; Shared.
 ;;;
 
 (define %graph-backends
   (list %graphviz-backend
         %d3js-backend
-        %cypher-backend))
+        %cypher-backend
+        %trival-graph-backend))
 
 (define* (export-graph sinks port
                        #:key
@@ -299,8 +319,16 @@ true, draw reverse arrows."
                      (emit-node id (node-label head) port)
                      (for-each (lambda (dependency dependency-id)
                                  (if reverse-edges?
-                                     (emit-edge dependency-id id port)
-                                     (emit-edge id dependency-id port)))
+                                     (emit-edge dependency-id
+                                                (node-label dependency)
+                                                id
+                                                (node-label head)
+                                                port)
+                                     (emit-edge id
+                                                (node-label head)
+                                                dependency-id
+                                                (node-label dependency)
+                                                port)))
                                dependencies ids)
                      (loop (append dependencies tail)
                            (set-insert id visited)))))))))))))
-- 
2.13.6

[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Ludovic Courtès]

Hi Hartmut,

Hartmut Goebel <h.goebel@crazy-compilers.com> skribis:

> * guix/graph.scm ((emit-edge, emit-d3js-edge, emit-cypher-edge): New arguments
>   label1 , label2.
>   (emit-tg-progloug, mit-tgf-epilouge, emit-tgf-node, emit-tgf-edge): New
>   variables.
>   (%trivial-graph-backend): New variable.
>   (%graph-backends): Add %trivial-graph-backend.
>   (export-graph): Pass labels to emit-edge.

Can you tell us more about the Trivial Graph Format?

> -(define (emit-edge id1 id2 port)
> +(define (emit-edge id1 label1 id2 label2 port)
>    (format port "  \"~a\" -> \"~a\" [color = ~a];~%"
>            id1 id2 (pop-color id1)))

This is orthogonal to adding a new format, so it should probably be a
separate patch.

> +(define (emit-tgf-edge id1 label1 id2 label2 port)
> +  (format port "~a ~a~%" label1 label2))

This is probably incorrect because labels do not necessarily uniquely
identify nodes.  This is why the API distinguishes node identifiers and
labels.

Thanks,
Ludo’.

[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Hartmut Goebel]

Am 05.03.2018 um 18:17 schrieb Ludovic Courtès:
> Can you tell us more about the Trivial Graph Format? 

This is a *very* simple format, see
https://en.wikipedia.org/wiki/Trivial_Graph_Format. You can only define
nodes, edges and labels. Edges are always directed. I don't know whether
it is wide-spread. By chance I used it to import data into yEd
(non-free, by chance mentioned in the Wikipedia-article), which allows
to select quite some different graph layouts.

So the first decision should be whether TFG should be included.

(Alternativly, for importing into yEd, a simple GraphML should work,
too.So I could implement that, which might be of more widespread use.)

>> -(define (emit-edge id1 id2 port)
>> +(define (emit-edge id1 label1 id2 label2 port)
>>    (format port "  \"~a\" -> \"~a\" [color = ~a];~%"
>>            id1 id2 (pop-color id1)))
> This is orthogonal to adding a new format, so it should probably be a
> separate patch.

Will split up, when TGF backend is accepted.
>> +(define (emit-tgf-edge id1 label1 id2 label2 port)
>> +  (format port "~a ~a~%" label1 label2))
> This is probably incorrect because labels do not necessarily uniquely
> identify nodes.  This is why the API distinguishes node identifiers and
> labels.

Following you answer bug #30710 (graph gives duplicate edges) this is
true and this implementation is wrong.

TGF requires all nodes to be defined prior to any of their edges,
otherwise the edge's Ids will be taken as labels. Thus the export-graph
needs to be changed to first emit all nodes and then the edges. Due do
my little guile-knowledge I did not manage to change the code accordingly.

-- 
Regards
Hartmut Goebel

| Hartmut Goebel          | h.goebel@crazy-compilers.com               |
| www.crazy-compilers.com | compilers which you thought are impossible |

[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Ludovic Courtès]

Hi,

Hartmut Goebel <h.goebel@crazy-compilers.com> skribis:

> Am 05.03.2018 um 18:17 schrieb Ludovic Courtès:
>> Can you tell us more about the Trivial Graph Format? 
>
> This is a *very* simple format, see
> https://en.wikipedia.org/wiki/Trivial_Graph_Format. You can only define
> nodes, edges and labels. Edges are always directed. I don't know whether
> it is wide-spread. By chance I used it to import data into yEd
> (non-free, by chance mentioned in the Wikipedia-article), which allows
> to select quite some different graph layouts.
>
> So the first decision should be whether TFG should be included.

I must say I’m skeptical, in large part because the dot format is
already simple enough and implement by a number of graph-processing
tools, not just Graphviz.

> TGF requires all nodes to be defined prior to any of their edges,
> otherwise the edge's Ids will be taken as labels. Thus the export-graph
> needs to be changed to first emit all nodes and then the edges. Due do
> my little guile-knowledge I did not manage to change the code accordingly.

The issue is that the API currently assumes that backends are stateless:
they can just emit a node or an edge anytime we ask them, without prior
knowledge.  That doesn’t work for TGF.

TGF alone may not warrant a change in the backend API, if you ask me
;-), but there may be other things that would require the backend API to
be less stupid.  An ASCII rendering of the graph would need to be
stateful, for instance.

Needs more thought…

Ludo’.

bug#30711: [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Hartmut Goebel]

Hi,

I'm retracting this patch. The implementation is wrong, fixing it
requires too many changes and the use is arguable. So we should not
spend much tome on it.

Thanks for reviewing and feedback :-)

-- 
Regards
Hartmut Goebel

| Hartmut Goebel          | h.goebel@crazy-compilers.com               |
| www.crazy-compilers.com | compilers which you thought are impossible |

[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Björn Höfling]

[-- Attachment #1: Type: text/plain, Size: 548 bytes --]

On Tue, 6 Mar 2018 21:20:48 +0100
Hartmut Goebel <h.goebel@crazy-compilers.com> wrote:

> Hi,
> 
> I'm retracting this patch. The implementation is wrong, fixing it
> requires too many changes and the use is arguable. So we should not
> spend much tome on it.
> 
> Thanks for reviewing and feedback :-)
> 

Do you think with gvpr one could write a dot2tgf?

Here is the manual and an example:

https://manpages.debian.org/testing/graphviz/gvpr.1.en.html
https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424/

Björn

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Hartmut Goebel]

Am 06.03.2018 um 22:05 schrieb Björn Höfling:
> Do you think with gvpr one could write a dot2tgf?

May, but not owrth the effort IMHO. Esp. since I just discovered
graphviz includes "gv2gml" [1] and gml is an import- format for yed.
Thus this solves my problem :-)

Many thanks for pointing to [1].

Side-note: I'd be interested in a tool for interactively rearrange dot
graphs, zoom in/out, showing neighbors, etc. much like yed does. Any idea?

[1] https://manpages.debian.org/testing/graphviz/index.html

-- 
Regards
Hartmut Goebel

| Hartmut Goebel          | h.goebel@crazy-compilers.com               |
| www.crazy-compilers.com | compilers which you thought are impossible |

[bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.

[Ludovic Courtès]

Hartmut Goebel <h.goebel@crazy-compilers.com> skribis:

> Side-note: I'd be interested in a tool for interactively rearrange dot
> graphs, zoom in/out, showing neighbors, etc. much like yed does. Any idea?

Tulip, which is developed in the lab next to where I work, should
support that:

  http://tulip.labri.fr/TulipDrupal/

Ludo’.