Package org.mycore.tools

Class MCRTopologicalSort<T>

java.lang.Object
org.mycore.tools.MCRTopologicalSort<T>
public class MCRTopologicalSort<T> extends Object
This class implements an algorithm for topological ordering. It can be used to retrieve the order in which MyCoRe object can be imported to be sure that parent objects are imported first. It also checks for circular dependencies and will throw an exception if it occurs. The doTopoSort() method can only be called once, since it processes the internal data. Afterwards prepareData() must be called again or a new object has to be used. For performance reasons each node label will be mapped to an integer (position in node list) The algorithm is described in http://en.wikipedia.org/wiki/Topological_sorting
Version:
$Revision: 28688 $ $Date: 2013-12-18 15:27:20 +0100 (Mi, 18 Dez 2013) $
Author:
Robert Stephan

  • Constructor Details

    • MCRTopologicalSort

      public MCRTopologicalSort()

  • Method Details

    • prepareData

      public static void prepareData(MCRTopologicalSort<String> ts, String[] files, Path dir)
      parses MCRObject xml files for parent links and creates the graph uses StAX cursor API (higher performance)
      Parameters:
      ts - - the topological sort data structure
      files - - a list of file names
      dir - - the directory where the files can be found

    • prepareMCRObjects

      public static void prepareMCRObjects(MCRTopologicalSort<String> ts, String[] mcrids)
      reads MCRObjectIDs as Strings, retrieves parent links from MCRLinkTableManager and creates the graph uses StAX cursor API (higher performance)

    • reset

      public void reset()
      resets the topological sort data structure

    • getNodes

      public com.google.common.collect.BiMap<Integer,T> getNodes()
      return the Map of Integer to NodeObjects

    • addNode

      public void addNode(T name)
      add a node to the graph
      Parameters:
      name - - the node name

    • getNodeID

      public Integer getNodeID(T name)
      returns a node id for a given node
      Parameters:
      name - - the node name
      Returns:
      the node id

    • getNodeName

      public T getNodeName(Integer id)
      return the name of the given node
      Parameters:
      id - - the node id
      Returns:
      the node name

    • addEdge

      public void addEdge(Integer from, Integer to)
      add an edge to the graph
      Parameters:
      from - - the source node
      to - - the target node

    • removeEdge

      public boolean removeEdge(Integer from, Integer to)
      removes an edge from grapn
      Parameters:
      from - - the source node id
      to - - the target node id
      Returns:
      true, if there are no more incoming edges on the [to]-node ([to] = leaf node)

    • doTopoSort

      public int[] doTopoSort()
      based upon first pseudo code in http://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=611829125 The algorithm will destroy the input data -> the method can only be called once
      Returns:
      an array of ids which define the order in which the elements have to be retrieved from the given input list or null if an error occured

    • toString

      public String toString()
      Overrides:
      toString in class Object
      Returns:
      a string representation of the underlying graph