markhneedham/blog huggingface dataset:
gephi: Centring a graph around an individual node
Date: 2012-04-30 22:20:45

I spent some time recently playing around with http://gephi.org/[gephi] - an open source platform for creating visualisations of graphs - to get a bit more insight into the ThoughtWorks graph which I've created in neo4j.

I http://maxdemarzi.com/2012/04/12/using-sigma-js-with-neo4j/[followed Max De Marxi's blog post] to create a GEFX (Graph Exchange XML Format) file to use in gephi although I later learned that you can import directly from neo4j into gephi which I haven't tried yet.

I loaded it into gephi and this is what it looks like:

image::{{<siteurl>}}/uploads/2012/04/full-graph.jpg[Full graph,600]

image::{{<siteurl>}}/uploads/2012/04/filter-menu-top.jpg[Filter menu top,270]

There are massive numbers of connections between almost every node so it's pretty hard to see what's going on.

I wanted to be able to centre the graph around an individual person and see just the links related to them.

To do that we need to make use of an 'http://forum.gephi.org/viewtopic.php?t=286[ego] http://blog.ouseful.info/2010/05/10/getting-started-with-gephi-network-visualisation-app-%E2%80%93-my-facebook-network-part-iii-ego-filters-and-simple-network-stats/[filter]' so the first step is to make the filters menu visible by clicking 'Window > Filters'.

We can then choose the ego filter which sits under 'Library > Topology' and fill in the ID of the node that we want to centre the graph around as well as choose the depth of the traversal.

image::{{<siteurl>}}/uploads/2012/04/filter-menu-bottom.jpg[Filter menu bottom,257]

In this case any traversal above 1 will end up traversing the majority of the graph since the average distance between nodes in this graph is just above 2.5.

I run the 'Force Atlas' layout algorithm over it and this is what we end up with:

image::{{<siteurl>}}/uploads/2012/04/my-graph.jpg[My graph,545]

My graph shows some interesting clustering of nodes where the ones on the right are people I worked with in India, top left are people I worked with in Australia, bottom left people in the UK and the ones towards the lower middle are people I went to ThoughtWorks University with.

There are a load of other filters to choose from but the ego filter is pretty cool!
Performance: Caching per request
Date: 2012-04-30 21:45:50

A couple of years ago I wrote a post describing an approach my then colleague https://twitter.com/#!/christianralph[Christian Blunden] used to help improve the performance of an application where you try to http://www.markhneedham.com/blog/2010/07/10/performance-do-it-less-or-find-another-way/[do expensive things less or find another way to do them].

On the application I'm currently working on we load reference data from an Oracle database into memory based on configurations provided by the user.

There are multiple configurations and then multiple ways that those configurations can be priced so we have two nested for loops in which we load data and then perform calculations on it.

When profiling the application we realised that some of the database calls being made with the same parameters and were therefore loading back the same reference data that we'd already loaded.

The most obvious way to solve this problem would be to move the code out of the loop and make less calls to the database that way but logically the  domain is expressed more clearly when it's inside the loop.

http://www.linkedin.com/pub/alex-harin/13/40b/716[Alex] therefore came up with an alternative approach where we wrap the database calling code in a caching decorator.

The caching decorator is a request scoped object so we're only caching those results for a short amount of time which means that we http://martinfowler.com/bliki/TwoHardThings.html[don't have to worry about cache invalidation] because it's thrown away when the request has been processed.

I've previously seen this problem solving by using a Hibernate second level cache which would cache results across requests.

In our application there are more likely to be calls to the database with the same parameters within the same request rather than across requests.

The load on the system is likely to come from complex requests where many prices needed to be calculated rather than from a huge frequency of requests

If that changes then we always have the option of caching at both levels but at the moment our current approach seems to work pretty well.
Algo Class: Start simple and build up
Date: 2012-04-24 07:17:24

Over the last six weeks I've been working through Stanford's https://www.coursera.org/course/algo[Design and Analysis of Algorithms I] class and each week there's been a programming assignment on a specific algorithm for which a huge data set is provided.

For the first couple of assignments I tried writing the code for the algorithm and then running it directly against the provided data set.

As you might imagine it never worked first time and this approach led to me becoming very frustrated because there's no way of telling what went wrong.

