DEV Community: stevensonmt

Prim's algorithm in Elixir

stevensonmt — Fri, 06 May 2022 02:59:20 +0000

Prim's algorithm is a greedy algorithm for finding the lowest cost tree that includes all nodes of a graph, also called a minimum spanning tree. There are lots of blog posts and tutorials out there about implementing this, but I found it difficult to find information on implementations in functional languages or a functional style with immutable data structures.

In the implementation below, the nodes of the graph are given as an unordered list. I found it easiest to work with the list as a tuple that could be accessed by index. The collection of nodes is not going to be mutated (no additions or insertions) but is going to be frequently accessed. Because accessing a tuple by index is quite fast I felt this was a good approach. That said, it is not necessary and may actually make this less "functional" in style.

In Prim's algorithm you need two mathematical sets -- the set of all visited nodes (i.e., the nodes included in the minimum spanning tree) and the set of all nodes in the graph. You choose an arbitrary node to start and iterate over the unvisited nodes to find the minimum distance to connect to the MST. The algorithm is completed when these two sets are equivalent. In the implementation below I have chosen to simply track the set of unvisited nodes, with the algorithm being complete when the set is empty. This is because in this case I'm only interested in the cost of the MST, not the MST itself. If I needed to return the MST I would track the visited nodes alongside the original set of nodes.

You also need a way to know the cost of any edge in the graph. In this case I am assuming the graph is given as a series of {x, y} coordinate pairs and the weight of an edge is given by the Manhattan distance between them.

To begin we instantiate the set of unvisited nodes, the running "cost" of the minimum spanning tree, and a priority queue. In this instance I'm using a general balanced tree as the priority queue structure. I know they are not exactly equivalent, but Erlang has builtin GBT and I did not want to implement a priority queue from scratch.

The keys of the GBT are the distances, and the values of the GBT are a list of nodes that connects with at least one edge at that key distance. Because I'm using a GBT as a queue and the keys must be unique, if I don't use a list as the value of each GBT node the queue will drop nodes and end up being incorrect. This is the only issue I encountered with using GBT as the priority queue.

  def min_cost_connect_points(points) do
    vertices = 
      points 
      |> Enum.with_index() 
      |> Enum.map(fn {pt, i} -> {i, pt} end) 
      |> Enum.into(%{})

    len = length(points)

    candidates = MapSet.new(0..len - 1) 
# This will be our set of unvisited nodes, well, indices
# of nodes.

    queue = :gb_trees.enter(0, [0], :gb_trees.empty()) 
# We initiate the priority queue with an arbitrary node 
# that has a minimum distance of zero. The node index is
# wrapped in a list and entered into the GBT with key 0.

    cost = 0
    do_prims(vertices, candidates, queue, cost)
  end

  defp do_prims(vertices, candidates, queue, cost) do 
    if MapSet.size(candidates) == 0 do
# When the set of unvisited nodes (`candidates`) is 
# empty we're done.
      cost
    else
      {min_dist, [next_vertex | rest], new_queue} =
        :gb_trees.take_smallest(queue) 
# take_smallest/1 returns a 3 tuple of {key, value, new_tree}
# where the new_tree is the original tree with the node that 
# has the smallest key removed.
# The next line is necessary to avoid 'deduplicating' the 
# queue of nodes that have min_dist as a potential edge cost.
# Arbitrarily taking the head of the list does not impact the
# correctness of the algorithm.
      new_queue = if rest == [] do
                    new_queue
                  else 
# If multiple nodes have an edge where distance == min_dist,
# we need to put the min_dist key back in the queue with the
# rest of those nodes as the value.
                    :gb_trees.enter(min_dist, rest, new_queue)
                  end
      if not MapSet.member?(candidates, next_vertex) do 
# If the node we chose as the current smallest distance edge
# from the queue has already been visited (i.e., removed from
# the candidates set), then we skip next_vertex and try again
        do_prims(vertices, candidates, new_queue, cost)
      else
# If next_vertex has not been visited yet, we mark it as
# visited and update the queue with edges connecting to
# next_vertex. Note that while the queue may include edges
# that would be discarded due to involved nodes already
# having been visited, this step will only ever introduce
# edges for nodes that have not been visited yet.
        candidates = MapSet.delete(candidates, next_vertex)
        updated_queue = 
          candidates
          |> Enum.reduce(new_queue, fn i, q -> 
               d = 
                 distance(vertices[i], vertices[next_vertex])
# Here's where :gb_trees could really use an ergonomic
# update_or_insert function. There is an update/3 but it
# crashes if the key is not present. It also does not take
# a function as a parameter for the update, so it is less an
# update as a replace method. That's why we first check if the
# distance is already a key in the GBT. If it is, we have to
# get the value of that key and add the current node to the
# list. Otherwise we can just wrap the current node in a list.
               is = if :gb_trees.is_defined(d, q) do
                      is = :gb_trees.get(d, q)
                      [i | is]
                    else
                      [i]
                    end
               :gb_trees.enter(d, is, q)
             end)
# We have updated the candidates list and the queue, so we 
# recurse with the updated cost.
        do_prims(vertices, 
                 candidates, 
                 updated_queue, 
                 cost + min_dist)
      end
    end
  end

  defp distance([a, b], [c, d]), do: abs(a - c) + abs(b - d)

I hope someone finds this helpful. If anyone has tips on optimizations or corrections to my understanding of Prim's algorithm I'd love to hear them. Thanks for reading!

Working with menus in elm-ui

stevensonmt — Mon, 31 Dec 2018 02:56:17 +0000

Recently had to figure out how to get a modal sort of menu to open and close correctly using the mdgriffith/elm-ui package in Elm 0.19. For those unfamiliar, the elm-ui package allows you to create front-end interfaces without resorting to CSS or HTML (with occasional exceptions). If you are working in Elm, I highly recommend it. If you aren't working in Elm yet, I would point to elm-ui as one of its selling points and a reason to try it out.

Here is the very basic concept in an ellie.
Our simple model has two fields: count and menu. It is defined thus:

type alias Model =
    { count : Int, menu : Bool }


initialModel : Model
initialModel =
    { count = 0, menu = False }

Here is the view code:

view : Model -> Html Msg
view model =
    Element.layout [ Element.Background.color (Element.rgb255 30 30 30), padding 10]
    <| column [spacing 10, width <| px 200, Element.Background.color (Element.rgb255 200 30 10)] 
           [ el [ width fill
                , padding 8
                , Element.Font.center
                , Element.Background.color <| 
                      Element.rgb255 120 120 180
                ] <| 
                     Element.text (String.fromInt model.count)
           , el [ centerX
                , Element.Events.onClick OpenMenu
                , Element.below <| myMenu model
                ] <| 
                    Element.text "I'm a menu!"
           ]

And finally our Msgs and update function fill out the Elm Architecture for our demo app:

type Msg
    = Increment
    | Decrement
    | OpenMenu
    | CloseMenu


update : Msg -> Model -> Model
update msg model =
    case msg of
        Increment ->
            { model | count = model.count + 1 }

        Decrement ->
            { model | count = model.count - 1 }

        OpenMenu -> 
            { model | menu = True }

        CloseMenu -> 
            { model | menu = False }

If you try the ellie link you'll find that the menu opens to reveal the buttons for incrementing and decrementing the model count. Easy peasy. BUT the menu stays open. The first step to fix that is to change the menu element's onClick attribute from an OpenMenu action to a ToggleMenu action.
So now we have

type Msg
    = Increment
    ...
    | ToggleMenu

update : Msg -> Model -> Model
update msg model =
    case msg of
       ...
        ToggleMenu -> { model | menu = not model.menu }

view : Model -> Html Msg
view model =
    ...
    , el [ centerX
                , Element.Events.onClick ToggleMenu
                , Element.below <| myMenu model
                ] <| 
                    Element.text "I'm a menu!"
    ...

Sweet! Now the menu opens and closes when the triggering element is clicked. See the updated version here. But lots of users will probably expect the menu to close when any other part of the viewport is clicked. Here is the first way I thought of setting that up:

view : Model -> Html Msg
view model =
    Element.layout [ Element.Events.onClick CloseMenu
    ...

This should mean that clicking anywhere sends the CloseMenu Msg. See the problem with this approach here. Try to launch the menu and then open the debugger.

What you see is that clicking the menu sends the ToggleMenu Msg just like we want, but it is immediately followed by the CloseMenu Msg. This leads to the menu never opening. Ugggh.

The reason for this is that onClick events are propagated from child elements to parent elements. And we can't just use the ToggleMenu fix on the layout because that would open the menu anytime you click anywhere.

There are almost certainly many ways to get around this, but the way I hit upon was to put an empty element the size of layout behind the content of the layout using the cleverly named function Element.behindContent. Giving this element an onClick CloseMenu attribute works because it is not in a parent-child relationship with the menu elements.

This approach works okay but there's still a couple of glitches. See it in action here. The most obvious glitch in terms of the problem of getting the menu to close is that the element displaying the counter is not sending the CloseMenu Msg when clicked because it is in front and not a child element of the element we just added. My solution was to add the onClick CloseMenu attribute to that element. I'd be interested to hear more elegant solutions though!

The second obvious hiccup to me is that the menu closes each time you increment or decrement the count. I think most users would expect the menu to stay open until they were done incrementing/decrementing the count as many times as they wanted. I'll leave the solution to that as an exercise for anyone interested.

Thanks for reading. I hope you found it helpful. If you have questions about Elm or elm-ui I highly recommend the Elm Discourse and the Elm and elm-ui Slack channels.

Making impossible things impossible in Rust

stevensonmt — Wed, 06 Jun 2018 16:40:48 +0000

I watched Richard Feldman's talk Making Impossible States Impossible a while back when I was learning a little bit of Elm. I'm not sure I understood the execution described in his talk, but the concept of making errors literally impossible with correct data structures stuck with me. I'm in the middle of what is my most ambitious Rust project to date and struggling to get that proper data structure.

The problem centers around needing to create search strings for a web API that applies to 30+ database sets, each with unique but overlapping available search fields up to the 70s. I need it to be impossible to select an inappropriate field for a given database.

In the genericized code below I'd like to share a couple of approaches that have become clear to me as I go through this design process. In doing so I hope to improve my own understanding and hopefully that of others with regards to type safety, implementation of traits, and data structures in Rust.

enum Foo {
    Foo1(Foo1Field),
    Foo2(Foo2Field),
}

enum Foo1Field {
    Foo1Field1,
    Foo1Field2,
}

enum Foo2Field {
    Foo2Field1,
    Foo2Field2,
}

struct Bar {
    foo: Foo
}

With this organization you know that every Bar instance will always have a "field" type appropriate to the variant of Foo assigned. It's a little cumbersome to try and access those "fields" though. This is in part because the tuples of Foo1 and Foo2 are of different types.

An alternative is making more use of traits.

enum Foo1Field {
    Foo1Field1,
    Foo1Field2,
}

enum Foo2Field {
    Foo2Field1,
    Foo2Field2,
}

trait Foo {}

impl Foo for Foo1Field {}
impl Foo for Foo2Field {}

struct Bar<T: Foo> {
    foo: T
}

With this structure I no longer need a Foo enum, I just need the "field" enums to implement the Foo trait. The Bar struct now takes any enum that implements the Foo trait for its foo field. Accessing the field values is now trivial.

let bar = Bar { foo: Foo1Field::Foo1Field1 };
bar.foo // returns Foo1Field1 //
let bar2 = Bar { foo: Foo2Field::Foo2Field2 };
bar2.foo // returns Foo2Field2

This also allows me to add fields to various database sets without duplicating fields. I simply implement a trait for the new set. Hopefully others will find this helpful. I look forward to hearing additional insights or suggestions for alternative approaches to this type of problem. Thanks for reading.

Naming Nested For Loops in Rust

stevensonmt — Thu, 10 May 2018 13:27:06 +0000

I've been aware of the ability to name for loops in rust for a while, but a recent project made me consider how that can make code more readable. It almost can take the place of a separate comment. My project took a string of variable length and looked for sets of keywords, trying to return the most relevant match. Some keywords and positions would carry more weight in determining relevancy.

'clauses: for clause in text.split(";") {
    'phrases: for phrase in clause.split(",") {
        'words: for word in phrase.split_whitespace() {
            'mainkeywords: for mainkey in MAIN_KEYS.iter() {
                match word.find(mainkey) {
                    Some(_) => { dostuff(word);
                                 break 'phrases 
                               },
                    _ => 'secondarykeys: for key in SECONDARY_KEYS.iter() {
                             match key.find(word) {
                                                   Some(_) => do_other_stuff(word);
                                                   break 'words 
                                                  }
                 }
              }
           }
       }
    }

Naming the loops can have the same effect as comments while providing some useful function. I hadn't seen naming loops as a code organization/readability tool mentioned before and though I'd share. If anyone has comments on this approach in general or the code above specifically I'd love to hear them.

Hi, I'm stevensonmt

stevensonmt — Fri, 03 Feb 2017 04:54:10 +0000

I have been coding for a few years.

You can find me on GitHub as stevensonmt

I live in the Pacific NW.

I am an amateur coder with a day job tangentially related to software.

I mostly program in these languages: ruby, html, css, crystal, rust, elm.

I am currently learning more about rust and elm while getting a firmer grasp on core concepts such as recursion and the differences between functional and imperative programming. I would like to learn elixir at some point.

Nice to meet you.