Skip to content
forked from KaHIP/KaHIP

The graph partitioning framework KaHIP -- Karlsruhe High Quality Partitioning.

License

GPL-2.0, GPL-2.0 licenses found

Licenses found

GPL-2.0
LICENSE
GPL-2.0
COPYING
Notifications You must be signed in to change notification settings

SebastianSchlag/KaHIP

 
 

Repository files navigation

KaHIP v2.0

The graph partitioning framework KaHIP -- Karlsruhe High Quality Partitioning.

The graph partitioning problem asks for a division of a graph's node set into k equally sized blocks such that the number of edges that run between the blocks is minimized. KaHIP is a family of graph partitioning programs. It includes KaFFPa (Karlsruhe Fast Flow Partitioner), which is a multilevel graph partitioning algorithm, in its variants Strong, Eco and Fast, KaFFPaE (KaFFPaEvolutionary) which is a parallel evolutionary algorithm that uses KaFFPa to provide combine and mutation operations, as well as KaBaPE which extends the evolutionary algorithm. Moreover, specialized techniques are included to partition road networks (Buffoon), to output a vertex separator from a given partition as well as techniques geared towards the efficient partitioning of social networks.

NEW in v2.0:

ParHIP (Parallel High Quality Partitioning): Our distributed memory parallel partitioning techniques designed to partition hierarchically structured networks such as web graphs or social networks.

Mapping Algorithms: Our new algorithms to map the blocks onto processors to minimize overall communication time based on hierarchical partitionings of the task graph and fast local search algorithms.

Main project site:

http://algo2.iti.kit.edu/documents/kahip/index.html

Installation Notes

Before you can start you need to install the following software packages:

Once you installed the packages, just type ./compile.sh. Once you did that you can try to run the following command:

./deploy/kaffpa examples/delaunay_n15.graph --k 2 --preconfiguration=strong

For a description of the graph format please have a look into the manual.

Travis-CI Status Build Status

About

The graph partitioning framework KaHIP -- Karlsruhe High Quality Partitioning.

Resources

License

GPL-2.0, GPL-2.0 licenses found

Licenses found

GPL-2.0
LICENSE
GPL-2.0
COPYING

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 95.3%
  • Python 2.6%
  • Other 2.1%