Package de.uni_mannheim.informatik.dws.melt.matching_jena_matchers.structurelevel.hierarchical.agony

Class Agony<E>

java.lang.Object
de.uni_mannheim.informatik.dws.melt.matching_jena_matchers.structurelevel.hierarchical.agony.Agony<E>
Type Parameters:
E - Type of Node
public class Agony<E> extends Object
Class for computing hierarchy ranks in directed graphs (with cycles).This is an implementation of the paper:
Faster way to agony - Discovering hierarchies in directed graphs by Nikolaj Tatti
which is an improved version of the paper:
Hierarchies in directed networks by Nikolaj Tatti
Code is available at https://users.ics.aalto.fi/ntatti/software.shtml. This implementation has a similar runtime performance than the C++ code and is one to one translated. An evaluation can be found at https://github.com/zhenv5/breaking_cycles_in_noisy_hierarchies.

  • Field Details

    • LOGGER

      private static final org.slf4j.Logger LOGGER

    • nodes

      private final List<AgonyNode<E>> nodes

    • edges

      private final List<AgonyEdge> edges

    • graph

      private final AgonyGraph graph

    • dag

      private AgonyGraph dag

    • euler

      private AgonyGraph euler

    • dual

      private int dual

    • primal

      private int primal

    • slacks

      private List<Queue<AgonyEdge>> slacks

    • curslack

      private int curslack

    • SPLIT_PATTERN

      private static final Pattern SPLIT_PATTERN

  • Constructor Details

  • Method Details

    • readAdjacenyList

      public static Map<String,Set<String>> readAdjacenyList(File file)

    • readEdges

      public static List<Map.Entry<String,String>> readEdges(File file)

    • computeAgony

      public Map<E,Integer> computeAgony()
      Returns a mapping between each node and its corresponding rank (represented as integers). The rank starts at 0 and increases with each level.
      Returns:
      a mapping between each node and its corresponding rank

    • computeAgonyReverseMap

      public TreeMap<Integer,Set<E>> computeAgonyReverseMap()
      Returns a mapping between the different ranks/levels and corresponding nodes (of the graph) in these levels. This is just the reverese mapping of computeAgony().
      Returns:
      a mapping between the different ranks/levels and corresponding nodes

    • writeagony

      private Map<E,Integer> writeagony()

    • cycledfs

      private void cycledfs()

    • initagony

      private void initagony()

    • initrank

      private void initrank()

    • minagony

      private void minagony()

    • relief

      private void relief(int edge)

    • updaterelief

      private void updaterelief(List<AgonyNode<E>> nl)

    • shiftrank

      private void shiftrank(List<AgonyNode<E>> nl, int shift)

    • extractcycle

      private void extractcycle(int eid)

    • deleteslack

      private void deleteslack(int eid)

    • addslack

      private void addslack(int eid)

    • size

      private int size()

    • getNode

      private AgonyNode<E> getNode(int i)

    • getEdge

      private AgonyEdge getEdge(int i)

    • slack

      private int slack(AgonyNode<E> v, AgonyNode<E> u)

    • newslack

      private int newslack(AgonyNode<E> v, AgonyNode<E> u)

    • slack

      private int slack(int eid)

    • from

      private AgonyNode<E> from(int eid)

    • to

      private AgonyNode<E> to(int eid)