Documentation
¶
Index ¶
- Variables
- type AdjacencyListDigraph
- func (g *AdjacencyListDigraph[V]) AddEdge(from, to V)
- func (g *AdjacencyListDigraph[V]) AddNode(node V) bool
- func (g *AdjacencyListDigraph[V]) DepthFirst(less func(a, b V) bool, f func(V)) map[V]*DepthFirstNode[V]
- func (g *AdjacencyListDigraph[V]) Edges() [][2]V
- func (g *AdjacencyListDigraph[V]) Has(node V) bool
- func (g *AdjacencyListDigraph[V]) Neighbours(node V) ([]V, bool)
- func (g *AdjacencyListDigraph[V]) Nodes() []V
- func (g *AdjacencyListDigraph[V]) RemoveEdge(from, to V) bool
- func (g *AdjacencyListDigraph[V]) RemoveNode(node V) bool
- func (g *AdjacencyListDigraph[V]) ShortestDistance(from V) (distances map[V]int, subgraph *AdjacencyListDigraph[V])
- func (g *AdjacencyListDigraph[V]) String() string
- func (g *AdjacencyListDigraph[V]) TopologicalOrder() (order []V, err error)
- type DepthFirstNode
Constants ¶
This section is empty.
Variables ¶
var ErrCycleDetected = errors.New("cycle detected")
Functions ¶
This section is empty.
Types ¶
type AdjacencyListDigraph ¶
type AdjacencyListDigraph[V comparable] struct { // contains filtered or unexported fields }
AdjacencyListDigraph is a directed graph that uses an adjacency list representation. V should be a small type (int-sized, one machine word) for best performance. Multiple edges between vertices are not supported.
func NewAdjacencyListDigraph ¶
func NewAdjacencyListDigraph[V comparable]() *AdjacencyListDigraph[V]
func (*AdjacencyListDigraph[V]) AddEdge ¶
func (g *AdjacencyListDigraph[V]) AddEdge(from, to V)
AddEdge adds an edge to the graph. Duplicate edges are not supported.
func (*AdjacencyListDigraph[V]) AddNode ¶
func (g *AdjacencyListDigraph[V]) AddNode(node V) bool
AddNode tries to add a vertex to the graph, unconnected to any other vertex. It returns true if the node didn't exist and was successfully added.
func (*AdjacencyListDigraph[V]) DepthFirst ¶
func (g *AdjacencyListDigraph[V]) DepthFirst( less func(a, b V) bool, f func(V), ) map[V]*DepthFirstNode[V]
DepthFirst traverses the graph in depth-first order. If less is provided, it is used to pre-sort the graph's nodes before starting the traversal (see slices.SortFunc), which can make the traversal deterministic. If f is provided, it is called when a node is discovered.
func (*AdjacencyListDigraph[V]) Edges ¶
func (g *AdjacencyListDigraph[V]) Edges() [][2]V
Edges returns all edges in the graph, in no particular order. The inner pair of V, which represents one edge, is in the order {tail, head}.
func (*AdjacencyListDigraph[V]) Has ¶
func (g *AdjacencyListDigraph[V]) Has(node V) bool
Has returns true if the vertex provided is in the graph.
func (*AdjacencyListDigraph[V]) Neighbours ¶
func (g *AdjacencyListDigraph[V]) Neighbours(node V) ([]V, bool)
Neighbours returns all neighbours of the vertex, in no particular order. (nil, false) is returned if the vertex is not in the graph.
func (*AdjacencyListDigraph[V]) Nodes ¶
func (g *AdjacencyListDigraph[V]) Nodes() []V
Nodes returns all vertices in the graph, in no particular order.
func (*AdjacencyListDigraph[V]) RemoveEdge ¶
func (g *AdjacencyListDigraph[V]) RemoveEdge(from, to V) bool
RemoveEdge removes an edge from the graph. It returns true if the edge exists and was removed. If more than one edge exists, only one will be removed.
func (*AdjacencyListDigraph[V]) RemoveNode ¶
func (g *AdjacencyListDigraph[V]) RemoveNode(node V) bool
RemoveNode removes a vertex from the graph. It will also remove all edges that start or end from this vertex. It returns true if the vertex exists and was removed.
func (*AdjacencyListDigraph[V]) ShortestDistance ¶
func (g *AdjacencyListDigraph[V]) ShortestDistance(from V) ( distances map[V]int, subgraph *AdjacencyListDigraph[V])
ShortestDistance takes a node in the graph and returns a map of all nodes reachable from the first node to their shortest distance from that node, as well as a subgraph of reachable nodes. If the node doesn't exist, only that node is returned in the map with distance 0, and only that node is returned in the subgraph. This works with cyclic graphs as well.
func (*AdjacencyListDigraph[V]) String ¶
func (g *AdjacencyListDigraph[V]) String() string
String returns a string representation of the graph. If V implements fmt.Stringer, it will be used, otherwise the default format for its underlying type is used. Lines are sorted in lexicographic order of their nodes. The neighbours of each node are also output in lexicographic order.
func (*AdjacencyListDigraph[V]) TopologicalOrder ¶
func (g *AdjacencyListDigraph[V]) TopologicalOrder() (order []V, err error)
TopologicalOrder tries to generate a topological order for all vertices. It may return ErrCycleDetected if the order cannot be generated because the graph contains a cycle.
type DepthFirstNode ¶
type DepthFirstNode[V comparable] struct { // Discover is the time when the node was discovered. Discover int // Finish is the time when the node's children were fully explored. Finish int // Parent is the parent of this node. Parent V }
DepthFirstNode describes a node in a depth-first traversal.
func (*DepthFirstNode[V]) String ¶
func (d *DepthFirstNode[V]) String() string
Source Files