Document Open Access Logo

NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20

Authors Andrew Lumsdaine , Luke D'Alessandro, Kevin Deweese, Jesun Firoz , Xu Tony Liu , Scott McMillan , John Phillip Ratzloff, Marcin Zalewski

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2022.31.pdf
  • Filesize: 1.55 MB
  • 28 pages

Document Identifiers

Author Details

Andrew Lumsdaine
  • University of Washington, Seattle, WA, USA
  • Pacific Northwest National Laboratory, Richland, WA, USA
  • TileDB, Inc., Cambridge, MA, USA
Luke D'Alessandro
  • Indiana University, Bloomington, IN, USA
Kevin Deweese
  • Cadence Design Systems, San Jose, CA, USA
Jesun Firoz
  • Pacific Northwest National Laboratory, Richland, WA, USA
Xu Tony Liu
  • University of Washington, Seattle, WA, USA
Scott McMillan
  • Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA, USA
John Phillip Ratzloff
  • SAS Institute, Cary, NC, USA
Marcin Zalewski
  • NVIDIA, Seattle, WA, USA

Funding

This work was partially supported by the High Performance Data Analytics (HPDA) program and the Segmented Global Address Space (SGAS) LDRD under the Data Model Convergence (DMC) initiative at the U.S. Department of Energy’s Pacific Northwest National Laboratory (PNNL). PNNL is operated by Battelle Memorial Institute under Contract DE-AC06-76RL01830. This research was partially supported by NSF Awards OAC-1716828 and OAC-2126266. This material is also based upon work funded and supported by the Department of Defense under Contract No. FA8702-15-D-0002 with Carnegie Mellon University for the operation of the Software Engineering Institute, a federally funded research and development center [DM22-0432].

Cite AsGet BibTex

Andrew Lumsdaine, Luke D'Alessandro, Kevin Deweese, Jesun Firoz, Xu Tony Liu, Scott McMillan, John Phillip Ratzloff, and Marcin Zalewski. NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 31:1-31:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ECOOP.2022.31

Abstract

