Dev guide: Open tasks, projects and collaboration ideas

A detailed list of improvements/additions, that the JGraphT developers have already identified, follows. The list is by no means exhaustive, feel free to enhance functionality in some other area and submit a pull-request.

Demos

• Write visualization demo of various algorithms in action. For example, the ability to single-step a shortest-path traversal.
• Write demo which transforms from DOT into GraphML
• Write demo to execute shortest paths using A* and the ALT heuristic

Importers/Exporters

GraphML

Class GraphMLImporter supports GraphML version 1.0. Add subclasses for the following cases:

• GraphML version 1.1
• SVG extensions
• yEd extensions (ygraphml)

Matrix Market Exchange Format

See this document for the format.

Pajek

See this document for the format's description.

• Add Pajek exporter
• Add Pajek importer, using antlr for the parser.

XGMML

• Add support for XGMML

Named graphs and Generators

• We are still missing a lot of generators

Adapters

Mathematica Adapter

• Add an adapter which enables mathematica and JGraphT using Mathematica's Java interface. This can be similar to our Guava interface and should be done in a separate module.

Matlab Adapter

• Add an adapter which enables Matlab and JGraphT using Matlabs's Java interface. This can be similar to our Guava interface and should be done in a separate module. Matlab has limited support for graph theory objects.

Algorithms

Minimum cut in directed graphs

• Implement the algorithm by Hao and Orlin, A Faster Algorithm for Finding the Minimum Cut in a Directed Graph (1994). Note that this algorithm uses a modified version of the push-relabel algorithm by Goldberg and Tarjan (1988). JGraphT already contains an implementation of this push-relabel algorithm, so one should check whether this implementation can be re-used/extended/modified.

Shortest paths (org.jgrapht.alg.shortestpath)

• Implement large scale routing algorithms
  • Note: a PR #865 has been submitted.

Simple cycles (org.jgrapht.alg.cycle)

• Add interface which returns cycles as list of edges or a GraphPath and change the 4 algorithms to follow the interface.

Minimum mean cycle

• Add an efficient algorithm for finding minimum mean cycle in the directed weighted graph. Consider implementing one of the following algorithms: Karp's original algorithm, Hartman-Orlin algorithm or Howard's algorithm for minimum mean cycle.
  • Note: a PR #862 has been submitted.

Colorings (org.jgrapht.experimental.alg.color)

• Consider implementing the improved backtracking algorithm by Brélaz. See the following document for algorithmic details.
• Implement edge coloring algorithms.

Line graphs

• add method isLineGraph to GraphTests class

Chordal graphs

• Implement minimum triangulation (http://www.ii.uib.no/~pinar/MCS-M.pdf). Use MCS and LexBFS for that.
• Add a StrongChordalityInspector (and GraphTests.isStronglyChordal method). See https://en.wikipedia.org/wiki/Strongly_chordal_graph

Interval graphs

• Implement detection algorithm which tests whether a graph is an interval graph or a comparability graph. This paper might be a good starting point (check for more recent works!). The algorithm must provide a proof if the graph is or isn't an interval graph. Interval graphs have a perfect elimination order. Similar to ChordalGraphColoring, the class should implement a getPerfectEliminationOrder() method.

Cliques

Implement exact and heuristic methods to find the largest clique in a graph. A starting point would be cliquer and the well-known paper A fast algorithm for the maximum clique problem by Patrick Östergård. The new algorithms should be implemented in the org.jgrapht.alg.clique package and implement a new clique interface. This PR could give some inspiration.

Graph Isomorphism

• Add fast algorithms to test graph isomorphisms. Nauty, by Brendan D. McKay might be a good starting point. Old reference: Efficient Algorithms for Graph Isomorphism Testing Jose Luis Lopez Presa PhD thesis (2009)

Graph connectivity

• add method GraphTests.isKConnected to check whether a graph is k-connected
• add algorithms to find the edge-connectivity and vertex connectivity of a graph. A good starting point is the paper "Computing Vertex Connectivity: New Bounds from Old Techniques" by Henzinger, Rao, Gabow, 2000

Dynamic connectivity

• add support for the incremental connectivity
• add support for the decremental connectivity for acyclic and general graphs
• add support for the fully dymamic connectivity for acyclic and general graphs
• attempt to unify these algorithms with a common interface

Graph Polynomials

Add algorithms to compute a number of well-known graph polynomials. For this we need a new data structure to store and represent polynomials. This data structure needs to be compatible with other algorithmic packages. Consider using Apache commons math and in particular the classes PolynomialFunction. Need to check whether a Multivariate version of the PolynomialFunction exists.

• Tutte Polynomial: https://en.wikipedia.org/wiki/Tutte_polynomial and Computing Tutte Polynomials. Gary Haggard, David J. Pearce and Gordon Royle. In ACM Transactions on Mathematical Software, Volume 37(3), article 24, 2010. Preprint: http://homepages.ecs.vuw.ac.nz/~djp/files/TOMS10.pdf
• Chromatic Polynomial: http://mathworld.wolfram.com/ChromaticPolynomial.html. Birkhoff and Lewis, Chromatic Polynomials, Trans. AMS, Vol. 60, p.355–451, 1946.
• Flow Polynomial: http://mathworld.wolfram.com/FlowPolynomial.html
• Rank Polynomial: http://mathworld.wolfram.com/RankPolynomial.html
• Reliability Polynomial: http://mathworld.wolfram.com/ReliabilityPolynomial.html

Measures

• Implement an algorithm to compute the bandwidth of a graph. Add a static method to GraphMeasurer.
• Implement an algorithm to compute the pathwidth of a graph. Add a static method to GraphMeasurer. This also requires to implement a path decomposition (add implementation to decomposition package).

Community detection

• Implement Louvain Modularity
• Implement the Girvan–Newman algorithm
• Consider adding alternative community detection algorithms: https://en.wikipedia.org/wiki/Community_structure
• Implement an algorithm to detect k-truss and max-truss in a graph. Note: several fast, scalable algorithms exist to solve this problem for large graphs.

Decompositions

• Implement Modular Decomposition

Trees

• Implement Lengauer-Tarjan dominator tree algorithm: Thomas Lengauer and Robert Endre Tarjan: A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Language and Systems, 1(1):121-141, 1979.

Graph Tests

Several graph tests are still missing, including, but not limited to:

• GraphTests.isPerfect, GraphTests.isWeaklyPerfect, GraphTests.isStronglyPerfect. See http://mathworld.wolfram.com/PerfectGraph.html
• GraphTests.isMedian. See https://en.wikipedia.org/wiki/Median_graph
• GraphTests.isOuterPlanar See https://en.wikipedia.org/wiki/Planar_graph#Outerplanar_graphs
• GraphTests.isMaximalPlanar See https://en.wikipedia.org/wiki/Planar_graph#Maximal_planar_graphs. A maximal planar graph is sometimes also called a Triangulated Graph (http://mathworld.wolfram.com/TriangulatedGraph.html), so perhaps a isTriangulated method would make sense. Notice that the term 'triangulated' also occurs in the context of chords. It needs to be verified (and clarified) what the relation is, to avoid any sort of confusion (see note number 2 in this wiki article https://en.wikipedia.org/wiki/Chordal_graph).
• GraphTests.isKConnected (see connectivity topic above)
• GraphTests.isLineGraph (see line graph topic above)
• GraphTests.isChordlessGraphsee http://mathworld.wolfram.com/ChordlessGraph.html. Related to this are algorithms which detect chordless cycles in the graph.