Graphinder – Code review yourself


Few words of self reflection

After working a little on my side projects, I’ve found myself lacking a lot of code reviews. Or any sort of reflection on one’s code.
Often side projects are meant to be fun and focused on teaching oneself some new technology, new concept or just on simple proof of concept. Or made just for fun. But doesn’t mean it’s meant to resemble Swiss cheese. It’s quite the opposite.
Side project is where your code should shine.
Even if you tend to work in less Agile workflow (while (Waterfall) { fail++; }), you are mostly exposed to some sort of comments on your code. Sometimes somebody will come over to you with a bag of questions about your code. Sometimes you’ll find out you’d write it other way round. Alright, more than sometimes. But that’s not the point.
The point is that you have some sort of feedback.

Code review yourself

To fight back and to strive for better quality of code, I’ve forced myself to do annual Self Code Review.
You’d ask – how the hell? You’ll mostly lack feedback, because you’re the one, who gave birth to this little monster meant to be reviewed.
That’s actually not entirely true though.

Thinking over through many possibilities I’ve decided to go with behavior that would be closest to my natural way of reading the code.

Few steps to consider:

  • First of all, find an hour once a – let’s say – two weeks
  • Start from the point where you’re now in development. Let’s say, I’m in middle of Controller and View for one of my IAlgorithm in Graphinder. Let’s go down the whole pipeline, down to the very backend.
  • Now, let’s start going up, to middle end, to front end. Attempt to understand any method/property/field you’re going through in a process just by looking on a docs summary, method/property/field name or looking inside the body of each. Do you understand what it does or what it describes? Do you think it’s error-proof? If yes, that’s great – proceed. If not, you should do a quick reflection here.
  • Reflect on what is missing here. A quick docs summary? Maybe decomposition is necessary? Maybe you highly doubt it wont’ explode if you pass IDestroyerOfWorlds as param here? Or maybe name of the functionality is ambiguous? Or maybe it just doesn’t belong here and breaks SRP?
  • Decide on action that comes next: shall I document it properly now? Maybe. Should I refactor it now? Time is your judge. Should I postpone it then? It depends.
  • I believe that attempt to make code perfect at once tends to build up a lot of work and stops the progress of the project itself.
    While I also believe, that every project should work in a first place and then look beautiful, compromise is not an easy choice here.
    My advice would be to choose what you urgently need to fix (make it up to 2-3 pieces of code at most) and do it at once.
  • If you encounter the bug, always attempt to fix it before going back to writing new code. But that’s basics. That’s what should always be done when you find out bug.
  • Make sure, that every other thing that you’ve left behind is marked for future fixes. Make a goddamn //TODO {stuff we mostly don't come back to}. Acknowledge the fact, that some sort of refactor is needed here. Do yourself a favor and put it in some Scrum/Kanban/whatever board. I use Trello and love it. And I’m only user of my board. And I don’t care – as long as my workflow is being somehow organized.
  • Never trust code you see. Test it! It applies to every piece of code. Yours is the one you should probably trust the least. :)

Alrighty. We’ve got a few things we should go through here to make a few steps into direction of perfection.
But that’s only once a two weeks. Wouldn’t it be impossible to actually review all of that? Of course it would.
However, such approach made me behave a little differently when approaching my own code (and others’ too) at work (and everywhere else).
Whenever I come back to code written by myself or someone else, I try to reflect for a second or two on it.
I no longer feel afraid to put a big, bad //TODO in someone’s code and even put a card on a board with a task of making things right.
Of course mostly I bash my own code with wall of TODO‘s but I also tend to acknowledge others what smells just not right. Kindly, of course. Making enemies in our team is a bad idea from the very start, isn’t it? :)

As for growing up pile of TODO in your project, I’ll soon write a article about my upcoming TODO session.
Depending on how it goes. ;)

Other news

I’ve decided to introduce Continuous Integration for this project.
You can notice current status of last build every article’s menu, just below the logo. CI is provided by great amazing guys from AppVeyor @ https://ci.appveyor.com/. If you’re writing an app in C# and write unit tests (if you don’t then @&#!^#!&*^#!&* – do so!), you should definitely give it a try. It’s G-R-E-A-T.

Graphinder – Simulated Annealing algorithm


About Simulated Annealing

Simulated Annealing

Simulated Annealing is an algorithm based (as many, many other algorithms) on everyday life and observation of nature. In this particular case, the idea was to somehow mimic the process of annealing in metallurgy: to heat up system to some initial temperature and then step by step, work on it, cooling it slowly in a process.
Simulated Annealing is great solution, if we’re aiming for global optimum (best solution) instead of accepting local optima.
Algorithm depending on a temperature of system will be either likely to reject even high scored solutions (if temperature is high) or will stick to its current solution, provided that no better one was provided (if temperature is low).
There’s awesome animation on Wikipedia of how the process actually looks over the cooling process and as I don’t think I could come up with anything better, I’ll support myself with it:


Source: Simulated annealing – Wikipedia

As you can see, the lower the temperature of the system, the less likely algorithm will accept other, worse solution. On the other hand, when temperature is high, algorithm keeps on accepting almost anything that comes up with.
Note: accepting solution worse than current is important, if we don’t want to get stuck in local minimum. It might look as best at first, but we might later find out it was not globally best! :)

Implementation side

Algorithm definition

For any algorithm, including Simulated Annealing, there’s an interface IAlgorithm defining it’s behavior:

