JGraphT—A Java Library for Graph Data Structures and Algorithms

DOI10.1145/3381449zbMATH Open1484.05003arXiv1904.08355OpenAlexW3027461786WikidataQ113309942 ScholiaQ113309942MaRDI QIDQ5132324FDOQ5132324

John V. Sichi, Barak Naveh, Dimitrios Michail, J. Kinable

Publication date: 10 November 2020

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Abstract: Mathematical software and graph-theoretical algorithmic packages to efficiently model, analyze and query graphs are crucial in an era where large-scale spatial, societal and economic network data are abundantly available. One such package is JGraphT, a programming library which contains very efficient and generic graph data-structures along with a large collection of state-of-the-art algorithms. The library is written in Java with stability, interoperability and performance in mind. A distinctive feature of this library is the ability to model vertices and edges as arbitrary objects, thereby permitting natural representations of many common networks including transportation, social and biological networks. Besides classic graph algorithms such as shortest-paths and spanning-tree algorithms, the library contains numerous advanced algorithms: graph and subgraph isomorphism; matching and flow problems; approximation algorithms for NP-hard problems such as independent set and TSP; and several more exotic algorithms such as Berge graph detection. Due to its versatility and generic design, JGraphT is currently used in large-scale commercial, non-commercial and academic research projects. In this work we describe in detail the design and underlying structure of the library, and discuss its most important features and algorithms. A computational study is conducted to evaluate the performance of JGraphT versus a number of similar libraries. Experiments on a large number of graphs over a variety of popular algorithms show that JGraphT is highly competitive with other established libraries such as NetworkX or the BGL.

Full work available at URL: https://arxiv.org/abs/1904.08355

zbMATH Keywords

graph theorynetwork analysisdata structuresalgorithmic library

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Data structures (68P05) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Cited In (12)

• An exact solution approach for the inventory routing problem with time windows
• HyperBench
• Formalization and implementation of credibility dynamics through prioritized multiple revision
• JGraphT
• OCSM: finding overlapping cohesive subgraphs with minimum degree
• Exact bidirectional algorithm for the least expected travel-time path problem on stochastic and time-dependent networks
• Title not available (Why is that?)
• Continuous-time formulations for multi-mode project scheduling
• Delay resistant line planning with a view towards passenger transfers
• Certificates for probabilistic pushdown automata via optimistic value iteration
• Solving the Watchman Route Problem with Heuristic Search
• Solving maximum weighted matching on large graphs with deep reinforcement learning

Uses Software

• LEDA
• Mathematica
• NetworkX
• SageMath
• ANTLR
• SNAP
• Cytoscape
• Boost
• Gephi
• JUNG
• BGL
• Gunrock
• Ligra
• GraphMat
• LAGraph
• GraphBLAST
• NetworKit

Recommendations

• JGAP: a Java-based graph algorithms platform 👍 👎
• Graph Transformations 👍 👎
• A Flexible and Easy-to-Use Library for the Rapid Development of Graph Tools in Java 👍 👎
• A Java Library of Graph Algorithms and Optimization 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: JGraphT—A Java Library for Graph Data Structures and Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5132324)