Top 3.4% dependent packages on proxy.golang.org
Top 2.5% dependent repos on proxy.golang.org
proxy.golang.org : github.com/spakin/disjoint
Package disjoint implements a disjoint-set data structure. A disjoint-set—also called union-find—data structure keeps track of nonoverlapping partitions of a collection of data elements. Initially, each data element belongs to its own, singleton, set. The following operations can then be performed on these sets: • Union merges two sets into a single set containing the union of their elements. • Find returns an arbitrary element from a set. The critical feature is that Find returns the same element when given any element in a set. The implication is that two elements A and B belong to the same set if and only if A.Find() == B.Find(). Both Union and Find take as arguments elements of sets, not the sets themselves. Because sets are mutually disjoint, an element uniquely identifies a set. Ergo, there is no need to pass sets to those functions. Disjoint sets are more limited in functionality than conventional sets. They support only set union, not set intersection, set difference, or any other set operation. They don't allow an element to reside in more than one set. They don't even provide a way to enumerate the elements in a given set. What makes them useful, though, is that they're extremely fast, especially for large sets; both Union and Find run in amortized near-constant time. See http://en.wikipedia.org/wiki/Disjoint-set_data_structure for more information. Disjoint sets are often used in graph algorithms, for example to find a minimal spanning tree for a graph or to determine if adding a given edge to a graph would create a cycle. Draw a maze. This is my favorite use of disjoint-set forests. The algorithm works by repeatedly knocking down walls between two sets of rooms that are not part of the same union and merging those rooms into a single union. A union represents connected components—rooms in the maze that are mutually reachable. A single union implies that every room is reachable from every other room. This is a fairly long example, but note that only half of it relates to generating the maze. The other half renders the maze using Unicode box-drawing characters.
Registry
-
Source
- Documentation
- JSON
- codemeta.json
purl: pkg:golang/github.com/spakin/disjoint
License: BSD-3-Clause
Latest release: almost 2 years ago
First release: about 4 years ago
Namespace: github.com/spakin
Dependent packages: 3
Dependent repositories: 4
Stars: 9 on GitHub
Forks: 2 on GitHub
See more repository details: repos.ecosyste.ms
Last synced: 21 days ago