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

  • Done
  • quality assurance status badge
Details
3 participants
  • Björn Höfling
  • Hartmut Goebel
  • Ludovic Courtès
Owner
unassigned
Submitted by
Hartmut Goebel
Severity
normal
H
H
Hartmut Goebel wrote on 5 Mar 2018 12:41
(address . guix-patches@gnu.org)
20180305114136.7207-1-h.goebel@crazy-compilers.com
* 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(-)

Toggle diff (94 lines)
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\"]);~%"
;;;
+;;; 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))
+
+
+
+;;;
;;; 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
L
L
Ludovic Courtès wrote on 5 Mar 2018 18:17
Re: [bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.
(name . Hartmut Goebel)(address . h.goebel@crazy-compilers.com)(address . 30711@debbugs.gnu.org)
87h8pu8msv.fsf@gnu.org
Hi Hartmut,

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

Toggle quote (8 lines)
> * 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?

Toggle quote (5 lines)
> -(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.

Toggle quote (3 lines)
> +(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’.
H
H
Hartmut Goebel wrote on 5 Mar 2018 22:12
(name . Ludovic Courtès)(address . ludo@gnu.org)(address . 30711@debbugs.gnu.org)
f4288cc3-c383-0a59-a73e-13a8a870893d@crazy-compilers.com
Am 05.03.2018 um 18:17 schrieb Ludovic Courtès:
Toggle quote (2 lines)
> Can you tell us more about the Trivial Graph Format?

This is a *very* simple format, see
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.)

Toggle quote (7 lines)
>> -(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.
Toggle quote (6 lines)
>> +(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 |
L
L
Ludovic Courtès wrote on 6 Mar 2018 11:32
(name . Hartmut Goebel)(address . h.goebel@crazy-compilers.com)(address . 30711@debbugs.gnu.org)
87po4hxznk.fsf@gnu.org
Hi,

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

Toggle quote (12 lines)
> 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.

Toggle quote (5 lines)
> 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’.
H
H
Hartmut Goebel wrote on 6 Mar 2018 21:20
(address . 30711-close@debbugs.gnu.org)(name . Ludovic Courtès)(address . ludo@gnu.org)
8a311dbb-676e-17ee-79df-d0ab52c6f752@crazy-compilers.com
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 |
B
B
Björn Höfling wrote on 6 Mar 2018 22:05
Re: bug#30711: [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.
(name . Hartmut Goebel)(address . h.goebel@crazy-compilers.com)(address . 30711-close@debbugs.gnu.org)
20180306220521.555dd2a6@alma-ubu
On Tue, 6 Mar 2018 21:20:48 +0100
Hartmut Goebel <h.goebel@crazy-compilers.com> wrote:

Toggle quote (9 lines)
> 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:


Björn
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iEYEARECAAYFAlqfApIACgkQvyhstlk+X/3w7ACgk+02Hi2Xdr6fHoxpRZXxlliT
QCoAn3+iU1yhXbtEnN+E2LK2Zuc1zxBP
=8PwQ
-----END PGP SIGNATURE-----


H
H
Hartmut Goebel wrote on 6 Mar 2018 22:23
(name . Björn Höfling)(address . bjoern.hoefling@bjoernhoefling.de)(address . 30711-close@debbugs.gnu.org)
eb2f4f60-65e2-ada3-199b-46ba9e9f27c2@crazy-compilers.com
Am 06.03.2018 um 22:05 schrieb Björn Höfling:
Toggle quote (2 lines)
> 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?


--
Regards
Hartmut Goebel

| Hartmut Goebel | h.goebel@crazy-compilers.com |
| www.crazy-compilers.com | compilers which you thought are impossible |
L
L
Ludovic Courtès wrote on 12 Mar 2018 15:30
Re: [bug#30711] [PATCH 1/1] guix: graph: Add Trival Graph Format (TGF) backend.
(name . Hartmut Goebel)(address . h.goebel@crazy-compilers.com)
874lllpdr4.fsf@gnu.org
Hartmut Goebel <h.goebel@crazy-compilers.com> skribis:

Toggle quote (3 lines)
> 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:


Ludo’.
?