[PATCH] Add edgelist graph backend

  • Open
  • quality assurance status badge
Details
4 participants
  • Kyle Andrews
  • Liliana Marie Prikler
  • Ludovic Courtès
  • Simon Tournier
Owner
unassigned
Submitted by
Kyle Andrews
Severity
normal
Merged with
K
K
Kyle Andrews wrote on 15 Feb 2023 06:21
(name . Guix Patches)(address . guix-patches@gnu.org)
875yc3sdfo.fsf@posteo.net
Dear Guix,

I would like to be able to conveniently analyze Guix package
dependencies using general purpose network analysis software such as
igraph. To achieve this, I have added another backend to Guix and which
is exposed via guix graph which spits out a three column table that,
while not technically and edge list, is readily transformed into one
with minimal data munging.

Please see the attached patch file which I have created with `git diff'
from my working tree since I am not yet comfortable with more advanced
git workflows.
Toggle diff (39 lines)
diff --git a/guix/graph.scm b/guix/graph.scm
index 41219ab67d..e1760ed92a 100644
--- a/guix/graph.scm
+++ b/guix/graph.scm
@@ -255,6 +255,24 @@ (define %graphviz-backend
emit-prologue emit-epilogue
emit-node emit-edge))
+(define (emit-edgelist-prologue name port)
+ (display "" port))
+
+(define (emit-edgelist-epilogue port)
+ (display "" port))
+
+(define (emit-edgelist-node id label port)
+ (format port "package, ~a, ~a\n" label id))
+
+(define (emit-edgelist-edge id1 id2 port)
+ (format port "depends, ~a, ~a\n" id1 id2))
+
+(define %edgelist-backend
+ (graph-backend "edgelist"
+ "Generate graph in CSV edge list format"
+ emit-edgelist-prologue emit-edgelist-epilogue
+ emit-edgelist-node emit-edgelist-edge))
+
;;;
;;; d3js export.
@@ -338,7 +356,8 @@ (define %cypher-backend
(define %graph-backends
(list %graphviz-backend
%d3js-backend
- %cypher-backend))
+ %cypher-backend
+ %edgelist-backend))
(define (lookup-backend name)
"Return the graph backend called NAME. Raise an error if it is not found."
S
S
Simon Tournier wrote on 15 Feb 2023 17:32
86h6vmdh3k.fsf@gmail.com
Hi,

On Wed, 15 Feb 2023 at 05:21, Kyle Andrews <kyle@posteo.net> wrote:
Toggle quote (9 lines)
> Dear Guix,
>
> I would like to be able to conveniently analyze Guix package
> dependencies using general purpose network analysis software such as
> igraph. To achieve this, I have added another backend to Guix and which
> is exposed via guix graph which spits out a three column table that,
> while not technically and edge list, is readily transformed into one
> with minimal data munging.

You might be interested by [1] where I export all the packages as
JSON-like (Python dictionary) and then import with python-networkx.

Feel free to report your analyses, I am very interested by such. :-)



Toggle quote (3 lines)
> +(define (emit-edgelist-prologue name port)
> + (display "" port))

Here, I would add the description of the data as header of the CSV-like
file. For instance, something:

Toggle snippet (5 lines)
# type, name-or-edge1, item-or-edge2
# package, name, item
# depends, edge1, edge2

Well, is this format a standard format for representing graph?

From igraph documentation [1], it reads ’igraph_read_graph_edgelist’:

This format is simply a series of an even number of non-negative
integers separated by whitespace. The integers represent vertex
IDs. Placing each edge (i.e. pair of integers) on a separate
line is not required, but it is recommended for
readability. Edges of directed graphs are assumed to be in
"from, to" order.

so maybe it could be nice to use this plain list for the edgelist
backend. WDYT?



Cheers,
simon
K
K
Kyle Andrews wrote on 16 Feb 2023 04:28
(name . Simon Tournier)(address . zimon.toutoune@gmail.com)(address . 61527@debbugs.gnu.org)
878rgynpox.fsf@posteo.net
Simon Tournier <zimon.toutoune@gmail.com> writes:

Toggle quote (17 lines)
> Hi,
>
> On Wed, 15 Feb 2023 at 05:21, Kyle Andrews <kyle@posteo.net> wrote:
>> Dear Guix,
>>
>> I would like to be able to conveniently analyze Guix package
>> dependencies using general purpose network analysis software such as
>> igraph. To achieve this, I have added another backend to Guix and which
>> is exposed via guix graph which spits out a three column table that,
>> while not technically and edge list, is readily transformed into one
>> with minimal data munging.
>
> You might be interested by [1] where I export all the packages as
> JSON-like (Python dictionary) and then import with python-networkx.
>
> Feel free to report your analyses, I am very interested by such. :-)

That's my plan. I hope to provide Guix developers some tools to guide
their efforts. Of course, I would really like to make networks of many
more things in Guix including the Guile code itself and the Git history.

Toggle quote (2 lines)
That looks like a great reference! With regards to your query about
graphs in that email, I remember there being a Racket library which
provides the core graph data structures. Maybe those could be ported to
guile? However, I wonder if it would more practical for guile to
interface with igraph.

Toggle quote (12 lines)
>> +(define (emit-edgelist-prologue name port)
>> + (display "" port))
>
> Here, I would add the description of the data as header of the CSV-like
> file. For instance, something:
>
> --8<---------------cut here---------------start------------->8---
> # type, name-or-edge1, item-or-edge2
> # package, name, item
> # depends, edge1, edge2
> --8<---------------cut here---------------end--------------->8---

I toyed with calling columns 2 and 3 "parent/child", "source/sink",
"input/output", "origin/destination". The "input/output" option sounds
the best to me.

Toggle quote (2 lines)
> Well, is this format a standard format for representing graph?

No it's not. Since I am not particularly comfortable with guile, I was
hesitant to make extensive changes to the existing backend code. If I
could have produced just the "depends" lines with the integers
substituted with their meaningful names@versions, I would have done that
instead. If I could pass id1 id2 label1 label2 to all of the emit
procedures that would be pretty handy!

For example:

```
input, output
package1@1.2, package3@1.4
package1@1.2, package2@3.9
...
```

Technically, R programmers would probably first turn this into a matrix
or a data frame. That intermediate step would provide a convenient
opportuntity to extract out the versions strings so that networks could
more readily be compared across commits and branches. The versions could
be added back in later as node attributes. Just as with relational
tables, network analysis gets much more powerful when they have lots of
attributes, some of which may refer to hash table keys pointing to other
data structures. For example, libressl and openssl might share a
protocol attribute with a value of "SSL". With a rich set of attributes
data, researchers could start thinking about how to sample from the
distribution of possible alternative system configurations when doing
reproducibility studies. This might reveal "hot spots" of
irreproducibility which package authors could be looking out for. That's
one idea I just had while writing this email. I'm sure many people could
come up with many more neat ideas if the biggest barriers to getting the
data in the first place were removed.

Toggle quote (14 lines)
> From igraph documentation [1], it reads ’igraph_read_graph_edgelist’:
>
> This format is simply a series of an even number of non-negative
> integers separated by whitespace. The integers represent vertex
> IDs. Placing each edge (i.e. pair of integers) on a separate
> line is not required, but it is recommended for
> readability. Edges of directed graphs are assumed to be in
> "from, to" order.
>
> so maybe it could be nice to use this plain list for the edgelist
> backend. WDYT?
>
> 1: https://igraph.org/c/doc/igraph-Foreign.html#igraph_read_graph_edgelist

This is exactly why I did what I did in this patch. Just by filtering
rows with "depends" in the first column, you get the edge list the
igraph manual describes. To get the labels, you just need to filter rows
with "package" instead. These are straightfoward post processing steps
for many R and python users.

I don't like the idea of just returning integers though. It's no fun to
not be able to readily see what nodes refer to. That's why I prefer the
CSV view of things with descriptive labels.

Thanks for looking at my patch!

Cheers,
Kyle
L
L
Ludovic Courtès wrote on 27 Feb 2023 23:48
Re: bug#61527: [PATCH] Add edgelist graph backend
(name . Kyle Andrews)(address . kyle@posteo.net)
87bkleg1xi.fsf@gnu.org
Hello Kyle,

Kyle Andrews <kyle@posteo.net> skribis:

Toggle quote (7 lines)
> I would like to be able to conveniently analyze Guix package
> dependencies using general purpose network analysis software such as
> igraph. To achieve this, I have added another backend to Guix and which
> is exposed via guix graph which spits out a three column table that,
> while not technically and edge list, is readily transformed into one
> with minimal data munging.

Is “CSV edge list” some sort of a standard format, or is it more of an
idea you came up with?

The patch LGTM but we’ll need a couple more things:

1. Maybe emitting extra metadata as Simon suggested.

2. Adding documentation under “Invoking guix graph”. In particular,
it’d be nice to have an example showing how to query the generated
CSV with igraph.

3. Ideally a full patch with commit log as generated with ‘git
format-patch’. :-)

Could you send an updated patch?

Thank you!

Ludo’.
S
S
Simon Tournier wrote on 28 Feb 2023 10:21
Re: [bug#61527] [PATCH] Add edgelist graph backend
(address . 61527@debbugs.gnu.org)
87cz5ukuvk.fsf@gmail.com
Hi Kyle,

Thank you for your inputs on the topic. :-)


On lun., 27 févr. 2023 at 23:48, Ludovic Courtès <ludo@gnu.org> wrote:

Toggle quote (3 lines)
> Is “CSV edge list” some sort of a standard format, or is it more of an
> idea you came up with?

In addition to Ludo’s suggestions below, and commenting your answer [1],
instead of “edgelist” backend – which seems well documented by igraph so
it could be confusing for igraph folk, if any :-) – instead of
“edgelist” backend I would use “csv”. WDYT?

Quoting [1] for context:

Toggle quote (13 lines)
> > Here, I would add the description of the data as header of the CSV-like
> > file. For instance, something:
> >
> > --8<---------------cut here---------------start------------->8---
> > # type, name-or-edge1, item-or-edge2
> > # package, name, item
> > # depends, edge1, edge2
> > --8<---------------cut here---------------end--------------->8---
>
> I toyed with calling columns 2 and 3 "parent/child", "source/sink",
> "input/output", "origin/destination". The "input/output" option sounds
> the best to me.

This “input/output” does not sound to me. I would keep something like:

Toggle snippet (5 lines)
# type, name-or-from, vertex-or-to
# package, name, vertex
# depends, from, to

Thinking a bit about this format, I agree with you that this “format”
covers various needs feeding Python, R, etc. graph libraries. And it is
easy to filter via plain pipe “| grep depends“ or else.




Toggle quote (13 lines)
> The patch LGTM but we’ll need a couple more things:
>
> 1. Maybe emitting extra metadata as Simon suggested.
>
> 2. Adding documentation under “Invoking guix graph”. In particular,
> it’d be nice to have an example showing how to query the generated
> CSV with igraph.
>
> 3. Ideally a full patch with commit log as generated with ‘git
> format-patch’. :-)
>
> Could you send an updated patch?

Let me know if you need help. :-)

Cheers,
simon
K
K
Kyle Andrews wrote on 1 Mar 2023 04:49
(name . Simon Tournier)(address . zimon.toutoune@gmail.com)
875yblgl0m.fsf@posteo.net
Simon Tournier <zimon.toutoune@gmail.com> writes:

Toggle quote (15 lines)
> Hi Kyle,
>
> Thank you for your inputs on the topic. :-)
>
>
> On lun., 27 févr. 2023 at 23:48, Ludovic Courtès <ludo@gnu.org> wrote:
>
>> Is “CSV edge list” some sort of a standard format, or is it more of an
>> idea you came up with?
>
> In addition to Ludo’s suggestions below, and commenting your answer [1],
> instead of “edgelist” backend – which seems well documented by igraph so
> it could be confusing for igraph folk, if any :-) – instead of
> “edgelist” backend I would use “csv”. WDYT?

I agree 'csv' would be less confusing since in reality there are two
(normalized) tables embedded in one in the output.

Toggle quote (23 lines)
> Quoting [1] for context:
>
>> > Here, I would add the description of the data as header of the CSV-like
>> > file. For instance, something:
>> >
>> > --8<---------------cut here---------------start------------->8---
>> > # type, name-or-edge1, item-or-edge2
>> > # package, name, item
>> > # depends, edge1, edge2
>> > --8<---------------cut here---------------end--------------->8---
>>
>> I toyed with calling columns 2 and 3 "parent/child", "source/sink",
>> "input/output", "origin/destination". The "input/output" option sounds
>> the best to me.
>
> This “input/output” does not sound to me. I would keep something like:
>
> --8<---------------cut here---------------start------------->8---
> # type, name-or-from, vertex-or-to
> # package, name, vertex
> # depends, from, to
> --8<---------------cut here---------------end--------------->8---

I like the name "table" for the first column following my rationale
above. For the second and third columns my sense of style and experience
working with data in R, I tend to prefer shorter vaguer names which are
easier to type. I hope it should be clear from context what is a label
for a vertex and what is an id for vertex. It would make more sense to
me to explain the meaning of each column in a "data dictionary" included
in the documentation, rather than sacrifice interactive convenience.

Toggle quote (4 lines)
> Thinking a bit about this format, I agree with you that this “format”
> covers various needs feeding Python, R, etc. graph libraries. And it is
> easy to filter via plain pipe “| grep depends“ or else.

Exactly.

Toggle quote (8 lines)
>
> 1: <https://issues.guix.gnu.org/msgid/878rgynpox.fsf@posteo.net>
>
>
>> The patch LGTM but we’ll need a couple more things:
>>
>> 1. Maybe emitting extra metadata as Simon suggested.

Mostly done depending on whether you will be satisfied with my "data
dictionary" idea.

Toggle quote (4 lines)
>> 2. Adding documentation under “Invoking guix graph”. In particular,
>> it’d be nice to have an example showing how to query the generated
>> CSV with igraph.

I have not added an example yet but I did mention the backend in the
documentation with a short description.

Toggle quote (5 lines)
>> 3. Ideally a full patch with commit log as generated with ‘git
>> format-patch’. :-)

>> Could you send an updated patch?

Sorry, I tried to send an updated patch without reading (2) closely
enough. So, it's missing the example. I also want to add the data
dictionary I mentioned above.

I used git send-email for this task.

Toggle snippet (3 lines)
git send-email *.patch --to=guix-patches@gnu.org

Is that the preferred way to do it? I'm not quite sure how debbugs
associates the issue numbers.

Toggle quote (3 lines)
>
> Let me know if you need help. :-)

Thanks, for the offer! I really appreciate your patience.

Toggle quote (2 lines)
> Cheers,
> simon
L
L
Liliana Marie Prikler wrote on 1 Mar 2023 10:32
(address . control@debbugs.gnu.org)(name . Kyle Andrews)(address . kyle@posteo.net)
a2064a92dd87c1c6509e3096e8df7d23493e3f16.camel@ist.tugraz.at
merge 61527 61888
thanks

@Kyle: Next time, use the reroll-count option of git send-email and
resend your patch to the bug that's already open.

Cheers
S
S
Simon Tournier wrote on 1 Mar 2023 11:34
(name . Kyle Andrews)(address . kyle@posteo.net)
87pm9shiap.fsf@gmail.com
Hi Kyle,

On mer., 01 mars 2023 at 03:49, Kyle Andrews <kyle@posteo.net> wrote:

Toggle quote (9 lines)
> I used git send-email for this task.
>
> --8<---------------cut here---------------start------------->8---
> git send-email *.patch --to=guix-patches@gnu.org
> --8<---------------cut here---------------end--------------->8---
>
> Is that the preferred way to do it? I'm not quite sure how debbugs
> associates the issue numbers.

No, it is not. :-)

Doing this, you trigger a new Debbugs number, and worse, one per patch
behind *.patch.

Please give a look to the manual,


and let us know if it appears to you unclear, or any feedback. :-)

In short:

Once Debbugs created a number for tracking the patch, it is currently
the number 61527, you must reply to 61527@debbugs.gnu.org.

After a first version, you can use the option --reroll-count of
git-format-patch for incrementing the count. Here, it would be ’-v2’
(short for --reroll-count=2). This makes the Subject: [PATCH v2 x/N].

Hope that helps,
simon
?