By the third week I'd adapted and instead tested my code against a much smaller data set to check that the design of the algorithm was roughly correct.

I thought that I would be able to jump straight from the small data set to the huge one but realised that this sometimes didn't work for the following reasons:

. An inefficient algorithm will work fine on a small data set but grind to a halt on a larger data set. e.g. my implementation of the http://en.wikipedia.org/wiki/Strongly_connected_component[strongly connected components (SCC)] graph algorithm did a scan of a 5 million element list millions of times.
. An incorrect algorithm may still work on a small data set. e.g. my implementation of SCC didn't consider that some vertices wouldn't have forward edges and excluded them.

My colleague Seema showed me a better approach where we still use a small data set but think through all the intricacies of the algorithm and make sure our data set covers all of them.

For the SCC algorithm this meant creating a graph with 15 vertices where some vertices weren't strongly connected while others were connected to many others.

In my initial data set all of the vertices were strongly connected which meant I had missed some edge cases in the design of the algorithm.

Taking this approach was very effective for ensuring the correctness of the algorithm but it could still be inefficient.

I used http://visualvm.java.net/[Visual VM] to identify where the performance problems were.

In one case I ended up running out of memory because I had 3 different representations of the graph and was inadvertently using all of them.

I made the stupid mistake of not writing any automated tests for the smaller data sets. They would have been very helpful for ensuring I didn't break the algorithm when performance tuning it.

I should really have learnt that lesson by now given that I've been writing code in a test driven style for nearly six years but apparently I'd turned off that part of my brain.

Looking forward to Design and Analysis of Algorithms II!
Coding: Is there a name for everything?
Date: 2012-04-23 00:20:57

A month ago I wrote a post describing http://www.markhneedham.com/blog/2012/03/17/coding-wait-for-the-abstractions-to-emerge/[an approach my team has been taking to avoid premature abstractions] whereby we leave code inline until we know enough about the domain to pull out meaningful classes or methods.

Since I wrote that post we've come across a couple of examples where there doesn't seem to be a name to describe a data structure.

We are building a pricing engine where the input is a set of configurations and the output is a set of pricing rows associated with each configuration.

We modelled the problem using a List of http://code.google.com/p/totallylazy/source/browse/src/com/googlecode/totallylazy/Pair.java?r=ddc97667f03784cbf4db4906d2d09777926d0a17[Pairs] of Configuration/PricingItems:

[source,java]
----

List<Pair<Configuration, PricingItem>> configurationToPricingItems = buildThoseCombinations();
----

image::{{<siteurl>}}/uploads/2012/04/configuration-pricingrow.gif[Configuration pricingrow,221]

We don't need to do any lookups by Configuration - just show the results to the user - which is why we haven't used a Map.

Our object oriented background suggested that there should be a name in the business domain for this but when we spoke to our business analyst and subject matter expert it became clear that they didn't actually have a word.

Despite that it still feels strange to have to pass around a List of Pairs but I wonder if that's because in Java we tend to abstract concepts behind classes rather than because it makes sense to do so.

If we were using clojure then I don't think we'd feel as uncomfortable about passing around basic data structures because the language and the culture around it encourage this. We should only create a type when it's strictly necessary.

In this case it's a data structure to carry those combinations around and we don't actually apply any logic to the data structure as a whole, only to the individual entries.

We wrote the code about three weeks ago now and haven't experienced any difficulties in terms of the code being understandable or easy to work with.

I'm intrigued as to whether others have noticed a similar thing or if we aren't embracing Domain Driven Design fully and need to dig deeper to find a missing domain concept?
Haskell: A simple parsing example using pattern matching
Date: 2012-04-15 14:22:45

As part of https://code.google.com/codejam/contest/1460488/dashboard#s=p1[the second question in the Google Code Jam] I needed to be able to parse lines of data which looked like this:

[source,text]
----

3 1 5 15 13 11
----

where

____
The first integer will be N, the number of Googlers, and the second integer will be S, the number of surprising triplets of scores. The third integer will be p, as described above. Next will be N integers ti: the total points of the Googlers.
____

This seemed like it should be easy to do but my initial search led me to the http://book.realworldhaskell.org/read/using-parsec.html[Parsec chapter] in Real World Haskell which seemed a bit over the top for my problem.

