Date: Thu, 25 Jul 2019 20:07:29 -0400

By sparse matrix - I mean compressed row or col format:

https://en.wikipedia.org/wiki/Sparse_matrix

This is standard in the linear algebra community.

Sent from my iPhone

> On Jul 25, 2019, at 5:43 PM, Sebastian Messmer <messmer_at_[hidden]> wrote:

>

> If by “Sparse matrix” you mean a list or array of (source node, target node) pairs, then this is not consistent with the terminology in the Carnegie Mellon lecture I found. They would call that an “edge list” and define “adjacency array” in the way I did a few emails ago. In any case, terminology seems to be inconsistently used in literature and we need to define terms in the paper before we use them.

>

> Also, we should consider supporting the thing the Carnegie Mellon lecture calls “adjacency array” (i.e. not the edge list), because that’s a very performant and cache-efficient layout for graphs that are read heavily and (almost) never written to.

>

> Sebastian

>

>

> From: Matthew Galati <matthew.galati_at_[hidden]>

> Date: Saturday, July 20, 2019 at 3:33 AM

> To: "sg19_at_[hidden]" <sg19_at_[hidden]>

> Cc: Sebastian Messmer <messmer_at_[hidden]>

> Subject: Re: [SG19] Adjacency Arrays in Graph Proposal (p1709r0)

>

> ‘Adjacency array’ is really just an adjacency sparse matrix.

> https://en.wikipedia.org/wiki/Sparse_matrix

>

> We might want to consider using some standardized matrix storage object.

>

> Sent from my iPhone

>

> On Jul 20, 2019, at 2:40 AM, Sebastian Messmer via SG19 <sg19_at_[hidden]> wrote:

>

> Upon further research, I found that the terms are used inconsistently in different sources.

>

> The way I’ve learned and am using the terms is consistent with a Carnegie Mellon class I found: http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture07.pdf

> They have four graph layouts: adjacency matrix, adjacency list, adjacency array and edge list (edge list is the one where there’s just one array with all edges and each edge stores both corresponding vertex indices).

>

> But I’ve also found sources that describe what I know as “adjacency array” but call it “adjacency list”: https://www.sciencedirect.com/topics/computer-science/adjacency-list

> Though I don’t know what they call what I and the class linked above know as “adjacency list” then, maybe “linked adjacency list”?

>

> Given this inconsistent situation, we should probably decide for a terminology and then define the terms in the paper before we use them.

>

> Regards

> Sebastian

> From: SG19 <sg19-bounces_at_[hidden]> on behalf of Sebastian Messmer via SG19 <sg19_at_[hidden]>

> Reply-To: "sg19_at_[hidden]" <sg19_at_[hidden]>

> Date: Thursday, July 18, 2019 at 7:28 PM

> To: "sg19_at_[hidden]" <sg19_at_[hidden]>

> Cc: Sebastian Messmer <messmer_at_[hidden]>

> Subject: [SG19] Adjacency Arrays in Graph Proposal (p1709r0)

>

> Hi,

>

> I looked through the graph proposal paper and I think there might be some misunderstandings about what I meant when I talked about adjacency arrays in our phone call.

>

> I found a picture online that might make things a bit more clear: https://www.researchgate.net/figure/The-adjacency-list-data-structure-used-in-our-implementation-shown-for-a-sample-graph_fig1_268988477

> (they call it adjacency list in that link, but it’s actually an adjacency array).

>

> An adjacency array stores all edges in one array, but sorted by vertex. There is an additional vertex array that stores pointers to its first edge in the edge array.

> Say V is that vertex array and E is the edge array, then E[V[i] … V[i+1]-1] is the range storing all edges for vertex I, usually they store the vertex index of the vertex on the other side of the edge.

>

> A directed graph that only needs to be forward-traversable does not store backwards edges, for each vertex the edge array only holds the out-edges.

> A undirected graph stores each edge twice, once for each vertex.

> A directed graph that need to be forward- and backward-traversable can be implemented by storing two indices in/out per vertex. E[V[i].in ... V[i].out-1] stores the in-edges and E[V[i].out ... V[i+1].in-1] stores the out-edges. This also means that each edge is stored twice.

>

> Adjacency arrays are very fast and cache-efficient when traversed but slow when modified. They are often used for map data and route planning because map data doesn’t change that often.

>

> Following this, there’s a few errors in the paper, for example:

> Inserting a new edge to a pre-existing node is O(number of edges), not O(1), because it needs to add a new entry to the middle of the edge array

> The paper claims “For instance, edges in an adjacency matrix should only be as big as the user-defined edge value, and for an adjacency array should be the size of user-defined edge value and in and out vertex references (vertex_id or pointer).”. Actually, an edge only stores only one vertex reference, not an in- and out-reference.

>

> Regards

> Sebastian Messmer

>

> --

> SG19 mailing list

> SG19_at_[hidden]

