Repository files navigation

Simple graphs is a Java library containing basic graph data structures and algorithms. It is lightweight, fast, and intuitive to use.

It has two types of graph data structures representing undirected and directed graphs. Each of these provides methods for adding and removing vertices and edges, for retrieving edges, and for accessing collections of its vertices and edges. All graphs in simple graphs are weighted and (of course) simple.

Algorithms implemented are:

• breadth first search
• depth first search
• shortest path using theA* search algorithm (Dijkstra's algorithm when no heuristic is provided)
• cycle detection
• topological sort for directed graphs (performed in-place)
• minimum weight spanning tree for undirected graphs usingKruskal's algorithm

Simple graphs uses Java 8 and Java Collections. It has no dependencies, and is GWT compatible. It usesfloat for floating point values, so should be a little more compatible with libraries that use floats, such aslibgdx.

If you're looking for a broader, more powerful library and don't care about Java 8, GWT, or including a lot of extra dependencies, I'd recommendJGraphT. It essentially does everything this library does, plus a lot more (though it's not really "simple").

To include Simple Graphs in your project, follow the instructions on thejitpack website.

If you use GWT, your .gwt.xml file should inherit simple-graphs using:

<inheritsname="simple_graphs" />

Usage looks something like:

Graph<Integer>graph =newUndirectedGraph<>();// or new DirectedGraph<>();for (inti =0;i <5;i++) {graph.addVertex(i);}booleancontainsVertex =graph.contains(0);graph.addEdge(1,2);booleancontainsEdge =graph.edgeExists(1,2)

Edge weights can be assigned a fixed float value, or can be dynamically calculated via aWeightFunction.

// fixed valuegraph.addEdge(vertexA,vertexB,1.5f);graph.getEdge(vertexA,vertexB).setWeight(1.5f);graph.setDefaultEdgeWeight(1.5f);// weight functions (assuming vertex class implements a distance method dst())graph.addEdge(vertexA,vertexB, (a,b) ->a.dst(b));graph.getEdge(vertexA,vertexB).setWeight((a,b) ->a.dst(b));graph.setDefaultEdgeWeight((a,b) ->a.dst(b);

You can obtainCollection<V>s of the vertices and edges:

Collection<Integer>vertices =graph.getVertices();Collection<Edge<Integer>>edges =graph.getEdges();

Neither collection can be modified directly - they provide a "read-only" iterable view of the vertices and edges, and they are subject to the same restrictions as aCollection returned byCollections#unmodifiableCollection(). The iteration order is guaranteed to be consistent for both collections (default order is insertion order) and both are sortable, though you need to sort using the graph object and not directly on the collection. Something like:

graph.sortVertices((v1,v2) -> ...);

If you want to access elements by index, you need to convert to an array via thetoArray() methods or add them to aList via egnew ArrayList<>(graph.getVertices()).

To access algorithms, useGraph#algorithms(). You need to have a specific reference to a subclass ofGraph (DirectedGraph orUndirectedGraph) to access algorithms specific to that type of graph.

Vu,v;Graph<V>graph;UndirectedGraph<V>undirectedGraph;DirectedGraph<V>directedGraph;Path<V>path =graph.algorithms().findShortestPath(u,v);UndirectedGraph<V>tree =undirectedGraph.algorithms().findMinimumWeightSpanningTree();directedGraph.algorithms().topologicalSort();

Additionally, search algorithms allow a processing step at each step of the algorithm. These can be used for side effects (for example to construct another graph as the algorithm runs), or for deciding whether to skip processing that vertex or terminate the algorithm. For example:

graph.algorithms().breadthFirstSearch(u,step ->System.out.println("processing " +step.vertex()));Graph<Integer>tree =graph.createNew();graph.algorithms().depthFirstSearch(u,step -> {tree.addVertex(step.vertex());if (step.count() >0) {tree.addEdge(step.edge());    }if (step.depth() >4) {step.ignore();    }});

While vertices can be any type ofObject, care must be taken that they are immutable, in the sense that while in theGraph theirhashCode() method always returns the same value, andequals is consistent. In general, vertex objects are subject to the same requirements as keys in a javaMap.

See the wiki for more info.