Any Algorithm will attempt to find solution for a Problem by continuously searching for a solution better than CurrentSolution on a Graph. Of course, depending on its acceptance algorithm, it CanAcceptAnswer as a new one or just reject it. Once we LaunchAlgorithm, algorithm won’t stop while it CanContinueSearching(). Second most important thing besides finding a solution to our problem is to know what actual ProcessorTimeCost was, so that we can compare different strategies for our algorithm and perhaps, compare it even with other algorithms we have already implemented or imported to our application.

Algorithm logic

Besides everything we defined in our IAlgorithm, there’s actually couple of properties that are characteristic for Simulated Annealing algorithm.

First of all, we’ve been talking all the time about the temperature! So we have InitialTemperature on which we’ll start everything and CurrentTemperature that will keep on decreasing over and over until algorithm stops. How much system will cool on single step is defined by CoolingRate and how actually process of picking solution will look like is up to CoolingStrategy we’ve chosen for algorithm.

Currently then only implemented cooling strategy for Simulated Annealing is AllRandomCooling. In a simple manner: it will keep on rolling for random node from Graph until solution it’s building up is a correct solution to IProblem:

CoolingStrategy will keep on searching for the solution, until it can continue. Simulated Annealing by definition allows the process to go on until the iron is hot ie. until the temperature does not reach an extreme minimum:

One last thing that we needed implemented is how algorithm decides if it can accept proposed solution.
Let me note that mentioned implementation is meant to be partly replaced by IProblem.SolutionFitness. Common code smell (switch that might likely grow up in a future) will be removed on upcoming TO DO’s session. :)
One thing worth noting here is the calculation part, where you can easily notice how Math.Exp result will significantely change during cooling process:

As previously, all of the code is available on my GitHub. Link leads to subfolder containing anything concerning Simulated Annealing algorithm and also everything that was mentioned in this article:

Graphinder – Minimum Vertex Cover problem


About Minimum Vertex Cover

As we’ve already spoken about technologies, ideas and project plan, we may move on now to the very juice of Graphinder project – optimization problems.
Currently (and if time won’t be merciful, till the end of the project) we’ll be operating on a problem called Minimum Vertex Cover.
In a simple manner, Minimum Vertex Cover is a smallest vertex cover possible for given graph.
What vertex cover is then? Vertex cover is actually a set of vertexes chosen in such a way, that every edge of graph has at least one endpoint in a said set.

Let’s illustrate it with a simple graph:

Minimum Vertex Cover
Loosely based on example from: Vertex cover – Wikipedia

Green nodes are the ones chosen to be vertex cover. As you can see, if we attempt to take away one of the green ones from our vertex cover, it won’t meet vertex cover definition anymore.
To be precise, it would be suitable to also describe here a difference between minimum and minimal vertex cover. Minimum vertex cover (the one we’re working with) is the most optimal solution that meets vertex cover requirements. On the other hand, minimal vertex cover is the solution that provided we take away one node from it, it will no longer meet vertex cover requirements. That of course also means, that minimum vertex cover is a minimal vertex cover but not the other way round.

Code, code, code!

Data structure – Graph

Before going straight to the algorithm, let’s see how our graph looks like.
Graph used for an entire project will be an undirected graph with currently no weights on its edges (what may change on new problem implementation). It will be the main data structure every algorithm and problem will be operating on.
Graph consists of nodes, that have neighborhood relation with other nodes connected with edges.

Quick class diagram (details spared):

Graph class diagram

No magic, right?
Of course Graph is as encapsulated as it can be, exposing only necessary data outside, including only a copy of nodes collection outside (ReadOnlyCollecton would be perhaps a better choice here?) and strictly prohibiting one way of adding both nodes and edges to it.

Full code of Graph.cs can be found in Graphinder repository on GitHub or via the link provided below:

Problem – Minimum Vertex Cover

Knowing our data structure we can move on to algorithm for checking if vertex cover is correct.
Algorithm that will search for minimum vertex cover solution will use it a lot, that’s why it would probably be a matter of additional performance refactors later if necessary.

Definition of a problem

Let’s look on part of functionalities defined in IProblem interface.
I’ve spared the ones that we don’t need to elaborate now.
Most important for our process are what is a CurrentOutcome to our problem, which nodes are chosen to be our CurrentSolution, a way to AddNewSolution, a way to check if IsSolutionCorrect and perhaps exposed way to check, what provided SolutionOutcome will be.
As you probably noted, naming convention seems pretty natural and docs should fulfill the rest, so I will move on to implementation now. :)

IsSolutionCorrect

On a implementation side let’s take a look on a two methods that will be used the most.
First of all, as mentioned above, every problem and algorithm we have implemented would like to check if IsSolutionCorrect.
As solution is defined by a collection of nodes, we would like to check if every edge that comes out of their neighborhood relation ends up in a same amount of edges as a graph have:

We might want to check for whether all nodes are from the same graph as our optimization problem operates on though.
While Edge validation would forbid connecting nodes from different graphs with its CanConnect validation and MinimumVertexCover won’t accept any node in solution which key doesn’t belong to the problem’s graph, there might yet be a highly unlikely situation where all nodes from different graph match both keys from other graph and also match vertex cover.
New entry flies to Trello board then for a unit test to code!

AddNewSolution

Our seconds most important operation to use would be a way to AddNewSolution.
What we don’t want to see is a solution that contains node that problem’s graph doesn’t contain.
What we also don’t want to see is that node’s parent is different from the problem’s graph, due to the way node validates adding neighbors.

Full code of MinimumVertexCover.cs can be found in Graphinder repository on GitHub or via the link provided below:

Aaaaand… that’s it for today.
I’ll try to come up with some real life cases for you just before going to the .Web part implementation.
As for a next post, we’ll talk about our first algorithm to play with: Simulated Annealing.