Aqueduct

Aqueduct is a Java library for graph theory.

Quick start

Before digging into deeper details, let's begin with a quick example that builds a graph and run a BFS on it. The graph is directed and contains 5 vertices labeled from 01 to 05. It only contains 3 edges:

• one from 01 to 03
• one from 04 to 05
• one from 02 to 01

final Graph graph = new Directed();
graph.addEdge(new Vertex("01"), new Vertex("03"), 2.);
graph.addEdge(new Vertex("04"), new Vertex("05"), 1.);
graph.addEdge(new Vertex("02"), new Vertex("01"), 4.);
        
final Breadth bfs = new Breadth(graph, new Vertex("01"));
while (bfs.hasNext()) {
    System.out.println(bfs.next());
}

The BFS is run from the vertex 01. Obviously, this program will only outputs the vertices 01 and 03.

For large graphs, it would be more convenient to use the classes DirectedText and UndirectedText. These classes takes in one of their constructor a java.nio.file.Path to a textual file that has a predefined structure:

• The first line contains a single number representing the number of graph vertices. The resulting graph will have n vertices labeled from 1 to n
• The subsequent lines represents edges and contains each 3 numbers separated by one space character. The first number is the label of the edge starting vertex. The second number is the label of the edge ending vertex. The third number is the cost of the edge.

The previous graph could be represented by this text file:

5
1 3 2
4 5 1
2 1 4

(with a subtle difference which is the vertices are labeled 1 to 5, without the leading 0).

The code becomes:

final Graph graph = new DirectedText(
    Paths.get(ClassLoader.getSystemResource("graph.txt").toURI())
);
        
final Breadth bfs = new Breadth(graph, new Vertex("01"));
while (bfs.hasNext()) {
    System.out.println(bfs.next());
}

Supported features

Aqueduct supports these features (class names are given here):

• Breadth (BFS) and Depth (DFS)
• Dijkstra, DijkstraFast (Heap based), BellmanFord, FloydWarshall and Johnson
• Kruskal, Prims and PrimsFast (Heap based)
• TSP (Travel salesman)
• MaxFlow
• VertexCover

How to contribute

To contribute, just submit a pull request. The pull request should necessarily resolves an issue. Feel free to create an issue if your pull request does not solve an existing issue. Keep in mind that:

• The project uses Qulice 0.18.19
• Pull requests has a travis build check, and a coveralls test coverage check
• Coveralls check succeeds if coverage is at least 85%, and if the coverage does not drop from the last check by more than 5%
• If the two checks succeeds and code review comments (if any) are resolved, the pull request will be labeled by tomerge. This will trigger a GitHub workflow
• The pull request merging GitHub workflow will:
  • Checkout your branch
  • Merge it locally (inside the container running the workflow) with master branch
  • Perform a build (mvn clean install)
  • If the build succeeds the PR is merged into master branch
  • This guarantees that the master branch is always in a succeeding build state