PGL: A library of efficient graph structures and algorithms for large scale networks

This is a library of algorithms and data structures. Its main goal is to provide structures and algorithms optimized for large-scale graphs. The main building block is a dynamic graph structure, called Packed-memory Graph, that combines the static forward star graph structure with dynamic arrays (packed-memory arrays). It achieves a good cache efficiency during both normal static graph operations, like algorithm queries (which usually operate on a static graph layout), and updates of the layout of the graph. The library also contains several algorithms for shortest path computations on large-scale networks with either single or multi criteria edge costs.

• The library contains the following:

  Data Structures Graphs Adjacency List Dynamic Forward Star Packed-memory Graph Trees Complete Binary Tree Heap / Priority Queue Arrays Node-array Edge-array Packed-memory Array Dictionary/Map

  Shortest Path Algorithms Dijkstra's Algorithm A* Algorithm Euclidean Distances Landmarks Multi-objective Dijkstra's Algorithm NAMOA*

  Utilities Timer Random Number Generator Readers/Writers for the following formats: 9th DIMACS implementation challenge format 10th DIMACS implementation challenge format GML DDSG json

• Acquiring the library

  The library is hosted in this git repository. In order to get a local copy please execute git clone http://vernon.ceid.upatras.gr/git/pgl.git

• Reference Manual

  The reference manual of the library is located here

• Prerequisites
  • the Boost library
  • graph files (for example one of the 10th DIMACS Implementation Challenge maps)

• Getting Started

  To test the library, you can try the example that is provided in it. You can compile the example application using the Makefile it contains. You will need: 1) the PGL library, 2) the Boost library, 3) a DIMACS10 map. You should check the following:

  • The Makefile contains the correct path to the pgl/include folder
  • The Makefile contains the correct path to the boost header files folder (you have to install boost first, speciffically libboost-dev and libboost-program-options)
  • The example.cpp file contains a correct path to a map and a coordinates file (Lines 155-156). Available maps can be found here

• Related Publications/Talks
  • A. Paraskevopoulos and C. Zaroliagis, "Improved Alternative Route Planning"
    in Proc. 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems - ATMOS 2013, OASIcs Series, to appear.
  
  
  • C. Zaroliagis, "Engineering Multiobjective Shortest Path Heuristics"
    in 22nd International Conference on Multiple Criteria Decision Making - MCDM 2013 [invited talk].
  
  
  • G. Mali, P. Michail, A. Paraskevopoulos, and C. Zaroliagis, "A New Dynamic Graph Structure for Large-Scale Transportation Networks"
    in Algorithms and Complexity - CIAC 2013, Lecture Notes in Computer Science Vol.7878 (Springer 2013), pp. 312-323.
  
  
  • G. Mali, P. Michail, and C. Zaroliagis, "Faster Multiobjective Heuristic Search in Road Maps" ,
    in Proc. Int. Conf. on Advances in Information and Communication Technologies - ICT 2012, Vol. 3, pp. 67-72.
  
  
• People
  • Georgia Mali
    
  • Panos Michail
    
  • Andreas Paraskevopoulos
    
  • Nikos Rousias
    
  • Christos Zaroliagis