graph_addons

package
v0.7.2 Latest Latest
Warning

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

 Go to latest Published: Aug 21, 2024 License: Apache-2.0 Imports: 7 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	StopWalk = errors.New("stop walk")
	SkipPath = errors.New("skip path")
)

Functions

func NewMemoryStore 

func NewMemoryStore[K comparable, T comparable]() graph.Store[K, T]

func PathWeight 

func PathWeight[K comparable, V any](g graph.Graph[K, V], path Path[K]) (weight int, err error)

func RemoveVertexAndEdges 

func RemoveVertexAndEdges[K comparable, T any](g graph.Graph[K, T], id K) error

func ReplaceVertex 

func ReplaceVertex[K comparable, T any](g graph.Graph[K, T], oldId K, newValue T, hasher func(T) K) error

func ReverseGraph 

func ReverseGraph[K comparable, T any](g graph.Graph[K, T]) (graph.Graph[K, T], error)

func ReverseLess 

func ReverseLess[K any](less func(K, K) bool) func(K, K) bool

ReverseLess is a helper function that returns a new less function that reverses the order of the original less function.

func ReverseTopologicalSort 

func ReverseTopologicalSort[K comparable, T any](g graph.Graph[K, T], less func(K, K) bool) ([]K, error)

TopologicalSort provides a stable topological ordering.

func TopologicalSort 

func TopologicalSort[K comparable, T any](g graph.Graph[K, T], less func(K, K) bool) ([]K, error)

TopologicalSort provides a stable topological ordering.

func WalkDown 

func WalkDown[K comparable, T any](g graph.Graph[K, T], start K, f WalkGraphFunc[K]) error

WalkDown walks down through the graph starting at `start` in BFS order.

func WalkUp 

func WalkUp[K comparable, T any](g graph.Graph[K, T], start K, f WalkGraphFunc[K]) error

WalkUp walks up through the graph starting at `start` in BFS order.

Types

type LayeredGraph 

type LayeredGraph[K comparable, T any] []graph.Graph[K, T]

LayeredGraph is a graph that is composed of multiple layers. When a vertex is added, it is added to the first layer (`[0]`). When an edge is added, if the source and target exist in the same layer, the edge is added to that layer, otherwise, the source and target are added to the first layer, and the edge is added. Remove and update operations are applied to all layers.

func LayeredGraphOf 

func LayeredGraphOf[K comparable, T any](g ...graph.Graph[K, T]) LayeredGraph[K, T]

func (LayeredGraph[K, T]) AddEdge 

func (g LayeredGraph[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*graph.EdgeProperties)) error

func (LayeredGraph[K, T]) AddEdgesFrom 

func (g LayeredGraph[K, T]) AddEdgesFrom(o graph.Graph[K, T]) error

func (LayeredGraph[K, T]) AddVertex 

func (g LayeredGraph[K, T]) AddVertex(value T, options ...func(*graph.VertexProperties)) error

func (LayeredGraph[K, T]) AddVerticesFrom 

func (g LayeredGraph[K, T]) AddVerticesFrom(o graph.Graph[K, T]) error

func (LayeredGraph[K, T]) AdjacencyMap 

func (g LayeredGraph[K, T]) AdjacencyMap() (map[K]map[K]graph.Edge[K], error)

func (LayeredGraph[K, T]) Clone 

func (g LayeredGraph[K, T]) Clone() (graph.Graph[K, T], error)

func (LayeredGraph[K, T]) Edge 

func (g LayeredGraph[K, T]) Edge(sourceHash, targetHash K) (graph.Edge[T], error)

func (LayeredGraph[K, T]) Edges 

func (g LayeredGraph[K, T]) Edges() ([]graph.Edge[K], error)

Edges may return duplicate edges if an edge exists in multiple layers. This is intentional because those edges may contain different properties.

func (LayeredGraph[K, T]) Order 

func (g LayeredGraph[K, T]) Order() (int, error)

func (LayeredGraph[K, T]) PredecessorMap 

func (g LayeredGraph[K, T]) PredecessorMap() (map[K]map[K]graph.Edge[K], error)

func (LayeredGraph[K, T]) RemoveEdge 

func (g LayeredGraph[K, T]) RemoveEdge(source, target K) error

func (LayeredGraph[K, T]) RemoveVertex 

func (g LayeredGraph[K, T]) RemoveVertex(hash K) error

func (LayeredGraph[K, T]) Size 

func (g LayeredGraph[K, T]) Size() (int, error)

func (LayeredGraph[K, T]) Traits 

func (g LayeredGraph[K, T]) Traits() *graph.Traits

func (LayeredGraph[K, T]) UpdateEdge 

func (g LayeredGraph[K, T]) UpdateEdge(source, target K, options ...func(properties *graph.EdgeProperties)) error

func (LayeredGraph[K, T]) Vertex 

func (g LayeredGraph[K, T]) Vertex(hash K) (v T, err error)

func (LayeredGraph[K, T]) VertexWithProperties 

func (g LayeredGraph[K, T]) VertexWithProperties(hash K) (v T, p graph.VertexProperties, err error)

type LoggingGraph 

type LoggingGraph[K comparable, T any] struct {
	graph.Graph[K, T]

	Log  *zap.SugaredLogger
	Hash func(T) K
}

func (LoggingGraph[K, T]) AddEdge 

func (g LoggingGraph[K, T]) AddEdge(sourceHash K, targetHash K, options ...func(*graph.EdgeProperties)) error

func (LoggingGraph[K, T]) AddEdgesFrom 

func (g LoggingGraph[K, T]) AddEdgesFrom(other graph.Graph[K, T]) error

func (LoggingGraph[K, T]) AddVertex 

func (g LoggingGraph[K, T]) AddVertex(value T, options ...func(*graph.VertexProperties)) error

func (LoggingGraph[K, T]) AddVerticesFrom 

func (g LoggingGraph[K, T]) AddVerticesFrom(other graph.Graph[K, T]) error

func (LoggingGraph[K, T]) Clone 

func (g LoggingGraph[K, T]) Clone() (graph.Graph[K, T], error)

func (LoggingGraph[K, T]) RemoveEdge 

func (g LoggingGraph[K, T]) RemoveEdge(source K, target K) error

func (LoggingGraph[K, T]) RemoveVertex 

func (g LoggingGraph[K, T]) RemoveVertex(hash K) error

func (LoggingGraph[K, T]) UpdateEdge 

func (g LoggingGraph[K, T]) UpdateEdge(source K, target K, options ...func(properties *graph.EdgeProperties)) error

type MemoryStore 

type MemoryStore[K comparable, T comparable] struct {
	// contains filtered or unexported fields
}

MemoryStore is like the default store returned by graph.New except that [AddVertex] and [AddEdge] are idempotent - they do not return an error if the vertex or edge already exists with the exact same value.

func (*MemoryStore[K, T]) AddEdge 

func (s *MemoryStore[K, T]) AddEdge(sourceHash, targetHash K, edge graph.Edge[K]) error

func (*MemoryStore[K, T]) AddVertex 

func (s *MemoryStore[K, T]) AddVertex(k K, t T, p graph.VertexProperties) error

func (*MemoryStore[K, T]) CreatesCycle 

func (s *MemoryStore[K, T]) CreatesCycle(source, target K) (bool, error)

CreatesCycle is a fastpath version of [CreatesCycle] that avoids calling [PredecessorMap], which generates large amounts of garbage to collect.

Because CreatesCycle doesn't need to modify the PredecessorMap, we can use inEdges instead to compute the same thing without creating any copies.

func (*MemoryStore[K, T]) Edge 

func (s *MemoryStore[K, T]) Edge(sourceHash, targetHash K) (graph.Edge[K], error)

func (*MemoryStore[K, T]) ListEdges 

func (s *MemoryStore[K, T]) ListEdges() ([]graph.Edge[K], error)

func (*MemoryStore[K, T]) ListVertices 

func (s *MemoryStore[K, T]) ListVertices() ([]K, error)

func (*MemoryStore[K, T]) RemoveEdge 

func (s *MemoryStore[K, T]) RemoveEdge(sourceHash, targetHash K) error

func (*MemoryStore[K, T]) RemoveVertex 

func (s *MemoryStore[K, T]) RemoveVertex(k K) error

func (*MemoryStore[K, T]) UpdateEdge 

func (s *MemoryStore[K, T]) UpdateEdge(sourceHash, targetHash K, edge graph.Edge[K]) error

func (*MemoryStore[K, T]) Vertex 

func (s *MemoryStore[K, T]) Vertex(k K) (T, graph.VertexProperties, error)

func (*MemoryStore[K, T]) VertexCount 

func (s *MemoryStore[K, T]) VertexCount() (int, error)

type Path 

type Path[K comparable] []K

func (Path[K]) Contains 

func (p Path[K]) Contains(k K) bool

type WalkGraphFunc 

type WalkGraphFunc[K comparable] func(p Path[K], nerr error) error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.