modular and modern graph-theory algorithms framework in Java

Overview

Erdos is a very light, modular and super easy to use modern Graph theoretic algorithms framework for Java. It contains graph algorithms that you can apply swiftly with one line of code and was primarily developed to back a worker manager tasks for various Java projects including one in Android.

Erdos was born because other frameworks in Java were very hard to get started with or just plain heavy (overhead wise) or just too opinionated. Erdos let the developer design it's own graph engines to optimise the runtime and comes with all of the graph algorithms you can expect.

Build status Release

How to use

Option 1: Jitpack

Add Jitpack in your root build.gradle at the end of repositories:

allprojects {
    repositories {
        ...
        maven { url "https://jitpack.io" }
    }
}

Add to your dependencies:

dependencies {
    compile 'com.github.Erdos-Graph-Framework:Erdos:v1.0'
    // or the following for the current master snapshot
    // compile 'com.github.Erdos-Graph-Framework:Erdos:master-SNAPSHOT'
}

Option 2: Simply fork or download the project, you can also download and create .jar file yourself, with

git clone https://github.com/Erdos-Graph-Framework/Erdos.git erdos
cd erdos
./gradlew build
ls -l build/libs

Option 3: grab the latest released jar

https://github.com/Erdos-Graph-Framework/Erdos/releases

Notable technical features

  • compatible with Java 7
  • compose your graph by features and engine. modular design.
  • production proved code. Used in a commercial project.

Supported graphs

  • simple graph, directed and undirected
  • multi edge graph, directed and undirected
  • pseudo graph
  • custom graph, configure by self-loops, multi-edges and a graph engine.

builtin algorithms

Erdos is a framework to easily help you design graph algorithms with the correct abstractions and utilities. The builtin algorithms are:

builtin graph engines

  • Adjacency and Incidence list based graph engine
    designed for optimal complexity for algorithms that require more than a moderate edge queries.
  • in the future, a adjacency matrix engine will be added. That will be good to certain types of graphs, where queries are small, and memory should be kept as small as possible.
  • you can add your own graph engine by implementing AbstractGraphEngine.

Instructions, code by examples

1. creating a very simple graph

SimpleDirectedGraph graph_triangle = new SimpleDirectedGraph();

Vertex v0 = new Vertex();
Vertex v1 = new Vertex();
Vertex v2 = new Vertex("tag_v2");

graph_triangle.addVertex(v0);
graph_triangle.addVertex(v1);
graph_triangle.addVertex(v2);

Edge e_0 = graph_triangle.addEdge(v0, v1);
graph_triangle.addEdge(v1, v2);
graph_triangle.addEdge(v2, v3);

graph_triangle.print();

// iterate the graph vertices directly
for (IVertex vertex : graph_triangle) {
    System.out.println(vertex.toString());
}

// iterate the edges of the graph
for (Edge edge : graph_triangle.edges()) {
    System.out.println(edge.toString());
}

// removing a vertex in any of the following ways will remove it's connected edges as well,
// also removing any edge in similar fashion will update the graph :)
graph_triangle.removeVertex(v0);
graph_triangle.vertices().remove(v1);
graph_triangle.vertices().iterator().remove();

2. use a factory for custom graph

you can define your graph in terms of self loops, multi edges (per vertex) and a custom implementation of a graph engine.

boolean allow_self_loops = true;
boolean allow_multi_edges = true;

UndirectedGraph graph_undirected = Erdos.newUndirectedGraphWithEngine(new AdjIncidenceGraphEngine(), 
                                                                      allow_self_loops, allow_multi_edges);

DirectedGraph graph = Erdos.newGraphWithEngine(new AdjIncidenceGraphEngine(), 
                                               Edge.EDGE_DIRECTION.DIRECTED,
                                               allow_self_loops, allow_multi_edges);

3. algorithms introduction

every algorithm extends AbstractGraphAlgorithm<T, E extends IGraph>, which is generically typed E for input graph and T for output and must implement

  • T applyAlgorithm() method

for example, the Bellman-Ford algorithm for single source shortest path, followed by the Floyd-Warshall algorithm for all pairs shortest paths.

