Author Archives: steven.proctor@gmail.com

Erlang Thursday – digraph:in_neighbors/2

Today’s Erlang Thursday is on digraph:in_neighbors/2.

digraph:in_neighbors/2 takes a graph G, and a vertex V, and will return a list of all the vertices that have edges originating from them that are directed toward the vertex V.

We will continue working with the graph from last week’s post on digraph:get_path/3.

Graph = digraph:new().
% {digraph,20498,24595,28692,true}
V1 = digraph:add_vertex(Graph).
% ['$v'|0]
V2 = digraph:add_vertex(Graph).
% ['$v'|1]
V3 = digraph:add_vertex(Graph).
% ['$v'|2]
V4 = digraph:add_vertex(Graph).
% ['$v'|3]
E1 = digraph:add_edge(Graph, V1, V2).
% ['$e'|0]
E2 = digraph:add_edge(Graph, V2, V3).
% ['$e'|1]
E3 = digraph:add_edge(Graph, V3, V4).
% ['$e'|2]
E4 = digraph:add_edge(Graph, V2, V4).
% ['$e'|3]
E5 = digraph:add_edge(Graph, V4, V1).
% ['$e'|4]

With that graph setup again, we can now find the in_neighbors of different vertices in our graph.

digraph:in_neighbours(Graph, V4).
% [['$v'|1],['$v'|2]]
digraph:in_neighbours(Graph, V1).
% [['$v'|3]]
digraph:in_neighbours(Graph, V2).
% [['$v'|0]]

So for vertex V4 we see the return value of [['$v'|1],['$v'|2]], which are the vertices V2 and V3. For V1 we have an inbound neighbor of V4, and for V2 we have the inbound neighbor of V1.

digraph:out_neighbors/2

The digraph module also contains the function digraph:out_neighbors/2, which returns a list of the vertices that a the given vertex “points to” with its edges in the directed graph.

digraph:out_neighbours(Graph, V2).
% [['$v'|3],['$v'|2]]
digraph:out_neighbours(Graph, V4).
% [['$v'|0]]
digraph:out_neighbours(Graph, V1).
% [['$v'|1]]

We can see from the picture of our graph that V2 has edges that “point to” the vertices V3 and V4, and if we look at the result of digraph:out_neighbors/2, we get the result of the vertices V3 and V4.

In this case we get the list of vertices where V4 is first and V3 is second, but that may not be the case, as the documentation states that the the edges are “in some unspecified order”, which holds true of digraph:in_neighbors/2 as well.

–Proctor

Ruby Tuesday – Array#to_h

Today’s Ruby Tuesday is on Array#to_h.

Array#to_h will turn an Array of two element Arrays into a Hash where each two element Array represents a key value pair in the new Hash.

[[1, :a], [2, :b]].to_h
# => {1=>:a, 2=>:b}
[["cat", "meow"], ["dog", "woof"], ["mouse", "squeak"]].to_h
# => {"cat"=>"meow", "dog"=>"woof", "mouse"=>"squeak"}

If called on an Array that is not an Array of Arrays, you get a TypeError.

[1, 2, 3, 4].to_h
# TypeError: wrong element type Fixnum at 0 (expected array)
# from (pry):4:in `to_h'

If called on an Array that is an Array of Arrays, but the nested Arrays are not of length two, an ArgumentError is raised.

[[1, 2, 3], [2, 3, 4]].to_h
# ArgumentError: wrong array length at 0 (expected 2, was 3)
# from (pry):5:in `to_h'

The items in the nested arrays can be anything, even more Arrays, but those arrays will just be used as is.

[[1, [2, 3]], [[:a, :b], [3, 4]]].to_h
# => {1=>[2, 3], [:a, :b]=>[3, 4]}

–Proctor

Erlang Thursday – digraph:get_path/3

Today’s Erlang Thursday is on digraph:get_path/3.

digraph:get_path/3 takes a graph, a starting vertex, and an ending vertex and will attempt to find some path through the graph of length greater than zero, where all vertices in the path are distinct, except allowing for the first and last vertices to be the same.

If a path is found, it returns a list of the vertices visited (in order) to complete the path, if no path is found, false is returned.

