2
GitHub - lucastomic/go-graph-explorer: Graph exploration
source link: https://github.com/lucastomic/go-graph-explorer
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
go-graph-explorer
go-graph-explorer is a library for graph exploration.
Currently support the next algorithms:
- BranchAndBonud
- DepthFirst
- Climbing
- Amplitude
- BestFirst
Install
go get -u github.com/lucastomic/go-graph-explore
Usage
Import the go-graph-explorer package
import (
"github.com/lucastomic/go-graph-explorer/pkg/explorator/explorationAlgorithm/enums/informedAlgorithm"
"github.com/lucastomic/go-graph-explorer/pkg/explorator/explorationAlgorithm/enums/uninformedAlgorithm"
"github.com/lucastomic/go-graph-explorer/pkg/explorator/explorer"
)
Define the graph we want to explore:
var maxF float64 = math.MaxFloat64
var testGraph [][]float64 = [][]float64{
{maxF, 0.5, 0.5, maxF, maxF, 0.5},
{0.5, maxF, maxF, 2.5, 5, maxF},
{0.5, maxF, maxF, maxF, maxF, maxF},
{maxF, 2.5, maxF, maxF, 2, maxF},
{maxF, 5, maxF, 2, maxF, maxF},
{0.5, maxF, maxF, maxF, maxF, maxF},
}
Define our heuristic
// Heuristic which dislikes 1
type Dislike1Heur struct{}
func (h Dislike1Heur) Heuristic(state int) float64 {
if state == 1 {
return 10
} else {
return 1
}
}
Define the solution condition
type ThreeSolution struct {
}
func (s ThreeSolution) IsSolution(state int, graph [][]float64) bool {
return state == 3
}
and finally explore the graph. We can do it with an informed algorithm
res, _ := explorer.ExploreWithInformed(testGraph, ThreeSolution{}, Dislike1Heur{}, 5, informedAlgorithm.AStar)
// explorer.ExploreWithInformed(testGraph, ThreeSolution{}, Dislike1Heur{}, 5, informedAlgorithm.Climbing)
// explorer.ExploreWithInformed(testGraph, ThreeSolution{}, Dislike1Heur{}, 5, informedAlgorithm.BestFirst)
fmt.Println(res.ToString())
or with a uninformed one
res2, _ := explorer.ExploreWithUninformed(testGraph, ThreeSolution{}, 5, uninformedAlgorithm.Amplitude)
// explorer.ExploreWithUninformed(testGraph,ThreeSolution{},5,uninformedAlgorithm.DepthFirst)
// explorer.ExploreWithUninformed(testGraph,ThreeSolution{},5,uninformedAlgorithm.BranchAndBonud)
fmt.Println(res2.ToString())
Output:
5 -> 0 -> 1 -> 3
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK