Skip to content

Latest commit

 

History

History
225 lines (162 loc) · 5.52 KB

README.md

File metadata and controls

225 lines (162 loc) · 5.52 KB
Raw

Graphva

A graph implementation in Java

Graphs

  • Generic data types for edges and vertices
  • Directed, undirected graphs
  • Adjacency list or matrix graph implementations
  • Labeled edges and vertices with degrees
  • Iteratable iterators
  • Formatters (stdout or custom)
  • In/out vertex degrees

Heaps

  • Dynamic array based heap implementation

Trees

  • Disjointed sets
  • Minimum spanning tree

Algorithms

  • Breadth first search
  • Depth first search
  • Dijkstra search
  • Permutations
  • Topological sort
  • Kruskals minimum spanning tree
  • Prims minimum spanning tree

Graphs

Graph edges (connections) and Vertices (points) must implement Comparable.

Adjacency List and Matrix implementations

Implementations for Integer edges and String vertices:

// Create implementations for a graph with Integer edges and String vertices
Graphable<Integer,String> listImpl = new AdjacencyList<>()
Graphable<Integer,String> matrixImpl = new AdjacencyMatrix<>()

Examples

boolean directed = false;

Graph<Integer,String> graph = Graph<>(impl, directed);

// add a list of vertices
graph.addVertices("Hello", "World", "Robot", "Unnecessary", "Point");

// add an edge of value 1 between the World and Robot vertices
graph.addEdge("World", "Robot", 1);

// add and edge of value 2 between the Hello and Point vertices
graph.addEdge("Hello", "Point", 2);

Iterating

// iterate all vertices
Iterable<String> it = graph.vertices();

// or iterate adjacent vertices to Robot
for (String vertex : graph.adjacent("Robot")) {
  System.out.println(vertex);
}

// iterate all edges
Iterable<Edge<Integer,String>> it = graph.edges();

// iterate edges for the Robot vertex
for (Edge<Integer,String>> edge : graph.edges("Robot")) {
  System.out.println(edge);
}

Searching

Breadth or Depth first:

// Store the results as a list, could be a custom callback
List<String> result = new ArrayList<>();

// breadth first from Robot vertex
graph.bfs("Robot", result::add)

// depth first from Hello vertex (pre, post, reversePost)
graph.dfs("Hello", result::add, Ordering.Pre)

Dijkstra path:

// Store the result as a list, could be a custom callback
List<String> result = new ArrayList<>();

// Create the search for the graph
Dijkstra<Integer> path = new Dijkstra<>(graph, actual::add);

// start search from World vertex
path.search("World")

Topological sort:

TopologicalSort<Integer, String> sorter = new TopologicalSort<>(graph);

Collection<String> sorted = sorter.sort();

Default formatters

// print as a symbol matrix
System.out.println(graph.toString(new SymbolFormatter<>(graph)));

/*
 * OUTPUT:
 *             │ Hello       World       Robot       Unnecessary Point       
 * ────────────┼─────────────────────────────────────────────────────────────
 * Hello       │ ○           ○           ○           ○           ●           
 * World       │ ○           ○           ●           ○           ○           
 * Robot       │ ○           ●           ○           ○           ○           
 * Unnecessary │ ○           ○           ○           ○           ○           
 * Point       │ ●           ○           ○           ○           ○           
 *
 */
// print as a edge label matrix
System.out.println(graph.toString(new LabelFormatter<>(graph)));

/*
 * OUTPUT:
 *             │ Hello       World       Robot       Unnecessary Point       
 * ────────────┼─────────────────────────────────────────────────────────────
 * Hello       │ ○           ○           ○           ○           2           
 * World       │ ○           ○           1           ○           ○           
 * Robot       │ ○           1           ○           ○           ○           
 * Unnecessary │ ○           ○           ○           ○           ○           
 * Point       │ 2           ○           ○           ○           ○           
 *
 */

Other

Trees

A disjointed set used to implement minimum spanning tree implementations.

MinimumSpanningTree<Integer, String> kruskal = new MinimumSpanningTree.Kruskals<>(graph);

for (Edge<Integer,String> result : kruskal.find()) {
  System.out.println(result);
}

MinimumSpanningTree<Integer, String> prims = new MinimumSpanningTree.Prims<>(graph);

Iterable<> it = prims.find();

Heaps

// create a max heap with capacity of 5
// could also be a MinHeap<>(5) for reverse order output

Heap<Integer> heap = new MaxHeap<>(5);

// offer values to the heap
assert heap.offer(3);
assert heap.offer(8);
assert heap.offer(1);
assert heap.offer(4);
assert heap.offer(10);

// we've reach capacity and this value is not greater than the top
assert !heap.offer(7);

// however this value is greater
assert heap.offer(13);

for (Integer i : heap) {
  System.out.println(i);
}

while (!heap.isEmpty()) {
	System.out.println(heap.remove());
}

/*
 * OUTPUT:
 * 13
 * 10
 * 8
 * 4
 * 3
 */

Setup

use maven or import maven project

  • mvn test: run unit tests
  • mvn package: to build jar
  • mvn compile: to compile