
Graphinder series articles
 Graphinder – Project Introduction
 Graphinder – I don’t need this covered…
 Graphinder – Minimum Vertex Cover problem
 Graphinder – Simulated Annealing algorithm
 Graphinder – Code review yourself
 Graphinder – Genetic Algorithm – Introduction
 Graphinder – Genetic Algorithm – Selection
 Graphinder – Genetic Algorithm – Crossover
 Graphinder – Genetic Algorithm – Mutation
 Graphinder – Genetic Algorithm – Wrap up
 Graphinder – Monthly Progress Report – March
 Graphinder – Async IEnumerable with Rx.Net and IObservable
 Graphinder – Reporting progress with Rx.Net
 Graphinder – TDD and starting from red
 Graphinder – Domain models vs Persistence models
 Graphinder – Queries and Commands vs Repository pattern
 Graphinder – Encapsulating persistence layer
 Graphinder – Solution changes and nuget hell
 Graphinder – Monthly Progress Report – April
 Graphinder – Application architecture
 Graphinder – Resources planning on Azure
 Graphinder – Quick summary and what next
 Quick thoughts after Daj Sie Poznac 2016 finals
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:
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):
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. :)
1 2 3 4 5 6 7 8 
public interface IProblem : IOperableOn<Graph> { int CurrentOutcome { get; } ICollection<Node> CurrentSolution { get; } void AddNewSolution(ICollection<Node> nodes); bool IsSolutionCorrect(ICollection<Node> nodes); int SolutionOutcome(ICollection<Node> nodes); } 
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
public bool IsSolutionCorrect(ICollection<Node> nodes) { if (nodes == null) throw new ArgumentException(nameof(nodes)); if (!IsInitialized) return false; HashSet<Edge> alreadyCovered = new HashSet<Edge>(); foreach (var element in nodes) { foreach (var neighbour in element.Neighbours) { alreadyCovered.Add(new Edge(element, neighbour)); } if (alreadyCovered.Count == _graph.TotalEdges) break; } return alreadyCovered.Count == _graph.TotalEdges; } 
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.
1 2 3 4 5 6 7 8 9 
public void AddNewSolution(ICollection<Node> nodes) { if (nodes == null) throw new ArgumentException(nameof(nodes)); if (!IsInitialized) return; if (nodes.All(n => _graph.ContainsNode(n.Key) && _graph == n.Parent))) { _currentCover = new HashSet<Node>(nodes); } } 
Full code of MinimumVertexCover.cs
can be found in Graphinder
repository on GitHub or via the link provided below:
MinimumVertexCover.cs @ GitHub.com
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
.
Hm… I don’t like name of the method “AddNewSolution”. It suggest, that your adding the solution to some set of solutions, but implementation replaces “_currentCover” variable.. So calling again “AddNewSolution” causes the “_currentCover” value lost. I would suggest “SetNewSolution”. And what’s more – I would suggest to return bool that indicates whether operation is successfully done. Now, we don’t know if our nodes was set correctly or not :)
Yeah, I guess naming for the method might be ambiguous – good point! :) As for a classic bool return for reporting the result, I had some other idea for that but I guess KISS principle will win here.
Thanks for comment!