README
¶
An implementation of A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems (2018) by Markus Leitner, Ivana Ljubić, Martin Luipersbeck, Markus Sinnl.
Documentation
¶
Overview ¶
Very closely resembles the content of https://golang.org/pkg/container/heap/#example__priorityQueue Why am i copy-pasting parts of the documentation you ask? Well, this is the idiomatic way of doing it. Thanks for reading my rant.
An implementation of the algorithm described in "A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems" by Leitner et al.
Index ¶
Constants ¶
const ValueMax = Value(math.MaxFloat64)
ValueMax is the maximal value for Value
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Graph ¶
type Graph struct {
// Edges
Arcs int // The number of edges in the graph
Cost []Value // The cost for including the given edge
Src []int // The source vertex id for the edge
Dst []int // The dst vertex id for the edge
// Vertices
Root int // The vertex (the id) of the root of the solution tree
Nodes int // The number of vertices
Prize []Value // The reward for including the given vertex in the tree.
Fixed []bool // True if the given vertex must be part of the solution
Terminal []bool // The Prize is positive or Fixed is true
Incoming [][]int // For a given vertex, the list of incoming edge ids
Outgoing [][]int // For a given vertex, the list of outgoing edge ids
}
Graph represents the problem statement.
type Item ¶
type Item struct {
// contains filtered or unexported fields
}
An Item is something we manage in a priority queue.
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
A PriorityQueue implements heap.Interface and holds Items. Returns lowest priorirty first.
func (*PriorityQueue) Len ¶
func (pq *PriorityQueue) Len() int
func (*PriorityQueue) Pop ¶
func (pq *PriorityQueue) Pop() *Item
func (*PriorityQueue) Push ¶
func (pq *PriorityQueue) Push(x *Item)
Source Files