Documentation ¶
Overview ¶
Package vpbruijn implements De Bruijn graphs. See https://en.wikipedia.org/wiki/De_Bruijn_graph for theory about these graphs, this package has been initially written with the purpose of implementing the Koorde https://en.wikipedia.org/wiki/Koorde peer to peer network algorithm.
Index ¶
Constants ¶
const ( // GenericMinM is the minimum value for M (AKA base) // supported by the generic Bruijn implementation. GenericMinM = 2 // GenericMinN is the minimum value for N (number of elems) // supported by the generic Bruijn implementation. GenericMinN = 2 // GenericMaxM is the maximum value for M (AKA base) // supported by the generic Bruijn implementation. GenericMaxM = 100 // GenericMaxN is the maximum value for N (number of elems) // supported by the generic Bruijn implementation. GenericMaxN = 1000 )
const PackageCopyright = "Copyright (C) 2015, 2016 Christian Mauduit <ufoot@ufoot.org>" // PackageCopyright set by version.sh
PackageCopyright contains a short copyright notice.
const PackageEmail = "ufoot@ufoot.org" // PackageEmail set by version.sh
PackageEmail contains a contact email for the package.
const PackageLicense = "GNU GPL v3" // PackageLicense set by version.sh
PackageLicense contains a short license information.
const PackageName = "Vapor Toolkit" // PackageName set by version.sh
PackageName contains a readable name of the package, suitable for display.
const PackageTarname = "vapor" // PackageTarname set by version.sh
PackageTarname contains a short name of the package, suitable for a filename.
const PackageURL = "https://github.com/ufoot/vapor" // PackageURL set by version.sh
PackageURL contains the address of the project homepage.
const VersionMajor = 0 // VersionMajor set by version.sh
VersionMajor is the project major version.
const VersionMinor = 4 // VersionMinor set by version.sh
VersionMinor is the project minor version.
const VersionStamp = "c6a4298" // VersionStamp set by version.sh
VersionStamp is the project stamp, possibly changes for each build.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BruijnWalker ¶
type BruijnWalker interface { // M returns the m paramater (AKA base) for the Bruijn network. M() int // N returns the m paramater (number of elements) for the Bruijn network. N() int // NbBits returns the number of bits of keys for this Bruijn network. NbBits() int // NbBytes returns the number of bytes of keys for this Bruijn network. NbBytes() int // NextFirst returns the first Bruijn node pointed by this node. // Other nodes might be deduced by just incrementing this one. NextFirst(key []byte) []byte // NextLast returns the last Bruijn node pointing to this node. // Other nodes might be deduced by just decrementing this one with // a value of m**(n-1). NextLast(key []byte) []byte // NextList returns the list of all Bruijn nodes pointed by // this node, the nodes following this one (we walk down the graph). NextList(key []byte) [][]byte // PrevFirst returns the first Bruijn node pointing to this node. // Other nodes might be deduced by just incrementing this one with // a value of m**(n-1). PrevFirst(key []byte) []byte // PrevLast returns the last Bruijn node pointing to this node. // Other nodes might be deduced by just decrementing this one with // a value of m**(n-1). PrevLast(key []byte) []byte // PrevList returns the list of all Bruijn nodes pointing to // this node, the nodes preceding this one (we walk up the graph). PrevList(key []byte) [][]byte // ForwardPath returns the path between two nodes. The path // might be non-optimized, it always contains m+1 elements, including // from and to destination. This is the default forward path in which // node n+1 is the node after n in the bruijn sequence. ForwardPath(from, to []byte) [][]byte // BackwardPath returns the path between two nodes. The path // might be non-optimized, it always contains m+1 elements, including // from and to destination. This is the alternative backward path in which // node n+1 is the node before n in the bruijn sequence. BackwardPath(from, to []byte) [][]byte // ForwardElem returns the path element between two nodes. // Index 0 is the from element, and n (number of elements as in Bruijn nodes) // the to element. Uses the forward, default path. ForwardElem(from, to []byte, i int) []byte // BackwardElem returns the path element between two nodes. // Index 0 is the from element, and n (number of elements as in Bruijn nodes) // the to element. Uses the backward, alternative path. BackwardElem(from, to []byte, i int) []byte // Filter a key, typically doing a modulo on it, making sure the result // is within the allowed key range. This is not a hash, but it could typically // be called with a hash value, the hast having a greater range than the key // ring used. Filter(x []byte) []byte // Rand returns a random valid key. Rand(r *rand.Rand) []byte // Zero returns the zero key. Zero() []byte // Add 2 keys, if result is too big, will loop with Mod() and keep it // within the allowed key range. Add(x, y []byte) []byte // Sub substracts a key from another, if result is too small, will loop with // Mod() and keep it within the allowed key range. Sub(x, y []byte) []byte // Cmp compares two keys, returns 1 is y>x, -1 if x<y and 0 if they are equal. // It considers values reprensent keys on a ring, so if y is really greater // than x (that is, more than half-way considering the lenght of the ring) then // y is considered smaller than x. So one can have a>b and b>c and c>a. Cmp(x, y []byte) int // GeLt tells wether a key is between two other keys. It considers keys are // on a ring so if begin is before end, tests x>=begin and x<end, and if // end is before begin, tests x<end or x>=begin. GeLt(x, begin, end []byte) bool // GtLe tells wether a key is between two other keys. It considers keys are // on a ring so if begin is before end, tests x>begin and x<=end, and if // end is before begin, tests x<=end or x>begin. GtLe(x, begin, end []byte) bool // Incr increments the key by 1. If it's too great to fit within key space, // then returns 0. Incr(x []byte) []byte // Decr decreases the key by 1. If it's below 0, then set it to the greatest // possible key value. Decr(x []byte) []byte // RingPos returns the position on the ring between 0 and 1, this is typically // interesting in a Koorde context, mostly for debugging/reporting purposes. RingPos(x []byte) float64 // RingRange returns the range which x to y represents on the ring. The result // is between 0 and 1. RingRange(x, y []byte) float64 // BytesToIntArray converts from the compact bytes format to a more readable // int array structure, with N different elements. BytesToIntArray(x []byte) []int // BytesToIntArray converts from the more readable int array structure, // with N different elements, to the compact bytes format. IntArrayToBytes(x []int) []byte }
BruijnWalker allows walking along a Bruijn graph, going forward, backward, getting list of previous or next nodes.
func Bruijn16x64New ¶
func Bruijn16x64New() BruijnWalker
Bruijn16x64New creates a new Bruijn object capable of walking Bruijn graphcs wih m (AKA base) =16 and n (number of elems) =64. This is a specific, hopefully optimized for this case, implementation.
func BruijnGenericNew ¶
func BruijnGenericNew(m, n int) BruijnWalker
BruijnGenericNew creates a new Bruijn object capable of walking Bruijn graphcs with arbitrary m an n numbers. If m and n are outside allowed values, they will be increased/decreased to that they fit. This is a generic implementation, can be used for real usage or as a reference for optimized version. It can theorically be slower than optimized 2^n as it relies on a general purpose big integer machinery, in practice it shows decent results.
func BruijnNew ¶
func BruijnNew(m, n int) (BruijnWalker, error)
BruijnNew creates a new BruijnWalker compatible object, which can be use to walk along De Bruijn networks.