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
bin added basic unit tests 4 years ago
src added Topological Sorting 4 years ago
web added explainatory images of markov chain and FSM 4 years ago
.gitattributes :octocat: Added .gitattributes & .gitignore files 5 years ago
.travis.yml cahnged to gradlew 4 years ago

# GraphLib

Graphs in a .jar

## Build state ## Content

The library consists of three main parts

• Fully generic graph interface with one concrete Directed Graph class implemented using adjacency matrix.
• A GraphUtils class with common graph-algorithms such as:
• Usage examples

## 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>();
//Cost of the edges is defaulted to null
`````` Creating a graph and setting all edge costs to the sum of the nodes

``````Graph<Integer,Integer> graph = new Graph<Integer, Integer>();
//Cost of the edges is defaulted to null
graph.forEachEdge((a,b) -> a+b);
`````` #### 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>();
{
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.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. #### 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.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. #### State-searching

An example would be if you want to use the `GraphUtils`for 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. 