Documentation
¶
Index ¶
- Constants
- type DoubleButterfly
- type Graph
- func ConstructDoubleButterfly(id int, g, l int64) *Graph
- func ConstructLinearSuperConcentrator(id int, n, k, d int64, localize bool) *Graph
- func ConstructStackedExpanders(id int, n, k, d int64, localize bool) *Graph
- func DefaultDoubleButterfly(id int) *Graph
- func DefaultLinearSuperConcentrator(id int) *Graph
- func DefaultStackedExpanders(id int) *Graph
- func NewGraph(id int, size int64, _type string) *Graph
- type GraphType
- type LinearSuperConcentrator
- type Node
- type Nodelist
- type StackedExpanders
Constants ¶
const ( // Graph types DOUBLE_BUTTERFLY = "double_butterfly" LINEAR_SUPER_CONCENTRATOR = "linear_super_concentrator" STACKED_EXPANDERS = "stacked_expanders" )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DoubleButterfly ¶
type DoubleButterfly struct {
*Graph
}
func (*DoubleButterfly) IsGraphType ¶
func (_ *DoubleButterfly) IsGraphType() string
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
func ConstructDoubleButterfly ¶
Double Butterfly graph
func DefaultDoubleButterfly ¶
func DefaultStackedExpanders ¶
func (*Graph) GetParents ¶
type LinearSuperConcentrator ¶
type LinearSuperConcentrator struct {
*Graph
}
func (*LinearSuperConcentrator) Concentrator ¶
func (sup *LinearSuperConcentrator) Concentrator(m, n, d int64, localize, reverse bool)
A left expander output will have d incoming edges from inputs and one incoming edge from a leftover node in the concentrator. A right expander output will have d incoming edges from inputs and one incoming edge from the perfect matching..
func (*LinearSuperConcentrator) IsGraphType ¶
func (_ *LinearSuperConcentrator) IsGraphType() string
func (*LinearSuperConcentrator) PinskerExpander ¶
func (sup *LinearSuperConcentrator) PinskerExpander(m, n, d int64, localize bool)
Bipartite Expander
type Node ¶
type Node struct {
Idx int64 `json:"idx"`
Parents Int64s `json:"parents"`
Value []byte `json:"value"`
}
func (*Node) MarshalBinary ¶
func (*Node) UnmarshalBinary ¶
type StackedExpanders ¶
type StackedExpanders struct {
*Graph
}
func (*StackedExpanders) ChungExpander ¶
func (stacked *StackedExpanders) ChungExpander(m, n, d int64)
This implements Chung's randomized construction of a bipartite expander Each source has d outgoing edges and each sink has d incoming edges. We establish a one-to-one matching between sources and sinks by iterating through the sources and randomly selecting a sink for each. If the chosen sink already has a parent, we search outwards until we find an available sink. Once we have the random permutation, we add d-1 more incoming edges to each sink. These edges come from the d-1 sources immediately after the matching source (we loop around if we reach m+2*n) TODO: add localization transformation TODO: more explicit panic messages
func (*StackedExpanders) IsGraphType ¶
func (_ *StackedExpanders) IsGraphType() string
func (*StackedExpanders) PinskerExpander ¶
func (stacked *StackedExpanders) PinskerExpander(m, n, d int64, localize bool)
This implements Pinsker's randomized construction of a bipartite expander. We iterate through the sinks and randomly choose d predecessors for each. The localization transformation works as follows... each edge from source i to sink j where (i mod n) < (j mod n) is replaced by an edge from sink k to sink j where (i mod n) == (k mod n). After the randomized construction, any edge from source i to sink j where (i mod n) == (j mod n) that does not already exist is added to the graph..
Source Files