Grab Bag Release: Minimum Spanning Trees

Okay, the last weeks have been full of work, my apologies for the delay. This weekend, I finally managed to finish my implementation of the algorithm for finding minimum spanning trees by Fredman and Tarjan, here we go.

Minimum Spanning Trees

Let G = (V, E) be a connected, undirected graph with |V| = n vertices and |E| = m edges (v, w) with non-negative edge weights c(v, w). A minimum spanning tree of G is a spanning tree of G with minimum total edge weight.

Minimum Spanning Tree

The algorithm presented in “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms” by Michael L. Fredman and Robert Endre Tarjan in 1985 finds a minimum spanning tree of an input graph in O(m ß(m,n)), where

ß(m,n) = min{ i | log(i) n ≤ (m/n)}

and log(i) n is defined inductively by

  • log(0) n = n
  • log(i + 1) n = log log(i) n

Post-Mortem: Campus Buddies

The first project of slash games, the company Christian and me founded back at the beginning of the year, has been officially launched: yourfone.de Campus Buddies. This website concludes the first work-for-hire we’ve collaborated with Pop Rocket Games on. Pop Rocket Games wrote the gamification concept for the website and managed the whole production on behalf of the social media agency beesocial. All of us have learned quite a lot in the past months, and I’d like share eight learnings with you that I’m sure will come in handy some day.

yourfone.de Campus Buddies

About Campus Buddies

Campus Buddies allows students to promote a special yourfone.de offer, earning points which they can finally trade for attractive rewards like smartphones or Macbooks. The platform features a dynamic news stream for each user, many gamification elements like achievements and user levels, full social network integration (Facebook, Twitter, Google+) as well as SSL encryption of all connections. Just like LinkedIn, Campus Buddies is a stateless scalable Java web application based on the Play Framework.

And here is what we’ve learned making it.

1. Plan with changes of external APIs.

Campus Buddies has integrated three of the major social platforms: Facebook, Twitter and Google+. During the development process, both Facebook and Google+ changed their APIs, effectively turning some of our code into useless rubbish – it took us about a day or two to get everything up and running again.

Talking to other web developers, we learned that social platform providers tend to change their APIs regularly, and won’t notify you about that. Neither before, nor after. Never. If you’re planning similar integration, you should consider that in your project plan.

2. Avoid writing everything yourself.

You got a problem that is not exactly related to just your application? Maybe someone else has already solved it. There’s lots of great code out there, with smart people having spent tens of hundreds of hours on implementing and polishing it. Use that code!

Here are some examples of libraries that allowed us to save much development time:

  • Joda Time. Replacement for the Java date and time classes. They are better. A lot. Trust me.
  • Google Guava. Several of Google’s core libraries that they use in their Java projects, featuring useful collection extensions, concurrency libraries, string processing, I/O and more.
  • OpenCSV. Simple CSV parser library.

3. Make debugging as easy as possible.

At the beginning of the project, Christian had the idea of creating a debug web page containing links for several debug functions, like creating and logging in a test user or adding points for the current user.

Campus Buddies Development Debug PageThis was one of the best ideas we had throughout the project.

Debugging can be a pain in the ass, especially when network communication is involved. Our debug page was the equivalent to the debug UI or developer console of your game, and it saved us lots of blood, sweat and tears.

Note that the earlier you set up your debugging tools, the more you’ll benefit from them.

4. Make the deploy process as straight-forward as possible.

We set up a Jenkins and hooked it to our Git server, so that every time we pushed it would create the WAR package for our web application and deploy it to our development server. The version number and time stamp was automatically increased and displayed in the browser title bar, so we knew whether the actual deployment process had finished. Furthermore, Jenkins enabled us to deploy our current development version to the live server.

You wouldn’t wanna do all that by hand. Every time. Do you?

Again, the earlier you set your deployment tools up, the more you’ll benefit.

5. Mock network interaction for debug and testing purposes.

Everything that involves network communication is annoying to test. Full stop. Thus, we mocked parts of the remote interaction of our application, such as sending e-mails or verifying leads. Whenever a mail was sent, it was written to the console instead, for instance. This allowed us to check all parts of our application that include sending mails without having to spam our (or everyones…) inboxes.

2013-05-19 19:36:29,980 - [INFO] - from application
MOCK MAILER: send email

2013-05-19 19:36:29,982 - [INFO] - from application
FROM:"yourfone.de Campus Buddies" <keineantwort@campus-buddies.de>

2013-05-19 19:36:29,983 - [INFO] - from application
TO:"Nick" <mail@npruehs.de>

2013-05-19 19:36:29,985 - [INFO] - from application
TEXT:

<html>
<head>
<title>
...

6. Standardize code style for all team members.

If you aren’t alone (and I sincerely hope you’re not), you’ll want to standardize your code styles. Being clear about tiny details such as tabs vs. spaces can greatly increase code readability and maintainability and reduce the number of merge conflicts.

For Java, Eclipse allows you to export your editor settings, and for C# I encourage the usage of StyleCop. The settings files can be checked in to version control, and no one can do anything wrong with setting up his or her development environment.

7. Create reusable views where possible.

Just as you’re used to break down your model and controllers into reusable code parts, you should build reusable views as well. We were able to extract parts of our HTML forms into own templates, such as an address field or a password field with repetition, including validation.

You’ll have to smile every time you’re able to re-use one of them.

8. Set up hierarchical configuration files.

I hope you’re using configuration files for passing parameters to your application. We used these files for specifying the log level or the minimum password length for new users, for example.

By being able to override one file with another, we allow shorter passwords for testing on our development server than our live server. Even better: While most of the config files are checked in to version control, each of us had his or her own local config file for overriding the default settings, without having to constantly pay attention not to check it in.

Conclusion

While we’re not planning to use Java or the Play Framework for any of our upcoming game projects, most of the learnings are easily transferred to them anyway. Feel free to tell any thoughts in the comments below and to share these learnings with your co-workers and friends.

You might enjoy it the next time you join a new team 😉

Grab Bag Release: Graphs

Last week, I’ve been to Munich with my girlfriend, celebrating indie comics and her winning the Kurt Schalker Award! 🙂 AND I’ve found some time for working on my graph implementation.

Graphs

Graphs are pairs G = (V, E) where V denotes some set of vertices and E some set of edges between these vertices.

My implementation stores the set of edges of the graph as adjacency list, making it fast at enumerating vertex neighbors, but slows at accessing specific edges for dense graphs (which have many edges between each pair of vertices. It allows adding multiple edges between two vertices, thus being feasible for modeling multi-graphs. Also, it allows creating loops, edges whose source and target vertex are identical.