All we really need to do is split on a space and then extract the parts of the resulting list.

I thought there'd be a 'split' function to do that in the base libraries but if there is I couldn't see it.

However, there are a bunch of useful functions in the 'http://hackage.haskell.org/packages/archive/split/0.1.4.2/doc/html/Data-List-Split.html[Data.List.Split]' module which we can install using http://www.haskell.org/cabal/[cabal] - a RubyGems like tool which came with my Haskell installation.

Installing the http://hackage.haskell.org/package/split-0.1.4.2[split module] was as simple as:

[source,text]
----

cabal update
cabal install split
----

There's a list of all the packages available through cabal http://hackage.haskell.org/package/[here].

I needed the +++<cite>+++splitOn+++</cite>+++ function:

[source,text]
----

import Data.List.Split
> :t splitOn
splitOn :: Eq a => [a] -> [a] -> [[a]]
----

We can then split on a space and extract the  appropriate values using pattern matching like so:

[source,haskell]
----

let (_:surprisingScores:p:googlers) = map (\x -> read x :: Int) $ splitOn " " "3 1 5 15 13 11"
----

[source,text]
----

> surprisingScores
1
----

[source,text]
----

> p
5
----

[source,text]
----

> googlers
[15,13,11]
----
Ruby: neo4j gem - LoadError: no such file to load -- active_support/core_ext/class/inheritable_attributes
Date: 2012-04-14 10:21:40

I've been playing around with neo4j again over the past couple of days using the https://github.com/andreasronge/neo4j[neo4j.rb] gem to build up a graph.

I installed the gem but then ended up with the following error when I tried to 'require neo4j' in 'irb':

[source,Text]
----

LoadError: no such file to load -- active_support/core_ext/class/inheritable_attributes
  require at org/jruby/RubyKernel.java:1033
  require at /Users/mneedham/.rbenv/versions/jruby-1.6.7/lib/ruby/site_ruby/1.8/rubygems/custom_require.rb:36
   (root) at /Users/mneedham/.rbenv/versions/jruby-1.6.7/lib/ruby/gems/1.8/gems/neo4j-1.3.1-java/lib/neo4j.rb:9
  require at org/jruby/RubyKernel.java:1033
  require at /Users/mneedham/.rbenv/versions/jruby-1.6.7/lib/ruby/gems/1.8/gems/neo4j-1.3.1-java/lib/neo4j.rb:59
   (root) at src/main/ruby/neo_test.rb:2
----

It seems a few others https://github.com/andreasronge/neo4j/issues/150[have come across this problem as well] and the problem seems to be that ActiveSupport 3.2 isn't yet supported by the gem so we need to use an earlier version of that.

There were a few suggestions in the comments but it was the following that worked for me:

[source,text]
----

sudo gem uninstall railties
sudo gem install railties --version 3.1
----
neo4j: What question do you want to answer?
Date: 2012-05-05 13:20:41

Over the past few weeks I've been modelling ThoughtWorks project data in http://neo4j.org/[neo4j] and I realised that the way that I've been doing this is by considering *what question I want to answer* and then building a graph to answer it.

When I first started doing this the main question I wanted to answer was 'how connected are people to each other' which led to me modelling the data like this:

image::{{<siteurl>}}/uploads/2012/05/initial.png[Initial,413]

The 'colleagues with' relationship stored information about the project the two people had worked on together and how long they'd worked together.

This design was fine while that was the only question I wanted to answer but after I showed it to a few people it became clear that there were other questions we could ask which would be difficult to answer with it designed this way.

e.g.

* Which people on project X have I never worked with?
* Which person has worked for client X for the longest?
* Which people worked together on the same client if not the same project?

I therefore need to make 'client' and 'project' first class entities in the graph rather than just being there implicitly which favours a design more along these lines:

image::{{<siteurl>}}/uploads/2012/05/initial1.png[Initial,459]

It makes it a little more difficult to answer the initial question about connections between people but opens up the answers to other questions such as the ones detailed above.

I'm still getting used to this way of modelling data but it feels like you're driven towards designing your data in a way that's useful to you as opposed to the relational approach where you tend to model relations and then work out what you want to do with the data.
Haskell: Writing a custom equality operator
Date: 2012-05-16 13:16:48

