Skip to content

Latest commit

 

History

History
60 lines (53 loc) · 2.26 KB

README.md

File metadata and controls

60 lines (53 loc) · 2.26 KB
Raw

Project summary

Java Implementation of the AHRSZ algorithm, for maintaining a topological order of a directed graph upon insertion of edges as described in

"A Dynamic Algorithm for Topologically Sorting Directed Acyclic Graphs" by David J. Pearce, Paul H. J. Kelly .

http://www.doc.ic.ac.uk/~phjk/Publications/DynamicTopoSortAlg-JEA-07.pdf

In contrast to the algorithm described in the paper, this implementation also deals with cycles. When a new edge is inserted that completes a cycle in the graph, then all edges composing the cycle are diminished by the weight of the minimum edge of the cycle. This way the cycle is removed. Note that this algorithm is not deterministic. A newly inserted edge may introduce multiple cycles at once. In this case it is up to the implementation to chose the order of removing the cycles. This may lead to different remaining graphs.

Prerequisites

  1. Git (for cloning this repository)
  2. mvn (for building)
  3. java 1.8 or higher (for running)

Usage

  1. clone this repository
  2. change directory into the new repository: cd AHRSZ
  3. install jar via maven : mvn install
  4. add the jar as a dependency to your project:
<dependency>
  <groupId>AHRSZ</groupId>
  <artifactId>AHRSZ</artifactId>
  <version>1.0-SNAPSHOT</version>
</dependency>
  1. Use it as in the test cases of this project:
    @Test
    public void testComplexGraph() throws InvalidExpansionStateException, InvalidAhrszStateException {
        AhrszAlgorithm<Character> ahrsz = new AhrszAlgorithm<>();
        ahrsz.addEdge('A','B',0.1f);
        ahrsz.addEdge('C','E',0.1f);
        ahrsz.addEdge('E','F',0.1f);
        ahrsz.addEdge('G', 'F', 0.1f);
        assertTrue(ahrsz.before('A', 'B'));
        assertTrue(ahrsz.before('C', 'E'));
        assertTrue(ahrsz.before('E', 'F'));
        assertTrue(ahrsz.before('G', 'F'));
        assertTrue(ahrsz.before('G', 'A'));
        ahrsz.addEdge('E', 'A', 0.1f);
        assertTrue(ahrsz.before('G', 'C'));
        assertTrue(ahrsz.before('C', 'E'));
        assertTrue(ahrsz.before('E', 'A'));
        assertTrue(ahrsz.before('A', 'B'));
        assertTrue(ahrsz.before('B', 'F'));
    }