Class Orient3Hypergraph


  • public class Orient3Hypergraph
    extends java.lang.Object
    Commodity class implementing the selfless algorithm for the orientation of a 3-hypergraph. The algorithm has been described by Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink in “Tight thresholds for cuckoo hashing via XORSAT”, Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 6198, pp. 213−225, Springer (2010).

    Note that the method orient() is tailored to the needs of Linear3SystemSolver.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static boolean orient​(int[][] edges, int[] d, int[] vertex0, int[] vertex1, int[] vertex2, int[] hinges)
      Orients the edges of a 3-hypergraph.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Method Detail

      • orient

        public static boolean orient​(int[][] edges,
                                     int[] d,
                                     int[] vertex0,
                                     int[] vertex1,
                                     int[] vertex2,
                                     int[] hinges)
        Orients the edges of a 3-hypergraph.
        Parameters:
        edges - the edge array (an array of vertices for each hyperedge).
        d - the degree array.
        vertex0 - the first vertex of each edge.
        vertex1 - the second vertex of each edge.
        vertex2 - the third vertex of each edge.
        hinges - the vector where hinges will be stored.
        Returns:
        true if direction was successful.