First we will setup a new graph that we can traverse.

Graph = digraph:new().
% {digraph,20498,24595,28692,true}
V1 = digraph:add_vertex(Graph).
% ['$v'|0]
V2 = digraph:add_vertex(Graph).
% ['$v'|1]
V3 = digraph:add_vertex(Graph).
% ['$v'|2]
V4 = digraph:add_vertex(Graph).
% ['$v'|3]
E1 = digraph:add_edge(Graph, V1, V2).
% ['$e'|0]
E2 = digraph:add_edge(Graph, V2, V3).
% ['$e'|1]
E3 = digraph:add_edge(Graph, V3, V4).
% ['$e'|2]
E4 = digraph:add_edge(Graph, V2, V4).
% ['$e'|3]
E5 = digraph:add_edge(Graph, V4, V1).
% ['$e'|4]

This will give us a graph that looks like the following:

Now we can get to playing with digraph:get_path/3 and see what the paths are from any sets of nodes.

digraph:get_path(Graph, V2, V3).
% [['$v'|1],['$v'|2]]
digraph:get_path(Graph, V2, V4).
% [['$v'|1],['$v'|3]]
digraph:get_path(Graph, V2, V1).
% [['$v'|1],['$v'|3],['$v'|0]]
digraph:get_path(Graph, V3, V1).
% [['$v'|2],['$v'|3],['$v'|0]]
digraph:get_path(Graph, V1, V4).
% [['$v'|0],['$v'|1],['$v'|3]]
digraph:get_path(Graph, V1, V1).
% [['$v'|0],['$v'|1],['$v'|3],['$v'|0]]

Note that these just happen to be the shortest paths, but this is not guaranteed to return the shortest path, but just the first path found.

And if we add a new vertex, and don’t connect it to any other node in the graph, and we call digraph:get_path/3, we can see it returns false.

V5 = digraph:add_vertex(Graph).
% ['$v'|4]
digraph:get_path(Graph, V1, V5).
% false

–Proctor

Ruby Tuesday – Hash#invert

Today’s Ruby Tuesday is on Hash#invert.

Hash#invert will make the key the value, and the value the key, for each key-value pair in the hash.

{a: 1, b: 2, c: 3}.invert
# => {1=>:a, 2=>:b, 3=>:c}
{}.invert
# => {}
{twos: [2, 4, 6, 8], threes: [3, 6, 9], fives: [5, 10]}.invert
# => {[2, 4, 6, 8]=>:twos, [3, 6, 9]=>:threes, [5, 10]=>:fives}

This might seem like a odd thing to need, but sometimes your hash is not just a hash, but represents a bi-directional relationship.

One might use this when looking up DNA neucleobase pairings, where Adenine and Thymine always go together, and Guanine and Cytosine always pair togther, and we can create the full mapping by merging the mapping with it’s inverse.

{:A => :T, :C => :G}.invert
# => {:T=>:A, :G=>:C}
nucleobase_pairs.merge(nucleobase_pairs.invert)
# => {:A=>:T, :C=>:G, :T=>:A, :G=>:C}

Or when we have a mapping between a government id and a person (in the theoretically ideal world without identity theft), where we can get the person by their id, or the id for the person.

govt_ids_to_names = {123456789 => "Violetta",
                     999999999 => "Dilbert",
                     987654321 => "Nonnie Moose"}
# => {123456789=>"Violetta", 999999999=>"Dilbert", 987654321=>"Nonnie Moose"}
govt_ids_to_names.fetch(999999999)
# => "Dilbert"
govt_ids_to_names.invert.fetch("Nonnie Moose")
# => 987654321

And if we invert an inverted hash, we have the hash we started with.

govt_ids_to_names.invert.invert.fetch(123456789)
# => "Violetta"
govt_ids_to_names == govt_ids_to_names.invert.invert
# => true

–Proctor

Erlang Thursday – digraph:add_edge/4

Today’s Erlang Thursday is on digraph:add_edge/4.

digraph:add_edge/4 takes a graph as its first argument, the originating (eminating) vertex as its second arugment, the destination (incident) vertex as its third argument, and a label.