The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption. In this paper we show that the richness of graph algorithms and data structures can in fact be captured by straightforward composition of existing C++ mechanisms. Generic programming is algorithm-oriented. Accordingly, we apply a systematic approach to analyzing a broad set of graph algorithms, "lift" unnecessary constraints from them, and organize the resulting set of minimal common type requirements, i.e., concepts, for defining their interfaces. By using the newly available ranges and concepts in C++20, the type requirements for generic graph algorithms can be succinctly expressed. The generic algorithms and data structures resulting from our analysis are realized in NWGraph, a modern, composable, and extensible C++ library.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Software libraries and repositories
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph library
  • generic programming
  • graph algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Arvind Arasu, Jasmine Novak, Andrew Tomkins, and John Tomlin. PageRank computation and the structure of the web: Experiments and algorithms. In WWW, pages 107-117, 2002. Google Scholar
  2. Ariful Azad, Mohsen Mahmoudi Aznaveh, Scott Beamer, Mark Blanco, Jinhao Chen, Luke D'Alessandro, Roshan Dathathri, Tim Davis, Kevin Deweese, Jesun Firoz, et al. Evaluation of graph analytics frameworks using the gap benchmark suite. In 2020 IEEE International Symposium on Workload Characterization (IISWC), pages 216-227. IEEE, 2020. URL: https://doi.org/10.1109/IISWC50251.2020.00029.
  3. Lewis Baker, Eric Niebler, and Kirk Shoop. tag_invoke: A general pattern for supporting customisable functions. Technical Report P1895R0, JTC1, 2019. URL: http://open-std.org/JTC1/SC22/WG21/docs/papers/2019/p1895r0.pdf.
  4. Scott Beamer, Krste Asanović, and David Patterson. The GAP Benchmark Suite. arXiv, 2015. URL: https://doi.org/10.48550/ARXIV.1508.03619.
  5. Scott Beamer, Krste Asanović, and David A. Patterson. Direction-optimizing breadth-first search. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 1-10, 2012. URL: https://doi.org/10.1109/SC.2012.50.
  6. Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. WWW, pages 595-601, 2004. URL: https://doi.org/10.1145/988672.988752.
  7. Ulrik Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163-177, 2001. URL: https://doi.org/10.1080/0022250X.2001.9990249.
  8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, 3rd ed edition, 2009. Google Scholar
  9. Timothy A. Davis and Yifan Hu. The university of florida sparse matrix collection. ACM Trans. Math. Softw., 38(1), December 2011. URL: https://doi.org/10.1145/2049662.2049663.
  10. Balázs Dezső, Alpár Jüttner, and Péter Kovács. Lemon-an open source c++ graph template library. Electronic Notes in Theoretical Computer Science, 264(5):23-45, 2011. URL: https://lemon.cs.elte.hu/trac/lemon.
  11. 9th DIMACS implementation challenge - Shortest paths, 2006. URL: http://www.dis.uniroma1.it/challenge9/.
  12. Paul Erdős and Alfréd Rényi. On random graphs. I. Publicationes Mathematicae, 6:290-297, 1959. Google Scholar
  13. Douglas Gregor and Andrew Lumsdaine. Lifting sequential graph algorithms for distributed-memory parallel computation. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA '05, pages 423-437, New York, NY, USA, 2005. ACM. URL: https://doi.org/10.1145/1094811.1094844.
  14. Intel. Intel Threading Building Blocks (TBB), 2020. URL: https://github.com/oneapi-src/oneTBB.
  15. Mark T Jones and Paul E Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 14(3):654-669, 1993. URL: https://doi.org/10.1137/0914041.
  16. Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and L. Paul Chew. Optimistic parallelism requires abstractions. In PLDI, pages 211-222. ACM, 2007. URL: https://doi.org/10.1145/1250734.1250759.
  17. Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is twitter, a social network or a news media? In Proceedings of the 19th International Conference on World Wide Web, WWW '10, pages 591-600, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1772690.1772751.
  18. Andrew Lumsdaine, Luke Dalessandro, Kevin Deweese, Jesun Firoz, and Scott McMillan. Triangle counting with cyclic distributions. In 2020 IEEE High Performance Extreme Computing Conference (HPEC), pages 1-8, 2020. URL: https://doi.org/10.1109/HPEC43674.2020.9286220.
  19. Ulrich Meyer and Peter Sanders. Δ-stepping: a parallelizable shortest path algorithm. Journal of Algorithms, 49(1):114-152, 2003. 1998 European Symposium on Algorithms. URL: https://doi.org/10.1016/S0196-6774(03)00076-2.
  20. Richard C. Murphy, Kyle B. Wheeler, Brian W Barrett, and James A. Ang. Introducing the Graph 500. In Cray User’s Group. CUG, 2010. Google Scholar
  21. David R. Musser and Alexander A. Stepanov. Generic programming. In P Gianni, editor, International Symposium ISSAC 1988, volume 38 of Lecture Notes in Computer Science, pages 13-25. Springer-Verlag, 1989. Google Scholar
  22. Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A lightweight infrastructure for graph analytics. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13, pages 456-471, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2517349.2522739.
  23. Eric Niebler, Casey Carter, and Christopher Di Bella. The one ranges proposal. Technical report, Tech. rep. P0896r4. Nov. 2018., 2018. URL: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0896r4.pdf.
  24. S. M. Orzan. On Distributed Verification and Verified Distribution. Ph.d. thesis, VRIJE UNIVERSITEIT, November 2004. URL: http://dare.ubvu.vu.nl/handle/1871/10338.
  25. Roman Shaposhnik, Claudio Martella, and Dionysios Logothetis. Practical Graph Analytics with Apache Giraph. Apress, New York, 1st ed. edition edition, October 2015. Google Scholar
  26. Yossi Shiloach and Uzi Vishkin. An O(logn) parallel connectivity algorithm. Journal of Algorithms, 3(1):57-67, 1982. URL: https://doi.org/10.1016/0196-6774(82)90008-6.
  27. J. Shun, L. Dhulipala, and G. Blelloch. A simple and practical linear-work parallel algorithm for connectivity. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '14, pages 143-153. ACM, 2014. URL: https://doi.org/10.1145/2612669.2612692.
  28. Julian Shun and Guy E. Blelloch. Ligra: A lightweight graph processing framework for shared memory. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’13, pages 135-146, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2442516.2442530.
  29. Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, 2002. Google Scholar
  30. Alexander Stepanov and Meng Lee. The standard template library. Technical Report HPL-95-11, HP Laboratories, November 1995. URL: http://stepanovpapers.com/STL/DOC.PDF.
  31. Alexander Stepanov and Paul McJones. Elements of Programming. Addison-Wesley Professional, 1st edition, 2009. Google Scholar
  32. Michael Sutton, Tal Ben-Nun, and Amnon Barak. Optimizing parallel graph connectivity computation via subgraph sampling. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 12-21. IEEE, 2018. URL: https://doi.org/10.1109/IPDPS.2018.00012.
  33. Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D. Owens. Gunrock: A high-performance graph processing library on the gpu. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '16, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2851141.2851145.
  34. Da Yan, James Cheng, Kai Xing, Yi Lu, Wilfred Ng, and Yingyi Bu. Pregel algorithms for graph connectivity problems with performance guarantees. Proc. VLDB Endow., 7(14):1821-1832, 2014. URL: https://doi.org/10.14778/2733085.2733089.
  35. Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, and Julian Shun. Optimizing ordered graph algorithms with GraphIt. In CGO, pages 158-170. ACM, 2020. URL: https://doi.org/10.1145/3368826.3377909.
  36. Yunming Zhang, Mengjiao Yang, Riyadh Baghdadi, Shoaib Kamil, Julian Shun, and Saman Amarasinghe. Graphit: A high-performance graph dsl. Proc. ACM Program. Lang., 2(OOPSLA), October 2018. URL: https://doi.org/10.1145/3276491.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact