algos

Module, respectively collection of go packages concerning data structures and related algorithms.

Data Structues

Currently implemented are

Stack (LIFO)
Ring Buffer (FIFO)
Linked List
Heap
Graph

Stack (LIFO)

func ExampleStack() {
  // Create stack and initially push some elements -> 10 on top
  s := stack.NewStack(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  s.Push(20)             // pushes 20 on top of the stack
  fmt.Println(s.Pop())   // pop top element (ouputs 20)
  fmt.Println(s.Peek(0)) // peek on top element without removing it from stack (outputs 10)
  // Output:
  // 20
  // 10
}

Ring Buffer (FIFO)

func ExampleNewRingBufferWithFixedCapacity() {
  // Creates ring buffer (FIFO) with fixed capacity of 5 elements
  rFixed := ringbuffer.NewRingBufferWithFixedCapacity[int](5)
  // Push 5 elements into the ring buffer
  rFixed.Push(1, 2, 3, 4, 5)
  rFixed.Push(6) // pushing another element 6 drops element 1, because ring buffer is full
  for rFixed.Len() > 0 {
    fmt.Printf("%v ", rFixed.Pop())
  }
  // Output: 2 3 4 5 6
}

💡 Using NewRingBuffer() instead of NewRingBufferWithFixedCapacity(capacity int) creates a ring buffer that dynamically grows and won't drop elements.

Linked List (singly linked)

func Example() {
  // Create linked list and return head element
  l1 := linkedlist.NewElement(1, 2, 3, 4)
  l5 := linkedlist.NewElement(5)
  l6 := linkedlist.NewElement(6, 7, 8, 9)
  l5.InsertBefore(l1)
  l5.InsertAfter(l6)

  next := l1
  for i := 1; next != nil; i++ {
    fmt.Printf("%v,", next.Data)
    next = next.Next()
  }
  // Output: 1,2,3,4,5,6,7,8,9,
}

Heap

func Example() {
  // Create new heap with providing an appropricate less function and the heap's inital elements
  h := heap.NewMaxHeap(func(a int, b int) bool { return a < b }, 10, 20, 15, 12, 40, 25, 18, 19)

  // Heap then looks like this:
  //        ___40___
  //       /        \
  //     25          19
  //    /  \        /  \
  //  20    10    18    15

  fmt.Println(h.Peek()) // In a max heap the first element is always the biggest
  fmt.Println(h.Sort()) // Sort the heap's slice. This method breaks the heap
  h.Heapify()           // Heapify repairs the heap's order e.g. after calling Sort method
  h.Push(99)
  // Pop all elements until heap is empty
  for h.Len() > 0 {
    e := h.Pop()
    fmt.Printf("%v ", e)
  }
  // Output:
  // 40
  // [10 12 15 18 19 20 25 40]
  // 99 40 25 20 19 18 15 12 10
}

Graph

Traversal via DFS & BFS (Depth First Search & Breadth First Search)

func Example_graph_traversal() {
  // See this great video about graph traversal: https://youtu.be/TIbUeeksXcI
  //
  //      G_____A_____H
  //     /     / \   /
  //    /     /   \ /
  //   F     C_____B
  //    \   /     /
  //     \ /     /
  //      D_____E

  A, B, C, D, E, F, G, H :=
    graph.NewNode("A"), graph.NewNode("B"), graph.NewNode("C"),
    graph.NewNode("D"), graph.NewNode("E"), graph.NewNode("F"),
    graph.NewNode("G"), graph.NewNode("H")

  graph.LinkNodes(true, graph.LinkMap[string]{
    A: {{G, 1}, {C, 2}, {B, 3}, {H, 4}},
    B: {{E, 1}, {C, 2}, {H, 3}},
    C: {{D, 1}},
    D: {{F, 1}, {E, 2}},
    F: {{G, 0}},
  })
  fmt.Println(A)
  fmt.Println(B)
  fmt.Println(C)
  fmt.Println(D)
  fmt.Println(E)
  fmt.Println(F)
  fmt.Println(G)
  fmt.Println(H)

  // Traverse the graph
  visitFunc := func(n *graph.Node[string]) {
    fmt.Println(n)
  }
  fmt.Println("Traversing graph via DFS:")
  A.DepthFirstSearch(visitFunc)

  fmt.Println("Traversing graph via BFS:")
  A.BreadthFirstSearch(visitFunc)
  // Output:
  // A -> [G(1) C(2) B(3) H(4)]
  // B -> [E(1) C(2) H(3) A(3)]
  // C -> [D(1) A(2) B(2)]
  // D -> [F(1) C(1) E(2)]
  // E -> [B(1) D(2)]
  // F -> [G(0) D(1)]
  // G -> [F(0) A(1)]
  // H -> [B(3) A(4)]
  // Traversing graph via DFS:
  // A -> [G(1) C(2) B(3) H(4)]
  // G -> [F(0) A(1)]
  // F -> [G(0) D(1)]
  // D -> [F(1) C(1) E(2)]
  // C -> [D(1) A(2) B(2)]
  // B -> [E(1) C(2) H(3) A(3)]
  // E -> [B(1) D(2)]
  // H -> [B(3) A(4)]
  // Traversing graph via BFS:
  // A -> [G(1) C(2) B(3) H(4)]
  // H -> [B(3) A(4)]
  // B -> [E(1) C(2) H(3) A(3)]
  // C -> [D(1) A(2) B(2)]
  // G -> [F(0) A(1)]
  // E -> [B(1) D(2)]
  // D -> [F(1) C(1) E(2)]
  // F -> [G(0) D(1)]
}

Dijkstra Path Search Algorithm

func Example_dijkstra() {
  //
  //  O _____ N _____ J       _______ C _____ E _____ Z
  //   \  ⁷  /    ⁶  / \     /       / \  ⁶  /    ⁷  /
  //  ¹⁰\   /⁵      /⁵  \₄  /³     ₉/  ₄\   /¹⁰     /₁₁
  //     \ /       /     \ /       /     \ /       /
  //      M       I       A _____ B       D _____ F
  //     /       / \     / \  ¹  /       /    ⁷
  //   ₃/       /⁵  \₃  /²  \₅  /²     ₂/
  //   /       /     \ /     \ /       /
  //  L _____ K       H       S _____ G
  //      ⁶                       ⁴

  E, F, C, D, G, B, S, A, H, J, I, K, L, M, N, O, Z :=
    graph.NewNode(NewHNode("E", 7)), graph.NewNode(NewHNode("F", 10)),
    graph.NewNode(NewHNode("C", 11)), graph.NewNode(NewHNode("D", 15)),
    graph.NewNode(NewHNode("G", 20)), graph.NewNode(NewHNode("B", 20)),
    graph.NewNode(NewHNode("S", 22)), graph.NewNode(NewHNode("A", 21)),
    graph.NewNode(NewHNode("H", 23)), graph.NewNode(NewHNode("J", 25)),
    graph.NewNode(NewHNode("I", 26)), graph.NewNode(NewHNode("K", 28)),
    graph.NewNode(NewHNode("L", 30)), graph.NewNode(NewHNode("M", 32)),
    graph.NewNode(NewHNode("N", 28)), graph.NewNode(NewHNode("O", 32)),
    graph.NewNode(NewHNode("Z", 0))

  graph.LinkNodes(true, graph.LinkMap[*HNode]{
    Z: {{E, 7}, {F, 11}},
    D: {{E, 10}, {F, 7}, {C, 4}, {G, 2}},
    B: {{C, 9}, {S, 2}, {A, 1}},
    S: {{G, 4}, {A, 5}},
    A: {{C, 3}, {H, 2}, {J, 4}},
    I: {{J, 5}, {H, 3}, {K, 5}},
    N: {{J, 6}, {M, 0}, {O, 7}},
    L: {{M, 3}, {K, 6}},
  })
  route, steps := S.Dijkstra(Z)
  fmt.Printf("total costs %v: %v (visited nodes: %v)\n", route.TotalCosts(), route, steps)
  // Output:
  // total costs 23: [S(22)(0) G(20)(4) D(15)(2) E(7)(10) Z(0)(7)] (visited nodes: 40)
}

A* Path Search Algorithm

type HNode struct {
  name      string
  heuristic int
}

func NewHNode(name string, heuristic int) *HNode {
  return &HNode{name, heuristic}
}

func (hn *HNode) String() string {
  return fmt.Sprintf("%v(%v)", hn.name, hn.heuristic)
}

func Example_astar() {
//
  //  O _____ N _____ J       _______ C _____ E _____ Z
  //   \  ⁷  /    ⁶  / \     /       / \  ⁶  /    ⁷  /
  //  ¹⁰\   /⁵      /⁵  \₄  /³     ₉/  ₄\   /¹⁰     /₁₁
  //     \ /       /     \ /       /     \ /       /
  //      M       I       A _____ B       D _____ F
  //     /       / \     / \  ¹  /       /    ⁷
  //   ₃/       /⁵  \₃  /²  \₅  /²     ₂/
  //   /       /     \ /     \ /       /
  //  L _____ K       H       S _____ G
  //      ⁶                       ⁴

  E, F, C, D, G, B, S, A, H, J, I, K, L, M, N, O, Z :=
    graph.NewNode(NewHNode("E", 7)), graph.NewNode(NewHNode("F", 10)),
    graph.NewNode(NewHNode("C", 11)), graph.NewNode(NewHNode("D", 15)),
    graph.NewNode(NewHNode("G", 20)), graph.NewNode(NewHNode("B", 20)),
    graph.NewNode(NewHNode("S", 22)), graph.NewNode(NewHNode("A", 21)),
    graph.NewNode(NewHNode("H", 23)), graph.NewNode(NewHNode("J", 25)),
    graph.NewNode(NewHNode("I", 26)), graph.NewNode(NewHNode("K", 28)),
    graph.NewNode(NewHNode("L", 30)), graph.NewNode(NewHNode("M", 32)),
    graph.NewNode(NewHNode("N", 28)), graph.NewNode(NewHNode("O", 32)),
    graph.NewNode(NewHNode("Z", 0))

  graph.LinkNodes(true, graph.LinkMap[*HNode]{
    Z: {{E, 7}, {F, 11}},
    D: {{E, 10}, {F, 7}, {C, 4}, {G, 2}},
    B: {{C, 9}, {S, 2}, {A, 1}},
    S: {{G, 4}, {A, 5}},
    A: {{C, 3}, {H, 2}, {J, 4}},
    I: {{J, 5}, {H, 3}, {K, 5}},
    N: {{J, 6}, {M, 0}, {O, 7}},
    L: {{M, 3}, {K, 6}},
  })
  route, steps := S.AStar(Z, func(n *graph.Node[*HNode]) int {
    return n.Data.heuristic
  })
  fmt.Printf("total costs %v: %v (visited nodes: %v)\n", route.TotalCosts(), route, steps)
  // Output:
  // total costs 23: [S(22)(0) G(20)(4) D(15)(2) E(7)(10) Z(0)(7)] (visited nodes: 8)
}

mfmayer / algos Goto Github PK

algos's Introduction

algos

Data Structues

Stack (LIFO)

Ring Buffer (FIFO)

Linked List (singly linked)

Heap

Graph

Traversal via DFS & BFS (Depth First Search & Breadth First Search)

Dijkstra Path Search Algorithm

A* Path Search Algorithm

algos's People

Contributors

Stargazers

Watchers

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent