Finding “routes” of all-pairs shortest paths with Floyd-Warshall algorithm in C#

Introduction


In the previous post we saw how to solve all-pairs shortest path problem using Floyd-Warshall algorithm. We also explored several ways to improve algorithm’s performance by using parallelism and vectorisation.

However, if you think about the results of the Floyd-Warshall algorithm, you will quickly realise the interesting moment – we know the distances (values of shortest paths) between vertexes in a graph but we don’t know the “routes” i.e. we don’t know what vertexes contribute to each shortest path, and we can’t rebuild these “routes” from the results we have.

In this post, I invite you to join me and extend the Floyd-Warshall algorithm. This time, we are going to make sure we can calculate the distance and rebuild the “route”.

Continue reading “Finding “routes” of all-pairs shortest paths with Floyd-Warshall algorithm in C#”

Building, Testing and Debugging Visual Studio C++ project in Visual Studio Code

Notice

Starting from 2021/08/20 (as the result of this PR) Visual Studio Code documentation has been updated to include information about how to run Visual Studio Code outside of Developers Command Prompt.However, if you are interested in a story of how this happened or you need to run and debug Visual Studio tests using vstest.console.exe right from Visual Studio Code then, I invite you to continue reading the post.

Introduction


I started to code in C/Win32 API in the university and I continue to do this almost every day. I am not a professional C/C++ developer nor Windows internals specialist, however I like to write in C. Why I am telling this? Because it won’t be a surprise, all my C/C++ projects were always written in Visual Studio with all it’s goodies like IntelliSense, projects support and extensions like Visual Assist.

However, in a last few years working with .NET Core I’ve found myself doing almost all my coding in Visual Studio Code and to be honest I get used to its simplicity and blazing speed. So for me it was kind of logical and full of sense step to move my C/Win32 API development from Visual Studio to Visual Studio Code, and having previously a slick transition experience in .NET, I was expecting somewhat similar but it turned out to be not that simple, especially if you don’t want to cut off Visual Studio completely.

In this post I would like to share how you can configure Visual Studio Code to build, test and debug Visual Studio C++ project.

Continue reading “Building, Testing and Debugging Visual Studio C++ project in Visual Studio Code”

Implementing Floyd-Warshall algorithm for solving all-pairs shortest paths problem in C#

Notice

This post is a free form translation (with some clarifications) of my post in Russian published on techrocks.ru. So if you know Russian, you are welcome to read it there. Otherwise, I invite you to join me here and have some fun.

Introduction


All of us solve a “shortest path” problem many times a day. Unintentionally of course. We solve it on our way work or when we browse the Internet or when we arrange our things on a desk.

Sounds a bit… too much? Let’s find out.

Imagine, you have decided to meet with friends, well … let’s say in cafe. First of all, you need to find a route (or path) to cafe, so you start looking for available public transport (if you are on foot) or routes and streets (if you are driving). You are looking for a route from your current location to cafe but not “any” route – the shortest or fastest one.

Here is a one more example, which isn’t so obvious as the previous one. During you way work you decide to take a “short cut” through a side street because well… it is a “short cut” and it is “faster” to go this way. But how did you know this “short cut” is faster? Based on personal experience you solved a “shortest path” problem and selected a route, which goes through the side street.

In both examples, the “shortest” route is determined in either distance or time required to get from one place to another. Traveling examples are very natural applications of graph theory and “shortest path” problem in particular. However, what about the example with arranging things on a desk? In this case the “shortest” can represent a number or complexity of actions you have to perform to get, for example, a sheet of paper: open desk, open folder, take a sheet of paper vs take a sheet of paper right from desk.

All of the above examples represent a problem of finding a shortest path between two vertexes in a graph (a route or path between two places, a number of actions or complexity of getting a sheet of paper from one place or another). This class of shortest path problems is called SSSP (Single Source Shortest Path) and the base algorithm for solving these problems is Dijkstra’s algorithm, which has a O(n2) computational complexity.

But, sometimes we need to find all shortest paths between all vertexes. Consider the following example: you are creating a map for you regular movements between home, work and theatre. In this scenario you will end up with 6 routes: work -> home, home -> work, work -> theatre, theatre -> work, home -> theatre and theatre -> home (the reverse routes can be different because of one-way roads for example).

Adding more place to the map will result in a significant grow of combinations – according to permutations of n formula of combinatorics it can be calculated as:

A(k, n) = n! / (n - m)!

// where n - is a number of elements, 
//       k - is a number of elements in permutation (in our case k = 2)

Which gives us 12 routes for 4 places and 90 routes for 10 places (which is impressive). Note… this is without considering intermediate points between places i.e., to get from home to work you have to cross 4 streets, walk along the river and cross the bridge. If we imagine, some routes can have common intermediate points… well … as the result we will have a very large graph, with a lot of vertexes, where each vertex will represent either a place or a significant intermediate point. The class of problems, where we need to find all shortest paths between all pairs of vertexes in the graph, is called APSP (All Pairs Shortest Paths) and the base algorithm for solving these problems is Floyd-Warshall algorithm, which has O(n3) computational complexity.

And this is the algorithm we will implement today 🙂

Continue reading “Implementing Floyd-Warshall algorithm for solving all-pairs shortest paths problem in C#”

Using secrets in Azure Container Instances

Introduction


At work I am involved in one of our internal project development. This project is a relatively small (less than 30 pages) ASP.NET Core 3.1 Razor Pages application. From it’s first days application is hosted in Azure using Azure Container Instance, Azure SQL Database and Azure Key Vault (continues integration and deployment pipelines are powered by Azure DevOps).

There is nothing special in such setup, however as it happens with setups of this kind, there is one thing that has to be managed prior to implementing it – “How to securely pass secrets to Azure Container Instances and securely read secrets stored in Azure Key Vault (ex. read database connection string) from within Azure Container Instances?”

Finding the answer was my responsibility, so I have created a dummy project and dived into Azure documentation. This post contains results of my findings composed, as I hope, in easy and understandable format.

Continue reading “Using secrets in Azure Container Instances”

What is the difference between ToArray and ToList?

Introduction


In the beginning of June I attended .NET Summit conference in Minsk, Belarus. Besides interesting presentations (recording are available on YouTube, language is Russian / English) there were interesting quizzes.

One of the questions was:

What is the difference between ToArray and ToList?

Software Engineer

Hmm… what could be the difference besides one returns T[] and another one returns List<T>?

If you don’t know the answer or just like digging into sources of dotnet/corefx then I invite you to join me and find out the answer!

Note

All code snippets were taken from release/3.0 branch of dotnet/corefx repository. All code snippets were truncated to make them more representative (removed input argument checks, contracts, …, etc.).

Tests were targeting .NET Core 3.0 preview 7. However most of the information should be relevant for .NET Core 2.0+ and .NET Framework 4.5+.

Continue reading “What is the difference between ToArray and ToList?”

“html-escape” – a contributor’s story about Visual Studio Code extension

Have you ever find yourself typing ‘Escape html online‘ in Google search?

I’ve had 🙂

Recently I got tired of these searches and decided to look for an extension to Visual Studio Code, which I use for writing. This is where I met html-escape by Raymond Camden.

I used it for quite awhile a come up with some ideas of how to make it better. The problem was, these improvements required significant design changes. This has made me decide to start contributing.

In this post I invite you to join me in making these design changes. We will take a look at existing application feature set, get acquainted with some of Visual Studio Code concepts and theory, discuss application requirements, create application design (no architectural diagrams) and then literally implement all existing application features fitting them into our design.

Interested? Then let’s start.

Continue reading ““html-escape” – a contributor’s story about Visual Studio Code extension”