Graph Library

Java library containing basic graph algorithms. Fast and easy to use.

Usage

Usage is pretty pretty straightforward. Graph construction

Graph graph = new LinkedGraph(0); // or new MatrixGraph<>();

for (int i = 0; i < 10; i++) {
  for (int j = 0; j < 5; j++) {
    graph.addEdge(i, j, 1); // vertex, vertex, weight
  }
}

Remove Edge

graph.removeEdge(1, 2);

Graph size

int size = graph.size();

Edge count for whole graph, or particular vertex

int edges = graph.edgeCount();
int sevenEdges = graph.edgeCount(7);

Check weight, edge existance

boolean containsVertex = graph.hasEdge(1, 3);
int weight = graph.getWeight(1, 3);

Iterate over edges

Iterable<Edge> edges = graph.edges(3);

Algorithms

1. Traversal
   1. Breadth-first search
   2. Depth-first search
2. Sorting
   1. Topological sort
3. Path Finding
   1. Dijkstra's algorithm
   2. Floyd's algorithm
   3. Warshall's algorithm
4. Minimum Spanning Tree
   1. Prim's algorithm
5. Coloring
   1. Greedy Coloring algorithm
6. Detection
   1. Cycle Detection algorithm
   2. Connected Components algorithm
   3. Bridge Detection algorithm

Traversal

Breadth-first search

BFS algorithm recibes the graph to be traversed, starting vertex and a callback function to be executed on every node.

import algorithms.Traversal.BFS;

BFS.solve(g, 0, (arg) -> {
    System.out.println(arg);
});

Depth-first search

DFS algorithm recibes the graph to be traversed, starting vertex and a callback function to be executed on every node.

import algorithms.Traversal.DFS;

DFS.solve(g, 0, (arg) -> {
    System.out.println(arg);
});

Sorting

Topological Sort

Topological sort algorithm recibes a graph, and returns a sorted array representing one possible topological sort.

import algorithms.Sorting.TopoSort;

int[] result = TopoSort.solve(g);

PathFinding

Dijkstra's algorithm

Dijkstra's algorithm recibes a graph, starting index, and returns an array representing minimum travelling cost to every node.

import algorithms.PathFinding.Dijkstra;

int[] result = Dijkstra.solve(g, 0);

Floyd's algorithm

Floyd's algorithm recibes a graph and returns a matrix representing minimum travelling between every node.

import algorithms.PathFinding.Floyd;

int[][] result = Floyd.solve(g);

Warshall's algorithm

Warshall's algorithm recibes a graph and returns a matrix representing wether there is a path between nodes.

import algorithms.PathFinding.Warshall;

boolean[][] result = Warshall.solve(g);

Minimun Spanning Tree

Prim's algorithm

Prim's algorithm recibes a graph, and returns an array in which every node (position) contains its parent. Therefore MST can be constructed.

import algorithms.MST.Prim;

int[] result = Prim.solve(g);

Graph Coloring

Greedy Coloring algorithm

Greedy Coloring algorithm recibes an undirected graph, and returns an array in which every node (position) contains its corresponding color (represented as integer). Coloring makes no sense for directed graphs.

import algorithms.Coloring.GreedyColoring;

int[] result = GreedyColoring.solve(g);

Detection

Cycle Detection algorithm

Cycle Detection algorithm recibes a directed graph, and returns wether it contains a cycle.

import algorithms.Detection.CycleDetection;

boolean result = CycleDetection.solve(g);

Connected Components algorithm

Connected Components algorithm recibes a graph, and returns a list of connected components (Edge list)

import adt.Edge;
import algorithms.Detection.ConnectedComponents;

 List<List<Edge>> result = ConnectedComponents.solve(g);
 totalComponents = result.size();

Bridge Detection algorithm

Connected Components algorithm recibes a graph, and returns a list of bridges (Edge list). If graph is directed, algorithm solves strongly connected components problem.

import adt.Edge;
import algorithms.Detection.BridgeDetection;

List<Edge> result = BridgeDetection.solve(g);