private void BellmanFord()
{
    SimpleDirectedGraph graph = new SimpleDirectedGraph();

    Vertex s = new Vertex("s");
    Vertex t = new Vertex("t");
    Vertex x = new Vertex("x");
    Vertex y = new Vertex("y");
    Vertex z = new Vertex("z");

    graph.addVertex(s);
    graph.addVertex(t);
    graph.addVertex(x);
    graph.addVertex(y);
    graph.addVertex(z);

    graph.addEdge(s, t, 6);
    graph.addEdge(t, x, 5);
    graph.addEdge(x, t, -2);
    graph.addEdge(s, y, 7);
    graph.addEdge(y, z, 9);
    graph.addEdge(t, y, 8);
    graph.addEdge(z, x, 7);
    graph.addEdge(t, z, -4);
    graph.addEdge(y, x, -3);
    graph.addEdge(z, s, 2);

    graph.setTag("graph");
    graph.print();

    // apply the Bellman-Ford algorithm
    ShortestPathsTree res = new BellmanFordShortestPath(graph).setStartVertex(s).applyAlgorithm();
    // print it
    res.print();
    // apply the Floyd-Warshall algorithm
    AllPairsShortPathResult floyd_result = new FloydWarshall(graph).applyAlgorithm();
    // print the shortest paths tree of the vertex
    floyd_result.shortestPathsTreeOf(s).print();
    // print the shortest path between two nodes
    System.out.println(floyd_result.shortestPathBetween(s, z).toString());
}

4. algorithms, more examples

this example shows the simplicity of the framework (hopefully ;)) where we apply 5 different algorithms sequentally

// perform a breadth first search
BFS.BreadthFirstTree breadthFirstTree = new BFS(graph, s).applyAlgorithm();
// perform a depth first search
DFS.DepthFirstForest depthFirstForest = new DFS(graph).applyAlgorithm();
// extract the strongly connected components of the graph
ArrayList<HashSet<IVertex>> hashSets = new SCC(graph).applyAlgorithm();
// perform a topological sort on the graph
LinkedList<IVertex> res_sort = new TopologicalSort(graph).applyAlgorithm();
// compute all pairs shortest paths using the Floyd-Warshall algorithm
AllPairsShortPathResult floyd_result = new FloydWarshall(graph).applyAlgorithm();

5. algorithms factories

for major algorithms types, you can comfortably use the following algorithms factories

  • MinSpanTreeFactory - for Minimum Spanning Tree/Forest, for example:
AbstractGraphAlgorithm<UndirectedGraph, IUndirectedGraph> alg = MinSpanTreeFactory.newMST(graph, MstAlgorithm.KRUSKAL, start_vertex);
AbstractGraphAlgorithm<UndirectedGraph, IUndirectedGraph> alg2 = MinSpanTreeFactory.newMST(graph, MstAlgorithm.PRIM, start_vertex);
  • SingleSourceShortPathFactory - for single source shortest path, for example:
AbstractShortestPathAlgorithm alg = SingleSourceShortPathFactory.newSingleSourceShortPath(graph, SSSPAlgorithm.DIJKSTRA, start_vertex, end_vertex);
  • AllPairsShortPathFactory - for shortest paths between all pairs, for example:
