|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.sux4j.mph.HypergraphSorter<T>
public class HypergraphSorter<T>
A class implementing the 3-hypergraph edge sorting procedure that is necessary for the Majewski-Wormald-Havas-Czech technique.
Bohdan S. Majewski, Nicholas C. Wormald, George Havas, and Zbigniew J. Czech have
described in “A family of perfect hashing methods”,
Comput. J., 39(6):547−554, 1996,
a 3-hypergraph based technique to store functions
(actually, the paper uses the technique just to store a permutation of the key set, but
it is clear it can be used to store any function). More generally, the procedure sorts
the hyperedges of a random 3-hypergraph so that for each edge at least one vertex, the hinge, never
appeared before (this happens with positive probability if the number of vertices is at
least GAMMA
times the number of 3-hyperedges).
Instances of this class contain the data necessary to generate the random hypergraph
and apply the sorting procedure. At construction time, you provide just the desired number
of edges; then, each call to generateAndSort()
will generate a new 3-hypergraph using a 64-bit seed, an iterator returning the key set,
and a corresponding TransformationStrategy
. If the method returns true, the sorting was
successful and in the public field stack
you can retrieve the opposite
of the desired order (so enumerating edges starting from the last in stack
you
are guaranteed to find each time a vertex that never appeared before). The public fields
edge
, numEdges
and numVertices
expose the structure of the generated
3-hypergraph.
To guarantee the same results when reading a Majewski-Wormald-Havas-Czech-like structure,
the method bitVectorToEdge()
can be used to retrieve, starting from
a bit vector, the corresponding hyperedge. While having a function returning the edge starting
from a key would be more object-oriented and avoid hidden dependencies, it would also require
storing the transformation provided at construction time, which would make this class non-thread-safe.
Just be careful to transform the keys into bit vectors using
the same TransformationStrategy
used to generate the random 3-hypergraph.
We use Jenkin's hash in its 64-bit incarnation: beside providing an excellent hash function, it actually computes three 64-bit hash values, which is exactly what we need.
Building and sorting a large 3-hypergraph may take hours. As it happens with all probabilistic algorithms, one can just give estimates of the expected time.
There are two probabilistic sources of problems: duplicate hyperedges and non-acyclic hypergraphs. However, the probability of duplicate hyperedges is vanishing when n approaches infinity, and once the hypergraph has been generated, the stripping procedure succeeds in an expected number of trials that tends to 1 as n approaches infinity.
To help diagnosing problem with the generation process
class, this class will log at INFO
level
what's happening.
Note that if during the generation process the log warns more than once about duplicate hyperedges, you should suspect that there are duplicates in the string list, as duplicate hyperedges are extremely unlikely.
Field Summary | |
---|---|
int[][] |
edge
An 3×n array recording the triple of vertices involved in each hyperedge. |
static double |
GAMMA
The mythical threshold (or better, a reasonable upper bound of): random 3-hypergraphs are acyclic with positive probability if the ratio hyperedges/vertices exceeds this constant. |
int |
numEdges
The number of edges in the hypergraph. |
int |
numVertices
The number of vertices in the hypergraph ( ⌈ GAMMA * numEdges ⌉ + 1 ). |
int[] |
stack
The hyperedge stack. |
Constructor Summary | |
---|---|
HypergraphSorter(int numEdges)
Creates a hypergraph sorter for a given number of edges. |
Method Summary | |
---|---|
static void |
bitVectorToEdge(BitVector bv,
long seed,
int numVertices,
int[] e)
Turns a bit vector into a 3-hyperedge. |
boolean |
generateAndSort(java.util.Iterator<? extends T> iterator,
TransformationStrategy<? super T> transform,
long seed)
Generates a random 3-hypergraph and tries to sort its edges. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public static final double GAMMA
public final int numVertices
GAMMA
* numEdges
⌉ + 1 ).
public final int numEdges
public final int[][] edge
public final int[] stack
Constructor Detail |
---|
public HypergraphSorter(int numEdges)
numEdges
- the number of edges of this hypergraph sorter.Method Detail |
---|
public static void bitVectorToEdge(BitVector bv, long seed, int numVertices, int[] e)
This method will never return degenerate edge.
bv
- a bit vector.seed
- the seed for the hash function.numVertices
- the number of vertices in the underlying hypergraph.e
- an array to store the resulting hyperedge.public boolean generateAndSort(java.util.Iterator<? extends T> iterator, TransformationStrategy<? super T> transform, long seed)
iterator
- an iterator returning numEdges
keys.transform
- a transformation from keys to bit vectors.seed
- a 64-bit random seed.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |