Documentation
¶
Overview ¶
Package graph provides data structures to manipulate a set of vertices and a collection of edges that each connect a pair of vertices.
Depth-first search (DFS) and breadth-first search (BFS) start from source vertex and perform the following steps until the data structure is empty:
- take the next unmarked vertex v from the data structure and mark it,
- put onto the data structure all unmarked vertices that are adjacent to v.
The algorithms differ only in the rule used to take the next vertex: most recently added for DFS (stack), least recently added for BFS (queue).
DFS explores the graph by looking for new vertices far away from the start point, taking closer vertices only when dead ends are encountered.
BFS completely covers the area close to the starting point, moving farther away only when everything nearby has been examined.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DepthFirstSearch ¶
func DepthFirstSearch(g *AdjacencyList, source int) []int
DepthFirstSearch is a method to find the vertices connected to the source. It is similar to searching through the maze by using a string that guarantees you can always find a way out and the passage marks guarantee that you avoid exploring any passage or intersection twice. To search a graph, a recursive method is used that visits all of graph's vertices and edges.
Depth-first search marks all the vertices connected to a given source in time proportional to the sum of their degrees. A degree of vertex v is a count of its adjacent vertices.
func HasCycle ¶
func HasCycle(g *AdjacencyList) bool
HasCycle reports whether a given graph has a cycle (path with at least one edge whose first and last vertices are the same). It assumes no self-loops or parallel edges.
Example ¶
g := NewAdjacencyList(5) g.Add(1, 0) g.Add(0, 2) g.Add(0, 3) g.Add(3, 4) fmt.Println(HasCycle(g)) g.Add(2, 1) fmt.Println(HasCycle(g))
Output: false true
func IsBipartite ¶
func IsBipartite(g *AdjacencyList) bool
IsBipartite returns true if a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set (colored red) with a vertex in the other set (colored black). In other words, can the vertices of a given graph be assigned one of two colors in such a way that no edge connects vertices of the same color? Graph is two-colorable if and only if it contains no odd-length cycle.
For example, IMDB can be defined as a graph with movies and performers as vertices and each line defining the adjacency list of edges connecting each movie to its performers. The graph is bipartite — there are no edges connecting performers to performers or movies to movies.
Types ¶
type AdjacencyList ¶
type AdjacencyList struct {
// contains filtered or unexported fields
}
AdjacencyList maintains a vertex-indexed array of lists of the vertices adjacent to each vertex. Every edge appears twice: if an edge connects v and w, then w appears in v's list and v appears in w's list. Space usage is proportional to number of vertices + edges. A new edge is added in constant time and iteration through adjacent vertices is constant time per adjacent vertex.
func NewAdjacencyList ¶
func NewAdjacencyList(vertices int) *AdjacencyList
NewAdjacencyList creates a graph represented as an array of adjacency lists.
func (*AdjacencyList) Add ¶
func (g *AdjacencyList) Add(v, w int)
Add adds a new edge connecting v and w vertices.
func (*AdjacencyList) Adjacent ¶
func (g *AdjacencyList) Adjacent(v int) []int
Adjacent returns vertices adjacent to the vertex v.
func (*AdjacencyList) String ¶
func (g *AdjacencyList) String() string
String returns a string representation of the graph's adjacency lists.
type BreadthFirstPath ¶
type BreadthFirstPath struct {
// contains filtered or unexported fields
}
BreadthFirstPath uses breadth-first search to find paths in a graph with the fewest number of edges from the source vertex. The algorithm is based on maintaining a queue of all vertices that have been marked but whose adjacency lists have not been checked. It puts the source vertex onto the queue, then does the following steps until the queue is empty:
- remove the next vertex v from the queue,
- put onto the queue all unmarked vertices that are adjacent to v and mark them.
BFS takes time proportional to number of edges + number of vertices in the worst case.
func NewBreadthFirstPath ¶
func NewBreadthFirstPath(g *AdjacencyList, source int) *BreadthFirstPath
NewBreadthFirstPath creates BreadthFirstPath to look up shortest paths from the source vertex.
func (*BreadthFirstPath) To ¶
func (bfs *BreadthFirstPath) To(v int) []int
To searches a shortest path from source to the connected vertex v.
type ConnectedComponent ¶
type ConnectedComponent struct {
// contains filtered or unexported fields
}
ConnectedComponent uses depth-first search to find connected components in a graph.
func NewConnectedComponent ¶
func NewConnectedComponent(g *AdjacencyList) *ConnectedComponent
NewConnectedComponent finds the connected components of a graph. It uses marked array to find a vertex to serve as the starting point for a depth-first search in each component. Firstly it marks all vertices connected to 0. Then in a loop it looks for an unmarked vertex and marks all vertices connected to that vertex.
DFS uses preprocessing time and space proportional to E+V (number of edges plus vertices) to support constant-time connectivity queries in a graph. In theory DFS is faster than union-find algorithm, because it provides a constant-time guarantee. In practise, the difference is negligible, and union-find is faster because it doesn't have to build a full representation of the graph.
func (*ConnectedComponent) Count ¶
func (cc *ConnectedComponent) Count() int
Count returns number of components.
func (*ConnectedComponent) ID ¶
func (cc *ConnectedComponent) ID(v int) int
ID returns component identifier (between 0 and count-1) for vertex v.
func (*ConnectedComponent) IsConnected ¶
func (cc *ConnectedComponent) IsConnected(v, w int) bool
IsConnected tells whether v and w are in the same component by checking if site identifiers are equal.
type DepthFirstPath ¶
type DepthFirstPath struct {
// contains filtered or unexported fields
}
DepthFirstPath uses depth-first search to find paths to all the vertices in a graph that are connected to a given start vertex s. To save known paths to each vertex, it maintains a vertex-indexed array.
func NewDepthFirstPath ¶
func NewDepthFirstPath(g *AdjacencyList, source int) *DepthFirstPath
NewDepthFirstPath creates DepthFirstPath to look up paths connected to source vertex.
func (*DepthFirstPath) To ¶
func (dfs *DepthFirstPath) To(v int) []int
To searches a path from source to the connected vertex v.
type SymbolGraph ¶
type SymbolGraph struct {
// contains filtered or unexported fields
}
SymbolGraph is a graph whose vertices are strings (city, movie), not integer indices.
Example ¶
package main
import (
"bytes"
"fmt"
"log"
"github.com/marselester/alg/graph"
)
const routes = `
JFK MCO
ORD DEN
ORD HOU
DFW PHX
JFK ATL
ORD DFW
ORD PHX
ATL HOU
DEN PHX
PHX LAX
JFK ORD
DEN LAS
DFW HOU
ORD ATL
LAS LAX
ATL MCO
HOU MCO
LAS PHX
`
func main() {
sg, err := graph.NewSymbolGraph(bytes.NewReader([]byte(routes)), " ")
if err != nil {
log.Fatalf("flight: graph creation failed: %v", err)
}
v, ok := sg.Index("JFK")
if !ok {
log.Fatalf("flight: airport not found")
}
for _, v := range sg.Adjacent(v) {
fmt.Println(sg.Name(v))
}
}
Output: ORD ATL MCO
func NewSymbolGraph ¶
func NewSymbolGraph(in io.ReadSeeker, sep string) (*SymbolGraph, error)
NewSymbolGraph constructs a symbol graph. It uses two passes through the data to build underlying indices. Note, one pass would be sufficient if a graph used a hash table implementation (extra log V factor, V is number of vertices) instead of a linked list.
func (*SymbolGraph) Adjacent ¶
func (sg *SymbolGraph) Adjacent(v int) []int
Adjacent returns vertices adjacent to the vertex v.
func (*SymbolGraph) Graph ¶
func (sg *SymbolGraph) Graph() *AdjacencyList
Graph returns an underlying graph.
func (*SymbolGraph) Index ¶
func (sg *SymbolGraph) Index(key string) (int, bool)
Index returns a vertex index associated with a key (vertex name).
func (*SymbolGraph) Name ¶
func (sg *SymbolGraph) Name(v int) string
Name returns a vertex name associated with index v. Empty string indicates that vertex doesn't exist.
Source Files
Directories