Graph theory in a .jar
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
sciion 9ed274dc4e Update README.md 4 years ago
.settings added gradle build support 4 years ago
bin added basic unit tests 4 years ago
gradle/wrapper reverted to gradle 4 years ago
src added Topological Sorting 4 years ago
web added explainatory images of markov chain and FSM 4 years ago
.classpath added gradle build support 4 years ago
.gitattributes :octocat: Added .gitattributes & .gitignore files 5 years ago
.gitignore added gradle build support 4 years ago
.project added gradle build support 4 years ago
.travis.yml cahnged to gradlew 4 years ago
README.md Update README.md 4 years ago
build.gradle added basic unit tests 4 years ago
gradlew added gradle build support 4 years ago
gradlew.bat added gradle build support 4 years ago
settings.gradle added gradle build support 4 years ago

README.md

GraphLib

Graphs in a .jar

Work in progress


Index


Build state

Build Status

Content

The library consists of three main parts


Examples

Creating a graph with Integer as Nodes and Double for Edges and adding some nodes and edges.

Graph<Integer,Double> graph = new Graph<Integer, Double>();
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(4);
graph.addNode(5);
//Cost of the edges is defaulted to null
graph.addEdge(1,2);
graph.addEdge(1,3);
graph.addEdge(1,5);
graph.addEdge(2,4);
graph.addEdge(3,4);

Example

Creating a graph and setting all edge costs to the sum of the nodes

Graph<Integer,Integer> graph = new Graph<Integer, Integer>();
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(10);
//Cost of the edges is defaulted to null
graph.addEdge(1,2);
graph.addEdge(1,3);
graph.addEdge(3,2);
graph.addEdge(2,10);
graph.forEachEdge((a,b) -> a+b);

Example

Proppagation Graph

Many scenarios involves topologies with a fixed set of states but with dynamic edges. This can be represented using the PropagationGraph class.

What sets the PropagationGraph apart from the standrad Graph datastructure is that PropagationGraph allow for event listeners on modification of the graph structure. Both for nodes and edges.

PropagationGraph<Integer, Integer> graph = new PropagationGraph<Integer, Integer>();
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addEdge(1, 2, 0);
graph.addEdge(2, 3, 0);
graph.addEdge(3, 1, 0);
graph.addEdgeListener((a,b,e,c) -> 
   {
	    if (c == GraphChanges.CHANGE)
	      System.out.println("The values of edges " + a +"->" + b + " changed to " + e);
	});
graph.setEdgeValue(1,2,10);

Finite State Machine

The library contains a wrapper class around a Finite State Machine (FSM). The Finite State Machine uses a wrapper class (FSM) around the Graph data structure to limit the functionality of the Graph data structure to the constraints of a Finite State Machine.

The following code exemplifies how the FSM wrapper class can be used.

FSM<Integer,Integer> fsm = new FSM<Integer,Integer>();
fsm.addState(1);
fsm.addState(2);
fsm.addState(3);
fsm.addTransition(1,2,1);
fsm.addTransition(1,1,0);
fsm.addTransition(2,3,1);
fsm.addTransition(2,2,0);
fsm.addTransition(3,1,1);
fsm.addTransition(3,3,0);
fsm.setCurrentState(1);

To run the FSM you only need to present an input-sequence and a loop.

String sequence = "0110001111";
for(int i = 0; i < sequence.length(); i++)
	fsm.register(sequence.charAt(i) - '0');

The following image represents the FSM from the example above.

Example

Markov chain

The library also contains a wrapper class around the model of a Markov chain.

Example of how the MarkovChain wrapper class can be used

MarkovChain<String> mc = new MarkovChain<String>();
mc.addState("Sunny");
mc.addState("Rainy");
mc.addTransition("Sunny","Rainy",0.1);
mc.addTransition("Sunny","Sunny",0.9);
mc.addTransition("Rainy","Sunny",0.5);
mc.addTransition("Rainy","Rainy",0.5);
mc.setCurrentState("Sunny");
for(int i = 0; i <100; i++){
    mc.register();
   System.out.println(mc.getCurrentState());
}

The example will produce the following Markov chain and print the result of 100 iterations of the model. Example

State-searching

An example would be if you want to use the GraphUtilsfor searching in a state graph like n-puzzle solving, you would need to implement everything in AbstractGraph even thought A* only needs a Comparator<State> and the .getNeighbors().

What the example looks like using Hamming Distance.

Example


Javadocs

Javadocs can be found in the repository