> http://lists.isocpp.org/mailman/listinfo.cgi/sg19

https://en.wikipedia.org/wiki/Sparse_matrix

This is standard in the linear algebra community.

Sent from my iPhone

> On Jul 25, 2019, at 5:43 PM, Sebastian Messmer <messmer_at_[hidden]> wrote:

>

> If by “Sparse matrix” you mean a list or array of (source node, target node) pairs, then this is not consistent with the terminology in the Carnegie Mellon lecture I found. They would call that an “edge list” and define “adjacency array” in the way I did a few emails ago. In any case, terminology seems to be inconsistently used in literature and we need to define terms in the paper before we use them.

>

> Also, we should consider supporting the thing the Carnegie Mellon lecture calls “adjacency array” (i.e. not the edge list), because that’s a very performant and cache-efficient layout for graphs that are read heavily and (almost) never written to.

>

> Sebastian

>

>

> From: Matthew Galati <matthew.galati_at_[hidden]>

> Date: Saturday, July 20, 2019 at 3:33 AM

> To: "sg19_at_[hidden]" <sg19_at_[hidden]>

> Cc: Sebastian Messmer <messmer_at_[hidden]>

> Subject: Re: [SG19] Adjacency Arrays in Graph Proposal (p1709r0)

>

> ‘Adjacency array’ is really just an adjacency sparse matrix.

> https://en.wikipedia.org/wiki/Sparse_matrix

>

> We might want to consider using some standardized matrix storage object.

>

> Sent from my iPhone

>

> On Jul 20, 2019, at 2:40 AM, Sebastian Messmer via SG19 <sg19_at_[hidden]> wrote:

>

> Upon further research, I found that the terms are used inconsistently in different sources.

>

> The way I’ve learned and am using the terms is consistent with a Carnegie Mellon class I found: http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture07.pdf

> They have four graph layouts: adjacency matrix, adjacency list, adjacency array and edge list (edge list is the one where there’s just one array with all edges and each edge stores both corresponding vertex indices).

>

> But I’ve also found sources that describe what I know as “adjacency array” but call it “adjacency list”: https://www.sciencedirect.com/topics/computer-science/adjacency-list

> Though I don’t know what they call what I and the class linked above know as “adjacency list” then, maybe “linked adjacency list”?

>

> Given this inconsistent situation, we should probably decide for a terminology and then define the terms in the paper before we use them.

>

> Regards

> Sebastian

> From: SG19 <sg19-bounces_at_[hidden]> on behalf of Sebastian Messmer via SG19 <sg19_at_[hidden]>

> Reply-To: "sg19_at_[hidden]" <sg19_at_[hidden]>

> Date: Thursday, July 18, 2019 at 7:28 PM

> To: "sg19_at_[hidden]" <sg19_at_[hidden]>

> Cc: Sebastian Messmer <messmer_at_[hidden]>

> Subject: [SG19] Adjacency Arrays in Graph Proposal (p1709r0)

>

> Hi,

>

> I looked through the graph proposal paper and I think there might be some misunderstandings about what I meant when I talked about adjacency arrays in our phone call.

>

> I found a picture online that might make things a bit more clear: https://www.researchgate.net/figure/The-adjacency-list-data-structure-used-in-our-implementation-shown-for-a-sample-graph_fig1_268988477

> (they call it adjacency list in that link, but it’s actually an adjacency array).

>

> An adjacency array stores all edges in one array, but sorted by vertex. There is an additional vertex array that stores pointers to its first edge in the edge array.

> Say V is that vertex array and E is the edge array, then E[V[i] … V[i+1]-1] is the range storing all edges for vertex I, usually they store the vertex index of the vertex on the other side of the edge.

>

> A directed graph that only needs to be forward-traversable does not store backwards edges, for each vertex the edge array only holds the out-edges.

> A undirected graph stores each edge twice, once for each vertex.

> A directed graph that need to be forward- and backward-traversable can be implemented by storing two indices in/out per vertex. E[V[i].in ... V[i].out-1] stores the in-edges and E[V[i].out ... V[i+1].in-1] stores the out-edges. This also means that each edge is stored twice.

>

> Adjacency arrays are very fast and cache-efficient when traversed but slow when modified. They are often used for map data and route planning because map data doesn’t change that often.

>

> Following this, there’s a few errors in the paper, for example:

> Inserting a new edge to a pre-existing node is O(number of edges), not O(1), because it needs to add a new entry to the middle of the edge array

> The paper claims “For instance, edges in an adjacency matrix should only be as big as the user-defined edge value, and for an adjacency array should be the size of user-defined edge value and in and out vertex references (vertex_id or pointer).”. Actually, an edge only stores only one vertex reference, not an in- and out-reference.

>

> Regards

> Sebastian Messmer

>

> --

> SG19 mailing list

> SG19_at_[hidden]

> http://lists.isocpp.org/mailman/listinfo.cgi/sg19

Received on 2019-07-25 19:09:28