Documentation
¶
Index ¶
Constants ¶
const ApproximateSteinerTreeSupportedFeatures = graph.DeterministicIteration
ApproximateSteinerTreeSupportedFeatures are the graph features supported by the Steiner tree approximation algorithm.
const (
BellmanFordSupportedFeatures = graph.DeterministicIteration
)
const (
PrimMinimumSpanningTreeSupportedFeatures = graph.DeterministicIteration
)
const (
TiernanSimpleCyclesSupportedFeatures = graph.DeterministicIteration
)
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ApproximateSteinerTree ¶
type ApproximateSteinerTree struct {
// contains filtered or unexported fields
}
An ApproximateSteinerTree is an approximation of the Steiner tree of a graph G for a set of vertices Vr. A Steiner tree is a subset of G such that all Vr are present in the subset and the weights of the edges connecting Vr are minimized.
func ApproximateSteinerTreeOf ¶
func ApproximateSteinerTreeOf(g graph.UndirectedGraph, required []graph.Vertex) (*ApproximateSteinerTree, error)
ApproximateSteinerTreeOf computes an approximation of the Steiner tree for a given graph.
Steiner trees are known to be NP-complete, but an approximation can be found by the following algorithm:
- Compute the metric closure of the given graph. This forms a complete graph with edge weights corresponding to the distances between vertices; this specialization is computable in polynomial time.
- Remove all vertices not in the desired subset.
- Compute the minimum spanning tree of the metric closure.
- Expand the minimized edges into a graph.
- Replace the edges of the constructed graph with their paths from the given graph.
- Compute the minimum spanning tree of the expanded graph.
- Prepare a graph with only the edges contained in the tree.
If this proves too slow or inaccurate, it can be further optimized. See http://dl.acm.org/citation.cfm?doid=1806689.1806769 for more information.
If any of the given vertices do not exist in this graph, an error of type VertexNotFoundError is returned. If no path exists between any two of the given vertices, an error of type NotConnectedError is returned.
func (*ApproximateSteinerTree) AsGraph ¶
func (ast *ApproximateSteinerTree) AsGraph() graph.UndirectedGraph
AsGraph returns a graph representation of the subset of vertices and edges represented by this tree.
func (*ApproximateSteinerTree) Edges ¶
func (ast *ApproximateSteinerTree) Edges() graph.EdgeSet
Edges returns the set of edges computed as the approximation of the tree.
func (*ApproximateSteinerTree) Features ¶
func (ast *ApproximateSteinerTree) Features() graph.GraphFeature
Features returns the graph features being used for this algorithm.
type BellmanFordShortestPaths ¶
type BellmanFordShortestPaths struct {
// contains filtered or unexported fields
}
func BellmanFordShortestPathsOf ¶
func BellmanFordShortestPathsOf(g graph.Graph, start graph.Vertex) *BellmanFordShortestPaths
func (*BellmanFordShortestPaths) CostTo ¶
func (bfsp *BellmanFordShortestPaths) CostTo(end graph.Vertex) (float64, error)
func (*BellmanFordShortestPaths) Features ¶
func (bfsp *BellmanFordShortestPaths) Features() graph.GraphFeature
type PrimMinimumSpanningTree ¶
type PrimMinimumSpanningTree struct {
TotalWeight float64
// contains filtered or unexported fields
}
func PrimMinimumSpanningTreeOf ¶
func PrimMinimumSpanningTreeOf(g graph.UndirectedGraph) *PrimMinimumSpanningTree
func (*PrimMinimumSpanningTree) Edges ¶
func (mst *PrimMinimumSpanningTree) Edges() graph.EdgeSet
func (*PrimMinimumSpanningTree) Features ¶
func (mst *PrimMinimumSpanningTree) Features() graph.GraphFeature
type TiernanSimpleCycles ¶
type TiernanSimpleCycles struct {
// contains filtered or unexported fields
}
func TiernanSimpleCyclesOf ¶
func TiernanSimpleCyclesOf(g graph.DirectedGraph) *TiernanSimpleCycles
func (*TiernanSimpleCycles) Cycles ¶
func (tsc *TiernanSimpleCycles) Cycles() (cycles [][]graph.Vertex)
func (*TiernanSimpleCycles) CyclesInto ¶
func (tsc *TiernanSimpleCycles) CyclesInto(into interface{})
Source Files