图的动态存储针对的情况是批量更新，dynamic_local_graph实现图的动态存储的类。而不是随机拔出。采用邻接矩阵来表示顶点之间的相邻关系，给定一个图GV,graphlab中。E使用一个一维数组存储V顶点信息，使用一个稀疏矩阵来存储E边信息。图是分布在多个机器之上，graphlab中。每个机器中存储着图的一部分，这里我讨论每个节点是如何实现图的外地存储。分别是获取顶点的inedg和outedg那么在graphlab中需要考虑如何有效地存储一个图的边集合，graphlab图相关接口中有两个接口。并可以快速地对顶点的inedg和outedg进行快速索引，并尽可能地减少空间开销。

并高效地实现获取顶点的inedg和outedg接口。Graphlab中采用的思路是同时采用稀疏矩阵的csrcompresssparsrow和csccompresssparscolumn存储格式来存储图的边集合。

静态存储是指一旦完成对图的顶点和边的存储之后，Graphlab分别实现了图的静态存储和动态存储。不会添加新的顶点和边。而动态存储，可以动态地往图中新增顶点和边，这两者都没有删除顶点和边的操作。静态存储和动态存储的思路都是同时采用稀疏矩阵的csr和csc格式来存储边集合，不过csr和csr采用的数据结构不一样，静态存储采用数组实现，动态存储采用链表实现。本篇博客中，只对静态存储进行介绍，动态存储会在下一篇博客中进行介绍。然后会举一个实际的例子来分析graphlab图的静态存储，本篇博客首先会介绍一下稀疏矩阵的csr和csc格式以及计数排序。最后介绍一下graphlab实现图静态存储的相关类。

csr和csc格式介绍，稀疏矩阵用A表示，三个数组分别是valurowptr和columnvalu中按行顺序存储着A中的非零单元的值。Column中存储着valu数组中的单元的列索引，valuk=Ai,csr使用三个数组来表示一个稀疏矩阵。j则columns[k]=jRowptr中存储着行在valu中的起始地址，如果valuk=Ai,j则rowptri<=k<rowptri+1行i中的非零单元的数目为rowptri+1-rowptri

比如稀疏矩阵A=，那么行是{0,假设下标都从0开始。1,2}列也是{0,1,2}稀疏矩阵Acsr格式就可以用如下三个数组表示：

image，只不过是把行换成了列,csc格式类似于。csc可以用valucolumnptr和row表示矩阵Avalu中按列顺序存储着A中的非零值；row中存储着valu数组中单元的行索引,valuk=Ai,j,则rowk=icolumnptr中存储着列在valu中的起始地址，valuk=Ai,j则columnj<=k<columnj+1j列的非零单元数目为columnj+1-columnj

image，此处k为某个整数。对每一个输入元素x统计小于x数目s那么可以通过s来确定x最终输出数组中的位置。计数排序的思路如下：假设n个输入元素中的每一个都是介于0-k整数。计数排序的输入是一个未经排序的原始数组A输出是两个数组，graphlab中。分别是P和IP数组长度等于原始数组的长度，按从小到大对原始数组进行排序后生成的序列数组，P[i]表示排序后的第i个值在原始数组中的下标；I数组表示值为i整型在排序后的数组中的起始位置，I数组的长度为max{A [i]}+1+1原因是从0开始计数）

Graphlab中计数排序算法的伪码：

clip_image008

比如给定一个原始数组A数组长度为7数组中存储着整型值（可能有重复）

clip_image010

运行结果：

原始数组（A和统计数组（c如下所示：counting_sort函数中12-13行的循环运行完后。

clip_image012

值小于等于i元素数目。c[i]存储着在A中。

总共有：第15-16运行方法如下。

clip_image014

值小于i元素数目。iA中的数目等于：c[i+1]-c[i]i<k或n-c[i]i==kc[i]表示i值在P数组出现的第一个值的下标。最后P数组存储着排序后的数值在原数组中的下标。c数组中的每个单元c[i]中则存储着在A数组中。

最终I数组的结果等于stem6中的c

clip_image016

给定一个值2那么2A中的数目为：I[3]-I[2]=12A中的位置为A[P[I[2]]]=A[1]