In the comments on my post about http://www.markhneedham.com/blog/2012/05/08/haskell-generating-random-numbers/[generating random numbers] to test a function David Turner suggested that this was exactly the use case for which http://book.realworldhaskell.org/read/testing-and-quality-assurance.html[QuickCheck] was intended for so I've been learning a bit more about that this week.

I started with a simple property to check that the brute force (bf) and divide and conquer (dc) versions of the algorithm returned the same result, assuming that there were enough values in the list to have a closest pair:

[source,haskell]
----

prop_closest_pairs xs = length xs >= 2 ==> dcClosest xs == (fromJust $ bfClosest xs)
----

I could then run that as follows:

[source,haskell]
----

> import QuickCheck.Test
> quickCheck(prop_closest_pairs :: [(Double, Double)] -> Property)
----

It failed pretty quickly because the bf and dc versions of the algorithm sometimes return the pairs in a different order.

e.g. bf may say the closest pair is (2.0, 0.0), (2.1, 1.1) while dc says it's (2.1, 1.1), (2.0, 0.0) which will lead to the quick check property failing because those values aren't equal:

[source,haskell]
----

> ((2.0, 0.0), (2.1, 1.1))  == ((2.1, 1.1), (2.0, 0.0))
False
----

The best way I could think of to get around this problem was to create a type to represent a pair of points and then write a custom equality operator.

I initially ended up with the following:

[source,haskell]
----

type Point a = (a, a)
data Pair a = P (Point a) (Point a)
----

[source,haskell]
----

instance Eq (Pair a) where
	P a b == P c d = a == c && b == d || a == d && b == c
----

Which didn't actually compile:

[source,text]
----

qc_test.hs:41:58:
    No instance for (Eq a)
      arising from a use of `=='
    In the second argument of `(&&)', namely `b == c'
    In the second argument of `(||)', namely `a == d && b == c'
    In the expression: a == c && b == d || a == d && b == c
----

The problem is that while we've made Pair an instance of the Equality type class there's no guarantee that the value contained inside it is an instance of the Equality type class which means we might not be able to compare its values.

We need to add a class constraint to make sure that http://learnyouahaskell.com/making-our-own-types-and-typeclasses#typeclasses-102[the value inside P is a part of Eq]:

[source,haskell]
----

instance (Eq a) => Eq (Pair a) where
	P a b == P c d = a == c && b == d || a == d && b == c
----

Now we're saying that we want to make Pair an instance of the Equality type class but only when the value that Pair contains is already an instance of the Equality type class.

In this case we're just storing pairs of doubles inside the Pair so it will work fine.

Now if we compare the two points from above we'll see that they're equal:

[source,haskell]
----

> P (2.0, 0.0) (2.1, 1.1)  == P (2.1, 1.1) (2.0, 0.0)
True
----

I had to go and change the existing code to make use of this new but it didn't take more than 5-10 minutes to do that.
Haskell: Explicit type declarations in GHCI
Date: 2012-05-10 07:11:17

On a few occasions I've wanted to be able to explicitly define the type of something when trying things out in the Haskell REPL (GHCI) but I didn't actually realise this was possible until a couple of days ago.

For example say we want to use the +++<cite>+++http://zvon.org/other/haskell/Outputprelude/read_f.html[read]+++</cite>+++ function to parse an input string into an integer.

We could do this:

[source,haskell]
----

> read "1" :: Int
1
----

But if we just evaluate the function alone and try and assign the result without casting to a type we get an exception:

[source,haskell]
----

> let x  = read "1"

