Documentation
¶
Index ¶
- func FindCutVertices(gr Graph) []int
- func FindCycle(gr Graph) []int
- func IsBipartite(gr Graph) bool
- type ConnectedComponents
- func (connectedComponents ConnectedComponents) Component(componentID int) []int
- func (connectedComponents ConnectedComponents) ComponentID(vertexID int) int
- func (connectedComponents ConnectedComponents) Connected(vertexID1 int, vertexID2 int) bool
- func (connectedComponents ConnectedComponents) Count() int
- type Edge
- type Graph
- type ImplGraph
- type Paths
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func FindCutVertices ¶
FindCutVertices finds cut-vertices in a graph. Cut-vertex (articulation vertex) is a vertex whose removal increases number of connected components. A graph is biconnected if it has no articulation vertices. https://algs4.cs.princeton.edu/41graph/Biconnected.java.html
func FindCycle ¶
FindCycle returns cycle in a graph (if such cycle exists). Cycle is a path whose first and last vertices are the same. https://algs4.cs.princeton.edu/41graph/Cycle.java.html
func IsBipartite ¶
IsBipartite tells if graph is two-colorable - such that each no edge connects vertices of the same color. In a bipartite graph vertices can be divided into two sets such that all edges connect a vertex in one set with a vertex in other set. https://algs4.cs.princeton.edu/41graph/Bipartite.java.html
Types ¶
type ConnectedComponents ¶
type ConnectedComponents struct {
// contains filtered or unexported fields
}
ConnectedComponents is a collection of connected components in a graph. Connected component is a set of vertices connected by edges.
func FindConnectedComponents ¶
func FindConnectedComponents(gr Graph) ConnectedComponents
FindConnectedComponents returns connected components in a graph. https://algs4.cs.princeton.edu/41graph/CC.java.html
func NewConnectedComponents ¶
func NewConnectedComponents(count int, componentIDs []int) ConnectedComponents
NewConnectedComponents creates instance.
func (ConnectedComponents) Component ¶
func (connectedComponents ConnectedComponents) Component(componentID int) []int
Component returns vertices of a connected component.
func (ConnectedComponents) ComponentID ¶
func (connectedComponents ConnectedComponents) ComponentID(vertexID int) int
ComponentID returns component to which vertex belongs.
func (ConnectedComponents) Connected ¶
func (connectedComponents ConnectedComponents) Connected(vertexID1 int, vertexID2 int) bool
Connected tells if two vertices are connected.
func (ConnectedComponents) Count ¶
func (connectedComponents ConnectedComponents) Count() int
Count gets number of connected components.
type Edge ¶
type Edge struct {
// contains filtered or unexported fields
}
Edge is a pair of connected vertices in a graph.
func AllGraphEdges ¶
AllGraphEdges returns all edges of a graph.
func FindCutEdges ¶
FindCutEdges finds cut-edges in a graph. Cut-edge is an edge whose deletion increases number of connected components. An edge is a bridge iif it is not contained in any cycle. https://algs4.cs.princeton.edu/41graph/Bridge.java.html
type Graph ¶
type Graph interface {
// NumVertices gets number of graph vertices.
NumVertices() int
// NumEdges gets number of graph edges.
NumEdges() int
// AdjacentVertices returns vertices adjacent to the vertex.
AdjacentVertices(vertexID int) []int
}
Graph is a set of vertices and edges.
type ImplGraph ¶
type ImplGraph struct {
// contains filtered or unexported fields
}
ImplGraph is an implementation of Graph.
func NewImplGraph ¶
NewImplGraph creates instance of ImplGraph.
func (*ImplGraph) AdjacentVertices ¶
AdjacentVertices returns vertices adjacent to the vertex.
func (*ImplGraph) NumVertices ¶
NumVertices gets number of graph vertices.
type Paths ¶
type Paths struct {
// contains filtered or unexported fields
}
Paths is a collection of paths from the source vertex to other vertices. A path is a sequence of vertices connected by edges.
func FindPathsBreadthFirst ¶
FindPathsBreadthFirst returns paths from a vertex using breadth-first search. https://algs4.cs.princeton.edu/41graph/BreadthFirstPaths.java.html
func FindPathsDepthFirst ¶
FindPathsDepthFirst returns paths from a vertex using depth-first search. https://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.html
func (Paths) VertexCount ¶
VertexCount gets number of vertices connected with source vertex.
Source Files