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.

2 thoughts on “Graphinder – Minimum Vertex Cover problem”

  1. 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 :)

    1. 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!

Leave a Reply

Your email address will not be published. Required fields are marked *