algo

package
v0.1.2-0...-9ef9a90 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 16, 2023 License: EPL-1.0 Imports: 4 Imported by: 0

Documentation

Index

Constants

View Source
const ApproximateSteinerTreeSupportedFeatures = graph.DeterministicIteration

ApproximateSteinerTreeSupportedFeatures are the graph features supported by the Steiner tree approximation algorithm.

View Source
const (
	BellmanFordSupportedFeatures = graph.DeterministicIteration
)
View Source
const (
	PrimMinimumSpanningTreeSupportedFeatures = graph.DeterministicIteration
)
View Source
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:

  1. 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.
  2. Remove all vertices not in the desired subset.
  3. Compute the minimum spanning tree of the metric closure.
  4. Expand the minimized edges into a graph.
  5. Replace the edges of the constructed graph with their paths from the given graph.
  6. Compute the minimum spanning tree of the expanded graph.
  7. 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

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) EdgesTo

func (bfsp *BellmanFordShortestPaths) EdgesTo(end graph.Vertex) ([]graph.Edge, error)

func (*BellmanFordShortestPaths) Features

func (bfsp *BellmanFordShortestPaths) Features() graph.GraphFeature

type PrimMinimumSpanningTree

type PrimMinimumSpanningTree struct {
	TotalWeight float64
	// contains filtered or unexported fields
}

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{})

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL