graphs

Documentation

Index

• Variables
• func FindCycle(start uint32, graph Directed) []uint32
• func FindDistance(start, end uint32, graph Directed, cache *ShortestCache) int
• func FindPath(start, end uint32, graph Directed) []uint32
• type Connected
• type Directed
• type Edges
  • func (*Edges) Descriptor() ([]byte, []int)
  • func (x *Edges) GetId() uint32
  • func (x *Edges) GetReferences() []uint32
  • func (*Edges) ProtoMessage()
  • func (x *Edges) ProtoReflect() protoreflect.Message
  • func (x *Edges) Reset()
  • func (x *Edges) String() string
• type FromTo
• type Queue
  • func NewQueue(value uint32) *Queue
  • func (q *Queue) Dequeue() (uint32, *Queue)
  • func (q *Queue) Empty() bool
  • func (q *Queue) Enqueue(value uint32) *Queue
• type ShortestCache
  • func NewShortestCache(shards uint32) *ShortestCache
  • func (c *ShortestCache) Add(from, to uint32, dist int)
  • func (c *ShortestCache) AddNext(from, to, next uint32)
  • func (c *ShortestCache) Get(from, to uint32) (int, bool)

Variables

var File_pkg_graphs_edge_proto protoreflect.FileDescriptor

Functions

func FindCycle

func FindCycle(start uint32, graph Directed) []uint32

FindCycle returns a loop containing start in graph, or nil if there is no such loop.

func FindDistance

func FindDistance(start, end uint32, graph Directed, cache *ShortestCache) int

func FindPath

func FindPath(start, end uint32, graph Directed) []uint32

Types

type Connected

type Connected map[uint32]bool

type Directed

type Directed struct {
	Nodes map[uint32]map[uint32]bool
}

Directed is a thread-unsafe representation of a directed Graph.

type Edges

type Edges struct {

	// id is the unique identifier of the document.
	Id uint32 `protobuf:"varint,1,opt,name=id,proto3" json:"id,omitempty"`
	// references is the unique identifiers of referenced documents.
	References []uint32 `protobuf:"varint,2,rep,packed,name=references,proto3" json:"references,omitempty"`
	// contains filtered or unexported fields
}

Edges is the set of references in a document.

func (*Edges) Descriptor

func (*Edges) Descriptor() ([]byte, []int)

Deprecated: Use Edges.ProtoReflect.Descriptor instead.

func (*Edges) GetId

func (x *Edges) GetId() uint32

func (*Edges) GetReferences

func (x *Edges) GetReferences() []uint32

func (*Edges) ProtoMessage

func (*Edges) ProtoMessage()

func (*Edges) ProtoReflect

func (x *Edges) ProtoReflect() protoreflect.Message

func (*Edges) Reset

func (x *Edges) Reset()

func (*Edges) String

func (x *Edges) String() string

type FromTo

type FromTo struct {
	From uint32
	To   uint32
}

type Queue

type Queue struct {
	Value    uint32
	Next     *Queue
	Previous *Queue
}

func NewQueue

func NewQueue(value uint32) *Queue

func (*Queue) Dequeue

func (q *Queue) Dequeue() (uint32, *Queue)

func (*Queue) Empty

func (q *Queue) Empty() bool

func (*Queue) Enqueue

func (q *Queue) Enqueue(value uint32) *Queue

type ShortestCache

type ShortestCache struct {
	// contains filtered or unexported fields
}

func NewShortestCache

func NewShortestCache(shards uint32) *ShortestCache

func (*ShortestCache) Add

func (c *ShortestCache) Add(from, to uint32, dist int)

func (*ShortestCache) AddNext

func (c *ShortestCache) AddNext(from, to, next uint32)

func (*ShortestCache) Get

func (c *ShortestCache) Get(from, to uint32) (int, bool)