Graph = digraph:new().
% {digraph,20498,24595,28692,true}
Vertex1 = digraph:add_vertex(Graph, foo).
% foo
Vertex2 = digraph:add_vertex(Graph, bar).
% bar
Edge1 = digraph:add_edge(Graph, Vertex1, Vertex2, {foo, bar}).
% ['$e'|0]
digraph:edges(Graph).
% [['$e'|0]]
Edge2 = digraph:add_edge(Graph, Vertex2, Vertex1, {bar, foo}).
% ['$e'|1]
digraph:edges(Graph).
% [['$e'|1],['$e'|0]]

The digraph module also contains digraph:add_edge/5 which allows you to specify the edge identifier, in this case we want the edge to be myEdge.

digraph:add_edge(Graph, myEdge, Vertex2, Vertex1, myLabel).
% myEdge
digraph:edges(Graph).
% [['$e'|1],['$e'|2],['$e'|3],myEdge,['$e'|0]]

As well as digraph:add_edge/3 which allows you to not specify the edge or the label.

digraph:add_edge(Graph, Vertex2, Vertex1).
% ['$e'|2]
digraph:add_edge(Graph, Vertex2, Vertex1).
% ['$e'|3]
digraph:edges(Graph).
% [['$e'|1],['$e'|2],['$e'|3],['$e'|0]]

And if you note in the examples for digraph:add_edge/3 and digraph:add_edge/5 we added a number of edges with the same eminate and incident vertices, and it was happy to create those edges for us.

We can also create acyclic digraphs by using digraph:new/1, and specifying that we want the digraph() to be acyclic.

Graph2 = digraph:new([acyclic]).
% {digraph,20498,24595,28692,false}
VertexA = digraph:add_vertex(Graph2, foo).
% foo
VertexB = digraph:add_vertex(Graph2, bar).
% bar
EdgeAB = digraph:add_edge(Graph2, VertexA, VertexB, {foo, bar}).
% ['$e'|0]
EdgeBA = digraph:add_edge(Graph2, VertexB, VertexA, {bar, foo}).
% {error,{bad_edge,[foo,bar]}}

When we try to add an edge that will create a cycle in an acyclic directed graph, we get a return of a bad_edge error with the two edges specified.

–Proctor

Ruby Tuesday – Enumerable#group_by

Today’s Ruby Tuesday is on Enumerable#group_by.

Enumerable#group_by takes a block and returns a hash whose keys are the distinct values returned from the block, and the values are a list of items for which the block returned the key they are associated with.

This sounds a lot more complex than if you see it in code, so we will do a group_by of the range of numbers from one to ten, and group them by the result of calling even? on them.

(1..10).group_by(&:even?)
# => {false=>[1, 3, 5, 7, 9], true=>[2, 4, 6, 8, 10]}

We can se we have a hash with the two keys false and true, and the value for the key of false is a list of all the odd numbers, and the value for true is the list of the even numbers.

As the keys are just the return value, we can pass an array of strings, and group them by their first letter.

["foo", "bar", "bazz"].group_by(&:chr)
# => {"f"=>["foo"], "b"=>["bar", "bazz"]}

Or we can group them by their length,

["foo", "bar", "bazz"].group_by(&:length)
# => {3=>["foo", "bar"], 4=>["bazz"]}

Or, if we want to find some anagrams, we can group the words by the result of sorting their characters.

["tar", "rat", "bar", "rob", "art", "orb"].group_by {|word| word.chars.sort}
# => {["a", "r", "t"]=>["tar", "rat", "art"],
#  ["a", "b", "r"]=>["bar"],
#  ["b", "o", "r"]=>["rob", "orb"]}

This is also useful for when you are trying to get the start of some data to plot in a graph or a histogram, such as the length example above, or if we wanted to get a hash to be able to plot the number of words in the system dictionary against their length.

File.readlines("/usr/share/dict/words").
     map(&:strip).
     group_by(&:length).
     reduce({}) {|accum, kv| word_length, words = kv; accum[word_length] = words.length; accum}
# => {1=>52,
#  2=>160,
#  3=>1420,
#  5=>10230,
#  4=>5272,
#  8=>29989,
#  7=>23869,
#  9=>32403,
#  6=>17706,
#  11=>26013,
#  10=>30878,
#  12=>20462,
#  14=>9765,
#  16=>3377,
#  15=>5925,
#  20=>198,
#  19=>428,
#  17=>1813,
#  13=>14939,
#  18=>842,
#  21=>82,
#  22=>41,
#  23=>17,
#  24=>5}

–Proctor

BEAMing With Joy presentation from ElixirConf 2015 now available

Confreaks has started releases the videos from ElixirConf 2015 a couple of days ago, and just released the recording of my BEAMing With Joy talk yesterday.

The video, slides, favorite response to the talk so far, and a place for any questions you have can be found at http://www.proctor-it.com/beaming-with-joy/.

And if you have any comments, questions, or feedback, I would love to hear from you.

–Proctor

Erlang Thursday – digraph:add_vertex/1

Today’s Erlang Thursday starts to dig into the digraph module, as promised last week, and takes a look at digraph:add_vertex/1.

First we create a new directed graph, so we have something we can add vertices to.

Graph = digraph:new().
% {digraph,20498,24595,28692,true}

We then add some vertices to the graph by using digraph:add_vertex/1.

digraph:add_vertex(Graph).
% ['$v'|0]
digraph:add_vertex(Graph).
% ['$v'|1]
digraph:add_vertex(Graph).
% ['$v'|2]

As we don’t specify any information about the vertex we want to add, Erlang will create a new vertex for us of the format ['$v', I], with an empty list as the label where I is a non-negative integer.

We can also use digraph:add_vertex/2 to add a vertex if we wish to provide the vertex identifer, or provide vertex identifier and label in the case of digraph:add_vertex/3. As with digraph:add_vertex/1, digraph:add_vertex/2 uses the empty list as the label as well.

digraph:add_vertex(Graph, vertex1).
% vertex1
digraph:add_vertex(Graph, vertex2, "Vertex 2").
% vertex2

We have now added 5 vertices, and can check what vertices we have in the digraph() by using digraph:vertices/1.

digraph:vertices(Graph).
% [['$v'|2],['$v'|1],['$v'|0],vertex2,vertex1]

If we decide we want to try to add a vertex ourselves of the format ['$v' | I], we can run into trouble if you call digraph:add_vertex/1 after it.

digraph:add_vertex(Graph, ['$v' | 3]).
% ['$v'|3]
digraph:add_vertex(Graph).
% ['$v'|3]
digraph:vertices(Graph).
% [['$v'|2],['$v'|1],['$v'|0],['$v'|3],vertex2,vertex1]
digraph:add_vertex(Graph, ['$v' | 4]).
% ['$v'|4]
digraph:vertices(Graph).
% [['$v'|4],
%  ['$v'|2],
%  ['$v'|1],
%  ['$v'|0],
%  ['$v'|3],
%  vertex2,vertex1]

So we add a vertex by specifying the vertex() we want to add, and then add a new vertex and let Erlang take care of creating that vertex, and we wind up “losing” a vertex, as one essentially gets overridden when we look at the end state of the digraph().

–Proctor

Ruby Tuesday – Enumerable#find

Today’s Ruby Tuesday is on Enumerable#find a.k.a. Enumerable#detect.

Enumerable#find takes a predicate as a block and returns the first item for which the predicate returns true. If the predicate doesn’t return true for any of the items in the enumeration, nil is returned.

[1, 2, 3, 4, 5, 6, 7, 8, 9].find {|x| x > 5}
# => 6
[1, 2, 3, 4, 5, 6, 7, 8, 9].find {|x| x > 15}
# => nil

Enumerable#find can also take a “callable” as an argument, which will be called to if no item matches the predicate, and use that result as the return value of Enumerable#find.

