Date: Thu, 25 Jul 2019 21:43:18 +0000

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_lists.isocpp.org" <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<https://urldefense.proofpoint.com/v2/url?u=https-3A__en.wikipedia.org_wiki_Sparse-5Fmatrix&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=ZI5y0ODwrA1EXk83ILyzF4geEp6evAgNgCr50wWA6Bc&e=>

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]<mailto: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<https://urldefense.proofpoint.com/v2/url?u=http-3A__www.cs.cmu.edu_afs_cs_academic_class_15210-2Ds12_www_lectures_lecture07.pdf&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=RYB22hq8C5bRgfZN3liI8CH6zk0tSDeVLaGSJLn7rPA&e=>

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<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.sciencedirect.com_topics_computer-2Dscience_adjacency-2Dlist&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=a-jJ7efelcI-kqndMOWh7b1H2GblbpAbapYHB9hmWTM&e=>

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]<mailto:sg19-bounces_at_[hidden]>> on behalf of Sebastian Messmer via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>>

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

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

To: "sg19_at_[hidden].org<mailto:sg19_at_[hidden]>" <sg19_at_[hidden]<mailto:sg19_at_[hidden]>>

Cc: Sebastian Messmer <messmer_at_[hidden]<mailto: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<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.researchgate.net_figure_The-2Dadjacency-2Dlist-2Ddata-2Dstructure-2Dused-2Din-2Dour-2Dimplementation-2Dshown-2Dfor-2Da-2Dsample-2Dgraph-5Ffig1-5F268988477&d=DwMGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=0lgLljvQbuXjGY1x4_LhVs9Hik03kRnKOPRqi6uOhiQ&s=EunKpm1egr80k-5bpYwtNR8_zUxmcsCCHGDVktk5uxU&e=>

(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]<mailto:SG19_at_[hidden]>

http://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.isocpp.org_mailman_listinfo.cgi_sg19&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=8RLQ8jsgtPuCBmYgXb1ZSgZAlejrpQBL5V8omXpWh04&e=>

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_lists.isocpp.org" <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<https://urldefense.proofpoint.com/v2/url?u=https-3A__en.wikipedia.org_wiki_Sparse-5Fmatrix&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=ZI5y0ODwrA1EXk83ILyzF4geEp6evAgNgCr50wWA6Bc&e=>

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]<mailto: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<https://urldefense.proofpoint.com/v2/url?u=http-3A__www.cs.cmu.edu_afs_cs_academic_class_15210-2Ds12_www_lectures_lecture07.pdf&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=RYB22hq8C5bRgfZN3liI8CH6zk0tSDeVLaGSJLn7rPA&e=>

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<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.sciencedirect.com_topics_computer-2Dscience_adjacency-2Dlist&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=a-jJ7efelcI-kqndMOWh7b1H2GblbpAbapYHB9hmWTM&e=>

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]<mailto:sg19-bounces_at_[hidden]>> on behalf of Sebastian Messmer via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>>

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

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

To: "sg19_at_[hidden].org<mailto:sg19_at_[hidden]>" <sg19_at_[hidden]<mailto:sg19_at_[hidden]>>

Cc: Sebastian Messmer <messmer_at_[hidden]<mailto: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<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.researchgate.net_figure_The-2Dadjacency-2Dlist-2Ddata-2Dstructure-2Dused-2Din-2Dour-2Dimplementation-2Dshown-2Dfor-2Da-2Dsample-2Dgraph-5Ffig1-5F268988477&d=DwMGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=0lgLljvQbuXjGY1x4_LhVs9Hik03kRnKOPRqi6uOhiQ&s=EunKpm1egr80k-5bpYwtNR8_zUxmcsCCHGDVktk5uxU&e=>

(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]<mailto:SG19_at_[hidden]>

http://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.isocpp.org_mailman_listinfo.cgi_sg19&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=JjgYvsu9MrGGUueQx61-XQ&m=eGJr_WF0w0aKrlp_5I7WGGI8rGJqqFXrcbjcRQm-7MI&s=8RLQ8jsgtPuCBmYgXb1ZSgZAlejrpQBL5V8omXpWh04&e=>

Received on 2019-07-25 16:45:19