Ligra

摘要: There has been significant recent interest in parallel frameworks for processing graphs due to their applicability studying social networks, the Web graph, networks biology, and unstructured meshes scientific simulation. Due desire process large graphs, these systems have emphasized ability run on distributed memory machines. Today, however, a single multicore server can support more than terabyte of memory, which fit with tens or even hundreds billions edges. Furthermore, graph algorithms, shared-memory multicores are generally significantly efficient per core, dollar, joule basis systems, algorithms tend be simpler counterparts.In this paper, we present lightweight framework that is specific parallel/multicore machines, makes traversal easy write. The two very simple routines, one mapping over edges vertices. Our routines applied any subset vertices, useful many operate subsets Based ideas used fast algorithm breadth-first search (BFS), our automatically adapt density vertex sets. We implement several framework, including BFS, radii estimation, connectivity, betweenness centrality, PageRank single-source shortest paths. expressed using concise, perform almost as well highly optimized code. they get good speedups 40-core machine previously reported results machines cores.