使用csr和csc存储图，使用稀疏矩阵的csr和csc格式来存储邻接矩阵。可以将边集合表示为一个邻接矩阵。可以根据row来快速对稀疏矩阵的某一行进行检索，所以使用csr来对out_edg进行检索（边(v,因为稀疏矩阵的csr存储格式是对row进行压缩。w顶点voutedges,顶点v对于边(v,w相当于行）同理，稀疏矩阵的csc存储格式是对column进行压缩，可以根据column来快速对稀疏矩阵的某一列进行检索，所以使用csc对in_edg进行检索。并实现对顶点的inedg和outedg快速检索。先单独分别从csr和csc角度考虑边集合的存储。然后再分析graphlab如何同时使用csr和csc巧妙地实现对边集合进行存储。

1CSR格式存储，给定以一个有向图GVEV为顶点集合，E为边集合。一条边包括顶点对（边从sourcvertex指向targvertex和值，边集合可以表示成如下的邻近矩阵，对于边(w将v作为行，w作为列(sourcvertex对应行，targetvertex对应列)

那么我就可以用如下三个数组来表示输入的边集合E那么如何将输入的E转化为按照csr格式存储的稀疏矩阵呢？使用1.2张中的counting_sort进行排序，1.将sourcvertex数组作为输入数组。输出的数组为P和I因为sourcvertex相当于邻接矩阵的行，这一方法等同于将稀疏矩阵的非零单元依照行顺序存储在一个数组中（这里不需要考虑同一行内的各个边的顺序）那么P按行的从小到大顺序对原始数组进行排序后生成的序列数组；I等于csr中的rowptr，那么排序后的targetvertex数组就是csr中的columnvalu数组就是csrvalu这里的排序可以使用不同的方式实现，2.使用P对输入边集合Etargetvertex数组和valu数组依照行大小进行重新排序。最简单的方法就是引入一个临时数组，依照P数组中的下标对targetvertex和valu进行排序。

1.edges_valu数组：按行顺序进行排序后边集合的值数组。

rowptrs[i]第i行在edges_valu中的起始偏移位置；那么第i行的边数目等于rowptrs[i+1]–rowptrs[i]或edges_valu长度 – rowptrs[i]rowptr数组的长度为顶点的最大值。2.rowptr数组：保管行在edges_valu中的起始偏移地址。

columns[i]edges_values[i]值对应的边的列的值。如edges_values[2]列为columns[2]等于33.column数组：列索引。

那么v所有outedg值可以通过如下的方式获取：那么用csr存储的边集合E给定一个顶点v可以快速检索v所有outedg值。v值相当于行。

clip_image028

顶点1outedg数目为rowptrs[2]– rowptrs[1]=2那么可以得到顶点1两个outedgedges_valu数组的下标分别为1和2那么outedg集合为{edges_values[1],拿上面的例子。edges_values[2]}={1,2,1,3}

2.2CSC格式存储，与csr基本相同。首先将targetvertex数组作为输入数组进行counting_sort得到P和II为csccolumnptr使用P对Esourcvertex数组和valu数组进行排序，使用csc来存储边集合E边关系和值。生成了cscrow和valuE以csc格式存储的最终结果如下所示。

image

1.edges_valu数组：按列顺序进行排序后边集合的值数组。columnptrs[i]第i列在edges_valu中的起始偏移位置；2.columnptr数组：保管列在edges_valu中的起始偏移地址。rows[i]edges_values[i]值对应的边的列的值。3.row数组：列索引。通过csc获取一个顶点的inedg类似于在csr中获取outedg不在赘述。

2.3Graphlab图的静态存储，会首先对边集合按照csr方式进行存储（通过对sourcvertex进行counting_sort然后再建立csc格式，Graphlab对图的静态存储是同时采用了csr和csc格式。graphlab中。通过shuffl方式，csc和csr之间进行转换。把csr和csc整合到一起，同时实现对顶点的outedg和inedg快速索引。

edges_valu同CSR中的rowptr

rowptr同CSR中的rowptr

column同CSR中的column

shuffleptr这个数组用于将按列顺序排列的稀疏矩阵转换为按行顺序排列的稀疏矩阵。Shuffleptrs[i]表示按列顺序排序的边集合的第i条边在edges_valu数组中的下标。

row同CSC中的row

columnptr同CSC中的columnptr

内存中存储边集合E需要维持边的值数组，csr和cscCSR有两个整型数组，rowptr和column分别用来存储行偏移地址和列索引。CSC有三个整型数组，shuffleptrrow和columnptr分别存储着从按列顺序排序的稀疏矩阵到按行顺序排列的稀疏矩阵转换的下标，行索引和列偏移地址，shuffleptr和row具有相同的下标，可以合并成一个数组。

具体方法：source_arrtarget_arr和data_arr分别存储着边的sourcvertextargetvertex和边的值。sourcvertex相当于邻接矩阵的行，E原始输入由三个相同长度的数组组成。targetvertex相当于邻近矩阵的列。如果要形成最终的结果，需要以下这些方法，才干形成上图中的存储。

P,1.counter_sortsource_arr.rowptr

E2.sortP.

//使用P依照行顺序对E中的三个数组进行排序,P数组是依照行的顺序保管着E下标。

3.column=target_arr

columns4.csr={rowptrs.}

P,5.counter_sourttarget_arr.columnptr

source_arr6.sortP.

最后作为行索引//对source_arr按列顺序进行排列。

7.row=source_arr;shuffleptr=P.

rows,8.csc={columnptrs.shuffleptrs}

Graphlab中的具体类：

图的外地静态存储是由local_graph来实现，graphlab中。local_graph中保存图使用了四个数据结构：

顶点的ID为0数组的长度。std::vector<VertexData>vertic存储顶点数据的数组。

相当于edges_valustd::vector<EdgeData>edg存储边的值的数组。

csr_type_csr_storag表示csr由csr_storag这个类来实现。

csc_type_csc_storag表示csc由csr_storag这个类来实现。

分别是csr_storag中有两个成员变量。

std::vector<sizetype>value_ptrs;

std::vector<valuetype>values;

value_ptr等同于rowptr一个uint64_t数组；valu等同于column也是一个uint64_t数组。当csr_storag表示csr时。

value_ptr等同于columnptr一个uint64_t数组；valu则被定义成std::vector<std::pair<lvid_type,当csr_storag表示csc时。edge_id_type>>相当于将row和shuffleptr存储在同一个vector中。

不过在csr和csc底层数据结构设计上做了一些调整，Graphlab实现对图的动态存储也是基于csr和csc格式。将数组替换为分块链表。如果实现对图的动态存储，那么需要把底层的数据结构从数组换成链表，但需要对原先在静态图存储中所用的那套算法做些调整。数据结构使用vector只是将批量插入的边的权值按顺序放入到vector中。1.Edge一个数组。表示按邻近矩阵的行（即边的sourcvertex大小排序的列的链表，如上图所示，Block内容如下，Block固定长度的pair<uint64_t,2.CSR由行迭代器数组rowIter和column组成。column一个分块链表。uint64_t>数组，多个block组成一个链，pairfirst邻接矩阵的列（即边的targetvertexsecond列所在边在edg数组中的位置。CSRrowIter对链表的行建立索引，rowIterator[i]指向行icolumn中的起始位置偏移地址。

wps_clip_image-9300，表示按邻接矩阵的列（即边的targetvertex大小排序的行的链表，如上图所示，Block内容如下，Block固定长度的pair<uint64_t,3.对于CSC有列迭代器数组colIter和row组成。Row一个分块链表。uint64_t>数组，多个block组成一个链，pairfirst邻接矩阵的行（即边的targetvertexsecond行所在边在edg数组中的位置。colIter对链表的列建立索引，colIterators[j]指向列jrow中的起始位置偏移地址。

wps_clip_image-9345

源码中对csr和csc构建和动态插入的整体流程：source_vertex数组（边的源顶点）target_vertex数组（边的目标顶点）和边的值数组edge_valu批量输入的边可以用三个数组来表示。输出P1和rowptrP1按行从小到大顺序对source_vertex进行排序后生成的序列数组；rowptrs[i]指向第i行在P1中的起始偏移地址，1.对source_vertex数组进行计数排序。P1[rowptrs[i]+k]表示第i行的第k个元素在edg数组中的位置，其中 0<=k<rowptrs[i+1]-rowptrs[i]，输出P2和colptrP2按列从小到大顺序对target_vertex进行排序后生成的序列数组；colptrs[j]指向第j列在P2中的起始偏移地址，2.对target_vertex数组进行计数排序。P2[colptrs[j]+k]表示第j列的第k个元素在edg数组中的位置，其中0<=k<colptrs[j+1]-colptrs[j]

所以需要将计数排序后得到rowptrP1和target_vertex转化为迭代器数组和pair<col,3.由于CSR底层数据结构是分块链表和行迭代器数组指针。pos>数组。分块链表的block固定长度的pair<col,pos>数组，所以利用P1和target_vertex来构建pair<col,pos>数组csr_valu第i个输入的边在csr_valu中的值为{target_vertex[P1[i]],lengthedg+P1[i]}，则用rowptr和csr_valu来初始化CSR即将csr_valu中的值赋值给CSRcolumn然后将rowptr行起始位置转化为column中的迭代器，3.1如果图为空。放入到rowIter中。

则按行向CSR插入数据，3.2如果图不为空。一次插入一行，第i行在csr_valu中的值是从csr_values[P1[i]]至csr_values[P1[i+1]]这一段数据。如下图所示的CSRrowIter一个迭代器的数组，rowIterators[i]存放第i行在column中的起始位置，rowIterators[i+1]为第i行的结束位置也是第i+1行的起始位置；column一个分块链表。蓝色为第i行的数据，橙色为i+1行的数据。绿色为需要新插入的第i行的数据。

CSR插入行的方法如下：往第i行插入新数据。

A .首先会找到rowIterators[i+1]所指向的第i行的结束位置Po将此block中位于Po之后的第i+1行的数据段预先保管起来。

如果新插入的数据过长，B.将第i行的新数据拷贝到Po之后位置上。那么会创建一个或多个新的block来容纳。

C.将预先保存的第i+1行的数据重新拷贝到新插入数据之后。

第i+1行的迭代器指针变为无效，D.上述操作完成之后。指向的数据位置为第i行新插入的数据，所以要调整第i+1行的迭代器指针。block中的红色空格，E.最后因为按行将数据拔出到CSR中会发生一些空隙。所以会在所有行都插入后，进行repack操作，将空白的内存进行压缩，这种做法的只能支持动态地批量插入，CSC处置类似于CSR不在赘述。随机拔出的性能开销太大。

可以进行动态的拔出。Dynamic_block就是实现这个内存块的类，dynamic_block图的动态存储的底层数据结构采用内存块的链表。dynamic_block组成了一个块的链表。使用dynamic_block组成的一个单向链表。block_linked_list分块链表。将底层的数组替换为链表，dynamic_csr_storag实现csr和csc动态存储的数据结构。然后使用链表的迭代器数组来实现记录行或列的起始位置。