AbstractGraphAlgorithm<AllPairsShortPathResult, IDirectedGraph> alg2 = AllPairsShortPathFactory.newAllPairsShortPath(graph, APSPAlgorithm.Johnson);```

6. utilities

a bunch of helper utilities can be found in the package com.hendrix.erdos.utils

  • SVertexUtils.java - query vertex order information inside a graph
  • SEdgeUtils.java - query edge order information inside a graph
  • SMatrixUtils.java - compute the adjacency and incidence matrix of a graph
  • SGraphUtils.java - get a sorted list of the weighted edges in a graph

used in

  • Android-Zorn - for constructing a worker manager based on topological sorting in a graph.

Contributions

contributions are most welcomed, please consult CONTRIBUTING.md

what is the Erdős ?

homage to the great hungarian mathmatician Paul Erdős who part of his research was rooted in combinatorial graph theory.

License

If you like it -> star or share it with others

MIT License

Copyright (c) 2017 Tomer Shalev and Erdos (https://github.com/HendrixString)

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Contact Author

You might also like...

The modular web framework for Java and Kotlin

∞ do more, more easily Jooby is a modern, performant and easy to use web framework for Java and Kotlin built on top of your favorite web server. Java:

Dec 16, 2022

JUNG: Java Universal Network/Graph Framework

JUNG: The Java Universal Network/Graph Framework JUNG is a software library that provides a common and extensible language for the modeling, analysis,

Dec 28, 2022

A modular and portable open source XMPP client library written in Java for Android and Java (SE) VMs

Smack About Smack is an open source, highly modular, easy to use, XMPP client library written in Java for Java SE compatible JVMs and Android. A pure

Dec 28, 2022

[JAVA] Projeto exemplo de uma arquitetura modular em Java

[JAVA] Projeto exemplo de uma arquitetura modular em Java

Arquitetura modular O objetivo do bom design de software, como já diria Robert C. Martin, em seu livro 'Clean Architecture: A Craftsman's Guide to Sof

Dec 29, 2022

The Java collections framework provides a set of interfaces and classes to implement various data structures and algorithms.

The Java collections framework provides a set of interfaces and classes to implement various data structures and algorithms.

Homework #14 Table of Contents General Info Technologies Used Project Status Contact General Information Homework contains topics: Sorting an ArrayLis

Feb 12, 2022

Modular and customizable Material Design UI components for Android

Material Components for Android Material Components for Android (MDC-Android) help developers execute Material Design. Developed by a core team of eng

Jan 3, 2023

An extremely flexible yet vanilla-esque multiblock mod, that embraces aspects of MultiblockTweaker and Modular Machinery.

Multiblocked Multiblocked (mbd) is an extremely flexible yet vanilla-esque multiblock mod, that embraces aspects of MultiblockTweaker and Modular Mach

Jan 4, 2023

Genson a fast & modular Java Json library

Genson Genson is a complete json - java conversion library, providing full databinding, streaming and much more. Gensons main strengths? Easy to use

Jan 3, 2023

A modular, high performance, headless e-commerce(ecommerce) platform built with Java,Springboot, Vue.

A modular, high performance, headless e-commerce(ecommerce) platform built with Java,Springboot, Vue.

What is Shopfly? Shopfly is modular, high performance, headless e-commerce(ecommerce) platform built with Java,Springboot, Vue. Architecture Shopfly i

Jul 17, 2022

A modular, high performance, headless e-commerce(ecommerce) platform built with Java,Springboot, Vue.

What is Shopfly? Shopfly is modular, high performance, headless e-commerce(ecommerce) platform built with Java,Springboot, Vue. Architecture Shopfly i

Apr 25, 2022

A powerful 🚀 Android chart view / graph view library, supporting line- bar- pie- radar- bubble- and candlestick charts as well as scaling, panning and animations.

A powerful 🚀 Android chart view / graph view library, supporting line- bar- pie- radar- bubble- and candlestick charts as well as scaling, panning and animations.

⚡ A powerful & easy to use chart library for Android ⚡ Charts is the iOS version of this library Table of Contents Quick Start Gradle Maven Documentat

Jan 9, 2023

gMark: a domain- and query language-independent graph instance and query workload generator

gMark is a domain- and query language-independent graph instance and query workload generator.

Nov 19, 2022

An open source, modular alternative of sketchware. Create your own app in android using block programming like scratch!

An open source, modular alternative of sketchware. Create your own app in android using block programming like scratch!

OpenBlocks An open source, modular alternative of sketchware. Create your own app in android using block programming like scratch! What is OpenBlocks?

Dec 16, 2022

Modular Apache commons compress

Kala Compress This project is based on Apache Commons Compress. Kala Compress has made some improvements on its basis: Modularization (JPMS Support),

Feb 22, 2022

A modern testing and behavioural specification framework for Java 8

Introduction If you're a Java developer and you've seen the fluent, modern specification frameworks available in other programming languages such as s

Sep 12, 2022

Vaadin 6, 7, 8 is a Java framework for modern Java web applications.

Vaadin Framework Vaadin allows you to build modern web apps efficiently in plain Java, without touching low level web technologies. This repository co

Jan 5, 2023

A library for creating and editing graph-like diagrams in JavaFX.

A library for creating and editing graph-like diagrams in JavaFX.

Graph Editor A library for creating and editing graph-like diagrams in JavaFX. This project is a fork of tesis-dynaware/graph-editor 1.3.1, which is n

Jan 1, 2023
Comments
  • License query

    License query

    Hi Erdos-Graph-Framework team.

    I've noticed that the README says that Erdos is considered to be production proved code. Used in a commercial project.

    However, I've also noticed that Erdos is GPL-2.0 licensed. Is the commercial project mentioned in the README licensed under the GPL-2.0 as well?

    opened by jbduncan 6
  • FrequencyIterator doesn't decrease the frequency of current

    FrequencyIterator doesn't decrease the frequency of current

    By looking at the implementation I can see that current is never assigned, and when remove is called on the Iterator null is passed to decreaseFrequencyOf.

    opened by adam-arold 5
  • Publish to Maven Central

    Publish to Maven Central

    Hello. Huge fan of this framework so far!

    Just like the title says, I'm wondering if it's possible to publish this artifact on Maven Central or JCenter. I ask because my company currently has tight control over which repositories we're allowed to access.

    Thanks again for this project!

    opened by jjzazuet 1
  • Adding multiple vertices with the same data

    Adding multiple vertices with the same data

    Hello,

    Let's say I have a Vertex of the following form:

    Vertex<MyClass> myVertex = new Vertex<>(myObject.getMessage());

    In my program, it is possible for a Vertex with the same data to get graph.addVertex()'d. I want to be able to stop the graph from adding a Vertex if another one with the same data exists. I saw that the Vertex.hashCode is a function of some auto generated ID. If my data source is guaranteed to be unique elements, is it possible to make the hash a function of the data instead of a random ID ?

    Thanks for any advice.

    opened by Carpetfizz 4
Releases(v1.0)
Owner
Erdos
a modular graph theoretic algorithms framework for Java
Erdos
The foundational library of the Morpheus data science framework

Introduction The Morpheus library is designed to facilitate the development of high performance analytical software involving large datasets for both

Zavtech Systems 226 Dec 20, 2022
Java dataframe and visualization library

Tablesaw Overview Tablesaw is Java for data science. It includes a dataframe and a visualization library, as well as utilities for loading, transformi

Tablesaw 3.1k Jan 7, 2023
JGraphX - Library for visualizing (mainly Swing) and interacting with node-edge graphs.

JGraphX This project is end of life. We don't properly support Maven or publish to Maven Central. If that's an issue, use https://github.com/vlsi/jgra

JGraph 634 Jan 5, 2023
The Mines Java Toolkit

The Mines Java Toolkit The Mines Java Toolkit (Mines JTK) is a set of Java packages and native (non-Java) software libraries for science and engineeri

Mines Java Toolkit 57 Nov 19, 2022
A 3D chart library for Java applications (JavaFX, Swing or server-side).

Orson Charts (C)opyright 2013-2020, by Object Refinery Limited. All rights reserved. Version 2.0, 15 March 2020. Overview Orson Charts is a 3D chart l

David Gilbert 96 Sep 27, 2022
XChart is a light-weight Java library for plotting data.

XChart XChart is a light weight Java library for plotting data. Description XChart is a light-weight and convenient library for plotting data designed

Knowm 1.3k Dec 26, 2022
Graph Algorithms Repository for Coding Minutes Course.

graph-algorithms-for-competitive-coding Graph Algorithms Repository for Coding Minutes Course. This is the repository for Graph Algorithms Course for

Coding Minutes 126 Dec 28, 2022
Using ANTLR4 in the Course on Compiler Theory at software.nju.edu.cn

compilers-antlr Using ANTLR4 in the Course on Compiler Theory at software.nju.edu.cn src main antlr simpleexpr (gramma SimpleExpr) simpleexprlexer (le

null 8 Dec 14, 2022