11
$\begingroup$

Hello scicomp community,

I have worked in the area of graph algorithms using frameworks such as NetworkX (Python), JUNG and YFiles (Java). I am now entering the area of parallel and high perfomance computing. For a new project, I am looking for a C++ graph library with the following features:

  • has an intuitive interface that enables algorithm development
  • supports dynamic operations: e.g. arbitrary node/edge insertions and deletions
  • supports parallelization: e.g. shields the programmer from issues arising with multithreading
  • has a low memory overhead and is suitable for high performance computing

Please suggest some libraries and discuss these criteria as well as pros and cons.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
11
+50
$\begingroup$

Boost Graph Library and LEMON

As Daniel mentions in his comprehensive answer, the most full-featured general C++ library is the Boost Graph Library. There is a new distributed-memory extension capable of doing some basic algorithms such as breadth-first and depth-first search, minimum spanning trees, and connected components search, but I am not very familiar with the new project. The Boost Graph Library itself is well-reputed and used in many projects around the world.

If you are doing basic HPC graph work, you might want to start with the Boost Graph Library, but be aware that many HPC C++ compilers have difficulty with Boost (despite its fairly strict adherence to C++ standards), and you may need to use an older version of Boost or a non-vendor compiler such as GCC to get it working on HPC systems.

A quick browse of LEMON's repositories shows that there is involvement from the IBM BlueGene supercomputing team, but I don't see any dependencies or configuration for MPI, so this is likely to only be a serial graph library at the moment.

Load-balancing and Dynamic graph (re)-partitioning

If you are interested in load-balancing and dynamic graph partitioning, you have several more options. Perhaps the most well-known library is ParMETIS, which was updated to version 4 last year. ParMETIS features vertex-based weighting, which is important for multi-physics simulations.

ParMETIS's European competitor is PT-Scotch, which has had better performance for certain types of problems, but, similar to ParMETIS, is not frequently updated.

You may also be interested in Zoltan, which is part of the Sandia National Laboratories Trilinos meta-package for scientific computing in C++. Zoltan features its own hierarchical partitioners and interfaces into both ParMETIS and PT-Scotch.

Graph500

If you are working on the bleeding edge of concurrent search, optimization (single source shortest path), and edge-oriented (maximal independent set), you will also be interested in the freely available Graph500 benchmark.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Question: The Parallel Boost Graph Library is meant for distributed-memory parallelism. Is the ordinary Boost Graph Library suitable for shared-memory parallelization with OpenMP? $\endgroup$
    – clstaudt
    Nov 26, 2012 at 12:10
  • $\begingroup$ @clstaudt - This is going to be problem-specific. You are going to have to get deeper into the details of your algorithm for a better answer (and it would probably be a new question). $\endgroup$
    – Aron Ahmadia
    Nov 26, 2012 at 14:40
5
$\begingroup$

Perhaps, the Boost Graph Library is what you are looking for. It has a parser to read graphs specified in GraphViz's DOT format. While i don't really know about memory overhead, it does provide a variant for parallelization.

Another graph library is LEMON but i don't really know it and if it has support for parallelization, it's not advertised. It's website makes a good impression though ;)

Improve this answer
$\endgroup$
2
  • $\begingroup$ LEMON looks good to me, too, but I have absolutely no idea whether I can use it for shared-memory parallel code (OpenMP). $\endgroup$
    – clstaudt
    Nov 26, 2012 at 12:22
  • $\begingroup$ Me neither, to be honest. But perhaps you can use it to declare shared data structures for your problem and run it's algorithms in different threads. Maybe you can subdivide your problem into suitable subproblems. $\endgroup$
    – Daniel Eberts
    Nov 26, 2012 at 12:26
5
$\begingroup$

I'd also like to mention STINGER, a dynamic graph data structure designed for parallelism. According to the website, it is designed for the following objectives:

Portability: Algorithms written for STINGER can easily be translated/ported between multiple languages and frameworks

Productivity: STINGER should provide a common abstract data structure such that the large graph community can quickly leverage each others' research developments. This is similar in philosophy to the numerical algorithms community implicit use of sparse and dense matrices.

Performance: It is recognized that no single data structure is optimal for every graph algorithm. The objective of STINGER is to configure a sensible data structure that can run most algorithms well. There should be no significant performance reduction for using STINGER when compared with another general data structure across a broad set of typical graph algorithms. STINGER should assume a shared memory address space, and allow both sequential or parallel algorithms. The data structure should allow parallel algorithms to exploit concurrency where possible.

It is not as generic as LEMON or Boost Graph Library and in an earlier stage of development. If you check it out, I'd be interested in your comments.

Improve this answer
$\endgroup$
1
  • $\begingroup$ STINGER Comes out of David Bader's lab at Georgia Tech. He's well-known in the HPC community for his work on the Graph500, thanks for mentioning this one! $\endgroup$
    – Aron Ahmadia
    Nov 27, 2012 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.