그래프: 일반 그래프 데이터 구조를 생성하고 이를 수정, 분석 및 시각화하기 위한 라이브러리입니다.

graph은 일반 그래프 데이터 구조를 생성하고 이를 수정, 분석 및 시각화하기 위한 Go 라이브러리입니다.

특징

int 또는 City 와 같은 모든 유형의 일반 정점.

비순환 그래프의 주기 확인과 같은 해당 유효성 검사가 포함된 그래프 특성.

최단 경로 또는 강하게 연결된 구성 요소와 같은 경로 또는 구성 요소를 찾기 위한 알고리즘입니다.

변환 및 표현을 위한 알고리즘(예: 전이 감소 또는 위상 순서).

DFS 또는 BFS와 같은 비재귀 그래프 순회를 위한 알고리즘입니다.

가중치 또는 사용자 정의 속성과 같은 선택적 메타데이터가 있는 에지.

DOT 언어 및 Graphviz를 사용한 그래프의 시각화.

적용 범위가 ~90%이고 종속성이 없는 광범위한 테스트입니다.

Status: Because graph is in version 0, the public API shouldn't be considered stable.

시작하기

go get github.com/dominikbraun/graph

빠른 예

정수 그래프 만들기

g := graph.New(graph.IntHash)

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)
g.AddVertex(4)
g.AddVertex(5)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 4)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(2, 5)
_ = g.AddEdge(3, 5)

정수의 방향성 비순환 그래프 생성

g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)
g.AddVertex(4)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(3, 4)

사용자 지정 유형의 그래프 만들기

이 예를 자세히 이해하려면 concept of hashes 을 참조하십시오.

type City struct {
    Name string
}

cityHash := func(c City) string {
    return c.Name
}

g := graph.New(cityHash)

g.AddVertex(london)

가중 그래프 만들기

g := graph.New(cityHash, graph.Weighted())

g.AddVertex(london)
g.AddVertex(munich)
g.AddVertex(paris)
g.AddVertex(madrid)

_ = g.AddEdge("london", "munich", graph.EdgeWeight(3))
_ = g.AddEdge("london", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("london", "madrid", graph.EdgeWeight(5))
_ = g.AddEdge("munich", "madrid", graph.EdgeWeight(6))
_ = g.AddEdge("munich", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("paris", "madrid", graph.EdgeWeight(4))

깊이 우선 검색 수행

이 예제는 DFS 순서로 그래프의 모든 정점을 순회하고 인쇄합니다.

g := graph.New(graph.IntHash, graph.Directed())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)
g.AddVertex(4)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(3, 4)

_ = graph.DFS(g, 1, func(value int) bool {
    fmt.Println(value)
    return false
})

1 3 4 2

강력하게 연결된 구성 요소 찾기

g := graph.New(graph.IntHash)

// Add vertices and edges ...

scc, _ := graph.StronglyConnectedComponents(g)

fmt.Println(scc)

[[1 2 5] [3 4 8] [6 7]]

최단 경로 찾기

g := graph.New(graph.StringHash, graph.Weighted())

// Add vertices and weighted edges ...

path, _ := graph.ShortestPath(g, "A", "B")

fmt.Println(path)

[A C E B]

토폴로지 정렬 수행

g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

// Add vertices and weighted edges ...

order, _ := graph.TopologicalSort(g)

fmt.Println(order)

[1 2 3 4 5]

비순환 그래프에 대한 주기 검사

g := graph.New(graph.IntHash, graph.Acyclic())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)

if err := g.AddEdge(2, 3); err != nil {
    panic(err)
}

panic: an edge between 2 and 3 would introduce a cycle

Graphviz를 사용하여 그래프 시각화

다음 예제는 g에 대한 DOT 설명을 생성하고 주어진 파일에 씁니다.

g := graph.New(graph.IntHash, graph.Directed())

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)

file, _ := os.Create("./mygraph.gv")
_ = draw.DOT(g, file)

Graphviz를 사용하여 생성된 파일에서 SVG를 생성하려면 다음과 같은 명령을 사용합니다.

dot -Tsvg -O mygraph.gv

에지 속성 설정

에지는 메타데이터를 저장하는 데 사용할 수 있는 하나 이상의 속성을 가질 수 있습니다. 속성이 사용됩니다.
visualizing a graph 때를 고려합니다. 예를 들어, 이 모서리
빨간색으로 렌더링됩니다.

_ = g.AddEdge(1, 2, graph.EdgeAttribute("color", "red"))

지원되는 모든 속성에 대한 개요를 보려면 다음을 살펴보십시오.
DOT documentation .

개념

해시

그래프는 T 유형의 노드(또는 정점)로 구성되며 유형의 해시 값으로 식별됩니다.K . graph.New에 전달된 해싱 함수를 사용하여 해시 값을 얻습니다.

기본 유형

string 또는 int 와 같은 기본 유형의 경우 다음과 같은 미리 정의된 해싱 함수를 사용할 수 있습니다.graph.IntHash – 정수를 가져와 동시에 해시 값으로 사용하는 함수:

g := graph.New(graph.IntHash)

This also means that only one vertex with a value like 5 can exist in the graph if
graph.IntHash used.

맞춤 유형

사용자 지정 데이터 유형을 저장하려면 고유한 해싱 함수를 제공해야 합니다. 이 예제 함수City를 취하고 도시 이름을 고유한 해시 값으로 반환합니다.

cityHash := func(c City) string {
    return c.Name
}

이 해싱 함수를 사용하여 그래프를 생성하면 정점 유형이 있는 그래프가 생성됩니다City.string 유형의 해시 값으로 식별됩니다.

g := graph.New(cityHash)

특성

예를 들어 에지를 추가하거나 검색할 때 그래프의 동작은 특성에 따라 다릅니다. 너
이 라이브러리에서 제공하는 기능 옵션을 사용하여 그래프의 특성을 설정할 수 있습니다.

g := graph.New(graph.IntHash, graph.Directed(), graph.Weighted())

선적 서류 비치

전체 문서는 pkg.go.dev에서 볼 수 있습니다.

GitHub에서 그래프 확인: dominikbraun/graph