Documentation ¶
Index ¶
- Variables
- type Edge
- type EdgeOptionFunc
- type EdgeProperties
- type Graph
- type GraphOptionFunc
- type GraphProperties
- type GraphType
- type Vertex
- func (v *Vertex[T]) Degree() int
- func (v *Vertex[T]) HasNeighbor(vertex *Vertex[T]) bool
- func (v *Vertex[T]) InDegree() int
- func (v *Vertex[T]) Label() T
- func (v *Vertex[T]) NeighborByLabel(label T) *Vertex[T]
- func (v *Vertex[T]) Neighbors() []*Vertex[T]
- func (v *Vertex[T]) OutDegree() int
- func (v *Vertex[T]) Weight() float64
- type VertexOptionFunc
- type VertexProperties
Constants ¶
This section is empty.
Variables ¶
Functions ¶
This section is empty.
Types ¶
type Edge ¶
type Edge[T comparable] struct { // contains filtered or unexported fields }
Edge represents an edges in a graph. It contains start and end points.
func NewEdge ¶
func NewEdge[T comparable](source *Vertex[T], dest *Vertex[T], options ...EdgeOptionFunc) *Edge[T]
func (Edge[T]) Destination ¶ added in v0.2.0
Destination returns edge dest vertex
func (*Edge[T]) OtherVertex ¶ added in v0.2.0
OtherVertex accepts the label of one the vertices of the edge and returns the other one. If the input label doesn't match to either of the vertices, returns nil.
type EdgeOptionFunc ¶
type EdgeOptionFunc func(properties *EdgeProperties)
EdgeOptionFunc represent an alias of function type that modifies the specified edge properties.
func WithEdgeWeight ¶
func WithEdgeWeight(weight float64) EdgeOptionFunc
WithEdgeWeight sets the edge weight for the specified edge properties in the returned EdgeOptionFunc.
type EdgeProperties ¶
type EdgeProperties struct {
// contains filtered or unexported fields
}
EdgeProperties represents the properties of an edge.
type Graph ¶
type Graph[T comparable] interface { GraphType // AddEdge adds an edge from the vertex with the 'from' label to // the vertex with the 'to' label by appending the 'to' vertex to the // 'neighbors' slice of the 'from' vertex, in directed graph. // // In undirected graph, it also adds an edge from the vertex with // the 'to' label to the vertex with the 'from' label by appending // the 'from' vertex to the 'neighbors' slice of the 'to' vertex. it // means that it create the edges in both direction between the specified // vertices. // // This method accepts additional edge options such as weight and adds // them to the new edge. // // // It creates the input vertices if they don't exist in the graph. // If any of the specified vertices is nil, returns nil. // If edge already exist, returns error. AddEdge(from, to *Vertex[T], options ...EdgeOptionFunc) (*Edge[T], error) // GetAllEdges returns a slice of all edges connecting source vertex to // target vertex if such vertices exist in this graph. // // In directed graph, it returns a single edge. // // If any of the specified vertices is nil, returns nil. // If any of the vertices does not exist, returns nil. // If both vertices exist but no edges found, returns an empty set. GetAllEdges(from, to *Vertex[T]) []*Edge[T] // GetEdge returns an edge connecting source vertex to target vertex // if such vertices and such edge exist in this graph. // // In undirected graph, returns only the edge from the "from" vertex to // the "to" vertex. // // If any of the specified vertices is nil, returns nil. // If edge does not exist, returns nil. GetEdge(from, to *Vertex[T]) *Edge[T] // EdgesOf returns a slice of all edges touching the specified vertex. // If no edges are touching the specified vertex returns an empty slice. // // If the input vertex is nil, returns nil. // If the input vertex does not exist, returns nil. EdgesOf(v *Vertex[T]) []*Edge[T] // RemoveEdges removes input edges from the graph from the specified // slice of edges, if they exist. In undirected graph, removes edges // in both directions. RemoveEdges(edges ...*Edge[T]) // AddVertexByLabel adds a new vertex with the given label to the graph. // Label of the vertex is a comparable type. This method also accepts the // vertex properties such as weight. // // If there is a vertex with the same label in the graph, returns nil. // Otherwise, returns the created vertex. AddVertexByLabel(label T, options ...VertexOptionFunc) *Vertex[T] // AddVertex adds the input vertex to the graph. It doesn't add // vertex to the graph if the input vertex label is already exists // in the graph. AddVertex(v *Vertex[T]) // GetVertexByID returns the vertex with the input label. // // If vertex doesn't exist, returns nil. GetVertexByID(label T) *Vertex[T] // GetAllVerticesByID returns a slice of vertices with the specified label list. // // If vertex doesn't exist, doesn't add nil to the output list. GetAllVerticesByID(label ...T) []*Vertex[T] // GetAllVertices returns a slice of all existing vertices in the graph. GetAllVertices() []*Vertex[T] // RemoveVertices removes all the specified vertices from this graph including // all its touching edges if present. RemoveVertices(vertices ...*Vertex[T]) // ContainsEdge returns 'true' if and only if this graph contains an edge // going from the source vertex to the target vertex. // // If any of the specified vertices does not exist in the graph, or if is nil, // returns 'false'. ContainsEdge(from, to *Vertex[T]) bool // ContainsVertex returns 'true' if this graph contains the specified vertex. // // If the specified vertex is nil, returns 'false'. ContainsVertex(v *Vertex[T]) bool }
Graph defines methods for managing a graph with vertices and edges. It is the base interface in the graph hierarchy. Each graph object contains a set of vertices and edges.
Through generics, a graph can be typed to specific classes for vertices' label T.
func New ¶
func New[T comparable](options ...GraphOptionFunc) Graph[T]
New creates a new instance of base graph that implemented the Graph interface.
type GraphOptionFunc ¶
type GraphOptionFunc func(properties *GraphProperties)
GraphOptionFunc represent an alias of function type that modifies the specified graph properties.
func Acyclic ¶
func Acyclic() GraphOptionFunc
Acyclic returns a GraphOptionFunc that modifies the specified graph properties. It sets the isAcyclic and isDirected to true. Only direct graph can be acyclic.
func Directed ¶
func Directed() GraphOptionFunc
Directed returns a GraphOptionFunc that modifies the specified graph properties. It sets the isDirected to true.
func Weighted ¶
func Weighted() GraphOptionFunc
Weighted returns a GraphOptionFunc that modifies the specified graph properties. It sets the isWeighted to true.
type GraphProperties ¶
type GraphProperties struct {
// contains filtered or unexported fields
}
GraphProperties represents the properties of a graph.
type GraphType ¶
type GraphType interface { // IsDirected returns true if the graph is directed, false otherwise. IsDirected() bool // IsAcyclic returns true if the graph is acyclic, false otherwise. IsAcyclic() bool // IsWeighted returns true if the graph is weighted, false otherwise. IsWeighted() bool }
GraphType defines methods to determine the type of graph. A graph can have multiple types. e.g., a directed graph can be a weighted or acyclic.
type Vertex ¶
type Vertex[T comparable] struct { // contains filtered or unexported fields }
Vertex represents a node or point in a graph
func NewVertex ¶
func NewVertex[T comparable](label T, options ...VertexOptionFunc) *Vertex[T]
func TopologySort ¶
func TopologySort[T comparable](g Graph[T]) ([]*Vertex[T], error)
TopologySort performs a topological sort of the graph using Kahn's algorithm. If the sorted list of vertices does not contain all vertices in the graph, it means there is a cycle in the graph.
It returns error if it finds a cycle in the graph.
func (*Vertex[T]) Degree ¶ added in v0.2.0
Degree returns the total degree of the vertex which is the sum of in and out degrees.
func (*Vertex[T]) HasNeighbor ¶
HasNeighbor checks if the input vertex is the neighbor of the current node or not. It returns 'true' if it finds the input in the neighbors. Otherwise, returns 'false'.
func (*Vertex[T]) NeighborByLabel ¶
NeighborByLabel iterates over the neighbor slice and returns the vertex which its label is equal to the input label.
It returns nil if there is no neighbor with that label.
func (*Vertex[T]) Neighbors ¶
Neighbors returns a copy of neighbor slice. If the caller changed the result slice, it won't impact the graph or the vertex.
type VertexOptionFunc ¶
type VertexOptionFunc func(properties *VertexProperties)
VertexOptionFunc represent an alias of function type that modifies the specified vertex properties.
func WithVertexWeight ¶
func WithVertexWeight(weight float64) VertexOptionFunc
WithVertexWeight sets the edge weight for the specified vertex properties in the returned VertexOptionFunc.
type VertexProperties ¶
type VertexProperties struct {
// contains filtered or unexported fields
}
VertexProperties represents the properties of an edge.