README
¶
graph
A graph is a collection of "nodes" (a.k.a points or vertices) and "edges" (a.k.a lines or arcs) connecting some (possibly empty) subset of them. The edges of graphs may also be imbued with directedness. The study of graphs is known as graph theory.
Documentation
¶
Index ¶
- func AddEdges(addEdge ...AddEdge)
- func ConnectNodes(nodes ...*Node)
- func DeleteAttribute[T any](attrs Attributes, name string)
- func EncodeDOT(w io.Writer, nodes Nodes) error
- func EncodeJSON(w io.Writer, nodes Nodes) error
- func GetAttribute[T any](attrs Attributes, name string) (T, error)
- func MeshNodes(nodes ...*Node)
- func SetAttribute[T any](attrs Attributes, name string, value T)
- func UseAttribute[T any](attrs Attributes, name string, fn func(T)) error
- func WithAttributes(attrs Attributes) func(*Instance)
- func WithNodes(nodes Nodes) func(*Instance)
- type AddEdge
- type Attributes
- type Clique
- type Cliques
- type Edge
- type EdgeDirection
- type EdgeMap
- type Edges
- type Instance
- func (inst *Instance) AddEdge(from, to *Node)
- func (inst *Instance) AddEdges(em EdgeMap)
- func (inst *Instance) AddNode(node *Node)
- func (inst *Instance) AddNodes(nodes ...*Node)
- func (inst *Instance) BFS(fn func(*Node))
- func (inst *Instance) DFS(fn func(*Node))
- func (inst *Instance) IsAcyclic() bool
- func (inst *Instance) IsBipartite() bool
- func (inst *Instance) IsMultipartite(k int) bool
- func (inst *Instance) IsUnicyclic() bool
- func (inst *Instance) Visit(fn func(*Node))
- type Node
- func (n *Node) AddEdge(e *Node)
- func (n *Node) AddEdgeWithDirection(e *Node, direction EdgeDirection)
- func (n *Node) AddLink(e *Node)
- func (n *Node) HasCycleContaining(node *Node) bool
- func (n *Node) HasCycles() bool
- func (n *Node) HasPath(end *Node) bool
- func (n *Node) PathTo(end *Node) Path
- func (n *Node) PathToWithout(end, without *Node) bool
- func (n *Node) Visit(fn func(*Node))
- func (n *Node) VisitAll(fn func(*Node))
- type NodeSet
- type NodeSets
- type Nodes
- type Path
- type Paths
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ConnectNodes ¶
func ConnectNodes(nodes ...*Node)
ConnectNodes creats an ordered, directed relationship between the given nodes. The first node has an edge to the second node, which has a relationship to the third node, etc.
a → b → c → ...
Example ¶
package main
import (
"fmt"
"github.com/picatz/graph"
)
func main() {
a := &graph.Node{Name: "a"}
b := &graph.Node{Name: "b"}
c := &graph.Node{Name: "c"}
graph.ConnectNodes(a, b, c)
fmt.Println(a.PathTo(c))
}
Output: a → b → c
Example (Path_to) ¶
package main
import (
"fmt"
"github.com/picatz/graph"
)
func main() {
a := &graph.Node{Name: "a"}
b := &graph.Node{Name: "b"}
c := &graph.Node{Name: "c"}
// a → b → c
graph.ConnectNodes(a, b, c)
path := a.PathTo(c)
fmt.Println("a to c:", a.HasPath(c))
fmt.Println("c to a:", c.HasPath(a))
fmt.Println("nodes in path:", len(path))
fmt.Println("0:", path[0].Name)
fmt.Println("1:", path[1].Name)
fmt.Println("2:", path[2].Name)
}
Output: a to c: true c to a: false nodes in path: 3 0: a 1: b 2: c
func DeleteAttribute ¶
func DeleteAttribute[T any](attrs Attributes, name string)
DeleteAttribute is a helper function to remove a named attribute.
func GetAttribute ¶
func GetAttribute[T any](attrs Attributes, name string) (T, error)
GetAttributes is a helper function to return a named attribute of a specific type.
func MeshNodes ¶
func MeshNodes(nodes ...*Node)
MeshNodes creats a fully meshed, bi-directional relationship between all of the given nodes.
a
⤢ ↑ ⤡
b ←─┼─→ d
⤡ ↓ ⤢
c
Example ¶
package main
import (
"fmt"
"github.com/picatz/graph"
)
func main() {
a := &graph.Node{Name: "a"}
b := &graph.Node{Name: "b"}
c := &graph.Node{Name: "c"}
// a
// ⤢ ⤡
// b ↔ c
graph.MeshNodes(a, b, c)
fmt.Println(a.PathTo(c))
fmt.Println(c.PathTo(a))
}
Output: a → c c → a
Example (Path_to) ¶
package main
import (
"fmt"
"github.com/picatz/graph"
)
func main() {
a := &graph.Node{Name: "a"}
b := &graph.Node{Name: "b"}
c := &graph.Node{Name: "c"}
// a
// ⤢ ⤡
// b ↔ c
graph.MeshNodes(a, b, c)
fmt.Println("a to b:", a.HasPath(b))
fmt.Println("b to a:", b.HasPath(a))
fmt.Println("a to c:", a.HasPath(c))
fmt.Println("c to a:", c.HasPath(a))
fmt.Println("b to c:", b.HasPath(c))
fmt.Println("c to b:", c.HasPath(b))
}
Output: a to b: true b to a: true a to c: true c to a: true b to c: true c to b: true
func SetAttribute ¶
func SetAttribute[T any](attrs Attributes, name string, value T)
SetAttribute is a helper function to set a named attribute.
func UseAttribute ¶
func UseAttribute[T any](attrs Attributes, name string, fn func(T)) error
UseAttribute is a helper function to use a named attribute of a specific type.
func WithAttributes ¶
func WithAttributes(attrs Attributes) func(*Instance)
WithAttributes is a functional option that sets the attributes of the graph.
Types ¶
type AddEdge ¶
type AddEdge struct {
From *Node
Direction *EdgeDirection
To *Node
}
type Attributes ¶
Attributes are named values that can be associated with a node or subgraph.
type Clique ¶
type Clique = NodeSet
Clique is a subset of nodes in a graph such that every two distinct nodes in the set are adjacent.
type Cliques ¶
type Cliques []Clique
Cliques is a collection of clique node sets.
func FindCliques ¶
FindCliques handles finding all "cliques" within a graph. A a clique is a subset of nodes in a graph such that every two distinct nodes in the clique are adjacent. That is, a clique of a graph "G" is an induced subgraph of "G" that is complete.
Example
b
↙ ↖
c a
↙ ↘ ↗
e → d
Cliques: [1] {c, e, d}
References - https://en.wikipedia.org/wiki/Clique_(graph_theory) - https://en.wikipedia.org/wiki/Induced_subgraph - https://en.wikipedia.org/wiki/Complete_graph - https://mathworld.wolfram.com/Clique.html
func (Cliques) ContainsClique ¶
func (Cliques) ContainsNode ¶
type Edge ¶
type Edge struct {
Name string
Node *Node
Direction EdgeDirection
Attributes
}
Edge is a relationship with a Node, which can be directed if the edge is an "in" or "out" (directed) or neither (undirected).
type EdgeDirection ¶
type EdgeDirection int
EdgeDirection describes the "direction" of an edge relative to a node. A direction can be in one of five states:
- Unknown
- None
- In
- Out
- Both
const ( Unknown EdgeDirection = 0 // [ ┄ ] Edge has an unknown direction. None EdgeDirection = 1 // [ - ] Edge has no direction, is undirected. In EdgeDirection = 2 // [ ← ] Edge has inward direction. Out EdgeDirection = 3 // [ → ] Edge has outward direction. Both EdgeDirection = 4 // [ ↔ ] Edge has both inward and outward direction. )
func (EdgeDirection) AnyOf ¶
func (d EdgeDirection) AnyOf(directions ...EdgeDirection) bool
AnyOf checks if the edge direction is any of the given directions.
func (EdgeDirection) Match ¶
func (d EdgeDirection) Match(direction EdgeDirection) bool
Match checks if the edge direction matches the given edge direction, either exactly, or implicitly.
- Unknown ┄ : ┄
- None - : -, ↔
- In ← : ←, ↔
- Out → : →, ↔
- Both ↔ : ↔, ←, →
func (EdgeDirection) String ¶
func (d EdgeDirection) String() string
String returns a human and command-line friendly representation of the edge direction.
type Edges ¶
type Edges []*Edge
Edges is a collection of Node relationships.
func (Edges) AdjacentNodes ¶
func (Edges) AdjacentTo ¶
func (Edges) ButNotWith ¶
type Instance ¶
type Instance struct {
// Name is the name of the graph instance.
Name string
// Attributes is a map of key-value pairs that describe the graph instance.
Attributes
// Nodes is a slice of nodes that belong to the graph instance.
Nodes
}
Instance describes a graph of zero or more nodes.
func (*Instance) AddEdge ¶
AddEdge adds an edge to the graph from the source node to the target node.
func (*Instance) IsBipartite ¶
IsBipartite returns true if the nodes in the graph is a Bipartite graph, also called a bigraph, where nodes can be decomposed into two disjoint sets such that no two nodes within the same set are adjacent.
func (*Instance) IsMultipartite ¶
func (*Instance) IsUnicyclic ¶
IsUnicyclic returns true if the graph contains only a single cycle.
type Node ¶
type Node struct {
// The (unique) name (or label).
Name string
// Adjacency list of edges.
Edges
// Named attributes about the node.
Attributes
}
Node is the base unit of which graphs are formed.
Example ¶
package main
import (
"fmt"
"github.com/picatz/graph"
)
func main() {
a := &graph.Node{Name: "a"}
b := &graph.Node{Name: "b"}
a.AddEdge(b)
fmt.Println(a.Edges[0].Node.Name)
}
Output: b
func NewNode ¶
func NewNode(name string, attrs Attributes) *Node
NewNode returns a new node with the given name and attributes.
func (*Node) AddEdge ¶
AddEdge adds a directed relationship to a Node.
n → e
To control the direction used for the relationship, use the AddEdgeWithDirection method.
func (*Node) AddEdgeWithDirection ¶
func (n *Node) AddEdgeWithDirection(e *Node, direction EdgeDirection)
AddEdgeWithDirection adds a potentially directed relationship to a Node. The direction is up to the caller of the function. A corresponding edge is automatically added added; that is, if an "out edge" is added, an "in edge" is added on the other side of the edge relationship. This allows for the relationships to be bi-directionally walked from any point in the graph.
func (*Node) AddLink ¶
AddLink adds a bi-directional relationship to a Node.
Note: while this is sometimes rendered with a single "↔" (Both),
this method really defines two distinct edges using the
In and Out direction.
n ↔ e : [ n → e, e → n ]
func (*Node) HasCycleContaining ¶
HasCycleContaining checks if the Node is part of a cycle that contains the given node.
func (*Node) HasCycles ¶
HasCycles checks if the Node is part of a cycle. A cycle of a graph is a subset of the edge set of a graph that forms a path such that the first node of the path corresponds to the last.
Example of Cycle ¶
a → b → c → a
Example of Non-Cycle ¶
a → b → c
https://mathworld.wolfram.com/GraphCycle.html https://en.wikipedia.org/wiki/Cycle_(graph_theory)
func (*Node) HasPath ¶
HasPath checks if there is a Path to the given end Node.
root node f end node
┌──────── ↗ ┌───────
a → b → c → e i → e
↓ ↘ ↗
d g → h
Path: a → b → c → e → g → h → i → e
func (*Node) PathToWithout ¶
PathToWithout checks if there's a path to the given end node, without having to "go through" or "use" the other given node.
func (*Node) Visit ¶
Visit walks the outward nodes using a depth-first-search.
root node ┌──────── 1. Start at root "a" 1 a e 5 2. Go to edge node "b" ↑ ⤡ 3 4 ⤢ ↑ 3. Go to edge node "c" | c ↔ d | 4. Go to edge node "d" ↓ ⤢ ⤡ ↓ 5. Go to edge node "e" 2 b f 6 6. Go to edge node "f"
Example ¶
package main
import (
"fmt"
"github.com/picatz/graph"
)
func main() {
a := &graph.Node{Name: "a"}
b := &graph.Node{Name: "b"}
c := &graph.Node{Name: "c"}
graph.AddEdges(
graph.AddEdge{From: a, To: b},
graph.AddEdge{From: b, To: c},
graph.AddEdge{From: c, To: a},
)
a.Visit(func(n *graph.Node) {
fmt.Println(n.Name)
})
}
Output: a b c
type NodeSet ¶
type NodeSet map[*Node]struct{}
NodeSet is a collection of uniqe Node objects. Meant to be useful for algorithms that require collections of nodes that should not have repeated sequences.
Also particularly useful for recording visited nodes during graph traversal.
func NewNodeSet ¶
NewNodeSet returns a new NodeSet that includes the given nodes.
func (NodeSet) IsAdjacentWith ¶
IsAdjacentWith returns true if the given node is adjacent to all the other given nodes.
type NodeSets ¶
type NodeSets []NodeSet
NodeSets is a collection of NodeSet objects.
func (NodeSets) GetSetNotAdjacentWith ¶
GetSetNotAdjacentWith returns the NodeSet that is not adjacent to the given nodes.
type Nodes ¶
type Nodes []*Node
Nodes is a collection of Node objects.
type Path ¶
type Path Nodes
Path is an ordered set of Nodes that make a path from the start, the first element in the slice, to the end, the last element in the slice.
func FindBridges ¶
FindBridges finds all "bridge" paths within a graph. An edge, part of a path, is a bridge if and only if it is not contained in any cycle. Therefore, a bridge cannot be a cycle chord.
A "bridge" is also known as an "isthmus", "cut-edge", or "cut arc".
a ← d
↙ ↖
e → b → c Bridges (3): e → b, f → b, d → a
↑
f
a e
↑ ⤡ ⤢ ↑
| c → d | Bridges (1): c → d
↓ ⤢ ⤡ ↓
b f
To find the bridges in a graph, we need to visit each node and determine if it contains an edge that, if removed, would disconnect the graph into two. This is, if the number of components increases.
A bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle.
References - https://en.wikipedia.org/wiki/Bridge_(graph_theory) - https://en.wikipedia.org/wiki/Strongly_connected_component - https://mathworld.wolfram.com/GraphBridge.html
func (Path) ContainsNode ¶
ContainsNode checks if the given node is part of the path.
type Paths ¶
type Paths []Path
Paths is a collection of Path nodes.
func (Paths) ContainsNode ¶
ContainsNode checks if the given node is contained in any one of the path node sets.
func (Paths) ContainsPath ¶
ContainsPath checks if the given path is identical to any of one of the path node sets.
Source Files