[1, 2, 3, 4, 5, 6, 7, 8, 9].find(-> {:oops}) {|x| x > 15}
# => :oops
[1, 2, 3, 4, 5, 6, 7, 8, 9].find(-> {:oops}) {|x| x > 5}
# => 6
[1, 2, 3, 4, 5, 6, 7, 8, 9].find(-> {[true, false].sample}) {|x| x > 15}
# => false
[1, 2, 3, 4, 5, 6, 7, 8, 9].find(-> {[true, false].sample}) {|x| x > 15}
# => true
[1, 2, 3, 4, 5, 6, 7, 8, 9].find(-> {[true, false].sample}) {|x| x > 15}
# => false

–Proctor

Erlang Thursday – The digraph module

Today’s Erlang Thursday kicks of taking a look at the digraph module.

As I was looking into it, this module didn’t line up with my expectations of Erlang behavior, so I want to focus on that difference before taking a look at the functions in the module.

If we start by browsing through the function signatures in the digraph module, we can see that the only function that returns a digraph() are digraph:new/0 and digraph:new/1.

Thinking this was odd for a Erlang API, I went to the Erlang shell, and added a vertex to the digraph(), and then inpsected the result of that operation.

G = digraph:new().
% {digraph,69651,73748,77845,true}
G2 = digraph:add_vertex(G, foo, bar).
% foo

The return value of calling digraph:add_vertex/3 was foo, which was the second argument, and doesn’t match up with what the representation of a graph looks like.

Okay, time to look at the digraph() in G again then to see if that changed.

G.
% {digraph,69651,73748,77845,true}

That tuple result of the digraph() looks the same, so let’s see if that vertex we added is in the graph, since we did get the return value of foo.

digraph:vertices(G).
% [foo]
digraph:vertex(G, foo).
% {foo,bar}

Hrmm… Okay, looks like that vertex is in there.

Let’s add another vertex to the digraph() bound to G.

V = digraph:add_vertex(G).
% ['$v'|0]
digraph:vertices(G).
% [['$v'|0],foo]

That one is added as well.

HC SVNT DRACONES (Here Are Dragons)

So the behavior I want to call out in this post before we start looking at the functions in this module is that these functions exhibit observably mutable behavior on a digraph().

I say it is observably mutable, becuase while if it is not being changed under the covers of the implementation, the structure can be changed while the binding of the variable to the reference stays the same.

digraph:vertices(G).
% [['$v'|0],foo]
Copy = G.
% {digraph,69651,73748,77845,true}
V2 = digraph:add_vertex(G, wat).
% wat
digraph:vertices(Copy).
% [['$v'|0],foo,wat]
digraph:vertices(G).
% [['$v'|0],foo,wat]

This even mutates other varaible references as well, so this breaks any convention that I have seen in the Erlang ecosystem about keeping all data immutable.

We will continue looking at the digraph module in future Erlang Thursday posts, but I wanted to spend some time calling out the mutability inherent in the digraph()s, so that when you need to use a one, you can be aware that this is not something you want to use in your concurrent parts of your application without great caution.

Updated (October 18th)

As part of the translation into Lisp Flavoured Erlang as part of LFE Fridays, Robert Virding updated me with the reasoning of the digraph()‘s mutability, which he included in the translation as well.

The Dragons slain

The reason behind the dragons is how a digraph() is implemented. A digraph is built of 3 ETS tables, with, in this case, the table ids 8207, 12304 and 16401. You can see this by calling ets:i/0 which lists information about all the current tables. You can see that the 3 tables are owned by the LFE shell process:

> self().
<0.28.0>
> ets:i().
 id              name              type  size   mem      owner
 ----------------------------------------------------------------------------
 1               code              set   282    10393    code_server
 4098            code_names        set   64     7713     code_server
 8207            vertices          set   3      328      <0.28.0>
 12304           edges             set   0      305      <0.28.0>
 16401           neighbours        bag   2      319      <0.28.0>
 ac_tab          ac_tab            set   6      839      application_controller
 file_io_servers file_io_servers   set   0      305      file_server_2
 global_locks    global_locks      set   0      305      global_name_server
 global_names    global_names      set   0      305      global_name_server
...

ok

The digraph() structure itself is just a tagged tuple containing the table ids. As all changes are made to the ETS tables the structure itself never changes. Data about the tables and their contents can be read with ets:info/1 and ets:i/1.

–Proctor