<interactive>:1:10:
    Ambiguous type variable `a0' in the constraint:
      (Read a0) arising from a use of `read'
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: read "1"
    In an equation for `x': x = read "1"
----

sepp2k shows http://stackoverflow.com/questions/3093133/how-to-provide-explicit-type-declarations-for-functions-when-using-ghci[how we can provide a type declaration in GHCI in his Stack Over Flow answer]:

[source,haskell]
----

> let x::Int; x = read "1"
> x
1
----

We can also use it when creating a list of integers to ensure they are of type 'Int' rather than 'Integer' for example:

[source,haskell]
----

> let y = [1,2,3]
> :t y
y :: [Integer]

> let y::[Int]; y = [1,2,3]
> :t y
y :: [Int]
----

It's a pretty simple thing but I didn't know it was even possible!
Building an API: Test Harness UI
Date: 2012-05-19 20:03:02

On the project I've been working on we're building an API to be used by other applications in the organisation but when we started none of those applications were ready to integrate with us and therefore http://martinfowler.com/articles/consumerDrivenContracts.html[drive the API design].

Initially we tried driving the API through integration style tests but we realised that taking this approach made it quite difficult for us to imagine how an application would use it.

It also meant that we didn't have a good way to show our business stakeholders the work we'd done - showing off pieces of JSON going back and forth probably wouldn't have gone down too well!

We therefore decided to create our own test harness UI which we would use to show case what we'd developed so far and also use to help drive the design of the API.

Obviously it would be better if we were able to drive the API out from a real application but given that wasn't possible the test harness approach seems to work reasonably well.

The main problem that we ran into was not knowing how much effort we should be putting into the test harness UI given that its primary purpose was to show the progress being made on the UI.

We started out not writing many tests or paying much attention to how it looked since it was assumed to be a throwaway UI.

Over time it's become more complicated and since we use it to display progress to management stakeholders we've spent time making it more presentable.

Despite that I'd still say the effort we've put in is worthwhile because it gives us a way to show progress to non technical people.

From my experience if you can't do that they'll start to get nervous and wonder if you know what you're doing which isn't a good place to be!
Haskell: Maximum Int value
Date: 2012-05-07 09:18:02

One of the algorithms covered in https://www.coursera.org/course/algo[Algo Class] was the http://en.wikipedia.org/wiki/Closest_pair_of_points_problem[closest pairs algorithm] - an algorithm used to determine which pair of points on a plane are closest to each other based on their http://en.wikipedia.org/wiki/Euclidean_distance[Euclidean distance].

My real interest lies in writing the divide and conquer version of the algorithm but I started with the brute force version so that I'd be able to compare my answers.

This is the algorithm:

[source,text]
----

minDist = infinity
for each p in P:
  for each q in P:
    if p ≠ q and dist(p, q) < minDist:
      minDist = dist(p, q)
      closestPair = (p, q)
return closestPair
----

'infinity' in this case could be the maximum value that an Int could hold which on a 64 bit architecture would be 2^63^ so I hardcoded that into my implementation:
o

[source,haskell]
----

bfClosest :: (Ord a, Floating a) => [(a, a)] -> Maybe ((a, a), (a, a))
bfClosest pairs =
  snd $ foldl (\ acc@(min, soFar) (p1, p2) ->
                if distance p1 p2 < min then (distance p1 p2, Just(p1, p2)) else acc)
              (2^63, Nothing)
              [(pairs !! i, pairs !! j) | i <- [0..length pairs - 1], j <- [0..length pairs-1 ], i /= j]
  where distance (x1, y1) (x2, y2) =  sqrt $ ((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)
----

We're comparing each point with all the others in the list by folding over a collection of all the combinations and then passing the pair with the smallest distance between points as part of our accumulator.

More by chance than anything else I was reading http://learnyouahaskell.com/types-and-typeclasses[the Learn You a Haskell chapter on types and type classes] and came across the +++<cite>+++http://zvon.org/other/haskell/Outputprelude/maxBound_f.html[maxBound]+++</cite>+++ function which does exactly what I want:

[source,haskell]
----

> 2 ^ 63
9223372036854775808

> maxBound :: Int
9223372036854775807
----

We can't plug that straight into the function as is because the fold inside 'bfClosest' expects a float and had been automatically coercing 2^63^ into the appropriate type.

We therefore use 'fromIntegral' to help us out:

[source,haskell]
----

bfClosest :: (Ord a, Floating a) => [(a, a)] -> Maybe ((a, a), (a, a))
bfClosest pairs =
  snd $ foldl (\ acc@(min, soFar) (p1, p2) ->
                if distance p1 p2 < min then (distance p1 p2, Just(p1, p2)) else acc)
              (fromIntegral (maxBound :: Int), Nothing)
              [(pairs !! i, pairs !! j) | i <- [0..length pairs - 1], j <- [0..length pairs-1 ], i /= j]
  where distance (x1, y1) (x2, y2) =  sqrt $ ((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)
----