DEV Community: Anton Yarkov

The low-cost path to AI Mastery: building a Wiki Navigator with pure Similarity Search

Anton Yarkov — Wed, 01 Oct 2025 15:31:16 +0000

The world of Artificial Intelligence (AI) and Large Language Models (LLMs) often conjures images of immense computing power, proprietary platforms, and colossal GPU clusters. This perception can create a high barrier to entry, discouraging curious developers from exploring the fundamentals.

I recently embarked on a project—a sophisticated yet simple AI-powered chatbot I call the Wiki Navigator—that proves this complexity is often unnecessary for learning the essentials. By focusing on core concepts like tokenization, vector embeddings, and cosine similarity, I built a functional RAG (Retrieval Augmented Generation) search solution that operates across 9,000 documents in the Chromium open-source codebase. It took me a few hours to run and next day I was able to re-use the same codebase to train Chat bot on open-source books about the Rust programming language to have useful help during my Rust learning journey.

The main revelation? You don't need to dive too deep with huge GPU cards to learn how the essentials of LLM and AI work. It is a supremely rewarding and practical experience to learn by doing, immediately yielding results without incurring significant expense.

The magic of Vector Embeddings

Our Wiki Navigator functions not by generating novel text, but by reliably retrieving contextual replies and relevant links from source documentation, preventing hallucination by strictly following the links in the wiki. It is essentially a contextual search engine powered by Retrieval Augmented Generation (RAG).

The core concept is surprisingly straightforward:

Preparation (Training Phase): Convert all your documents (like Q&A pairs and wiki content) into a digital representation known as vector embeddings (watch this great explanation if you didn't yet). This process, which can take an hour or so for large corpora, creates a vector index.
Querying (Query Phase): When a user submits a question, that query is also converted into a vector embedding.
Comparison: The system compares the query vector against the document vectors using the Cosine Similarity operation to find the closest matches. If we found two vectors near to each other - that most likely means match in terms of the context (though, as we can see later, not always).

This simple process works effectively for tasks like navigating documentation and finding relevant resources.

Ensuring algorithmic parity

While many articles focus on the theory of similarity search, the real fun lies in implementing it. Interestingly enough, to run simplistic MVP you take NO AI MODEL, which makes it possible to be deployed statically, running entirely in the browser, making it perfect for hosting on platforms like GitHub Pages. This static deployment requires the training application (C#) and the client application (JavaScript) to share identical algorithms for tokenization and vector calculation, ensuring smooth operation and consistent results.

The training pipeline, which prepares the context database, is built in C# (located in TacTicA.FaqSimilaritySearchBot.Training/Program.cs). During training, data is converted into embeddings using services like the SimpleEmbeddingService (hash-based, in case of NO AI model for static web site deployment), the TfIdfEmbeddingService (TF-IDF/Keyword-Based Similarity - an extended version of trainer), or the sophisticated OnnxEmbeddingService (based on the pre-trained all-MiniLM-L6-v2 transformer model, which would require you to run some good back-end with AI model loaded into RAM).

In this article I mainly focus on the first option - simplistic hash-based approach, while I do also have an AI-Model-based solution running in production on tactica.xyz. This is full-fledged React application running all comparisons on the back-end, but the fundamental concepts stay the same.

The core mathematical utilities that define tokenization and vector operations reside in C# within TacTicA.FaqSimilaritySearchBot.Shared/Utils/VectorUtils.cs. To ensure the client-side browser application running in JavaScript via TacTicA.FaqSimilaritySearchBot.Web/js/chatbot.js (or TacTicA.FaqSimilaritySearchBot.WebOnnx/js/chatbot.js for the AI-model based one) can process new user queries identically to C# training algorithm, we must replicate those crucial steps.

It is also critical to make sure that all calcuations produce same outputs in both C# and JavaScript, during both training and running, which might take additional efforts, but still pretty straightforward. For example these two:

From SimpleEmbeddingService.cs:

    // This method is taken from chatbot.js to be very similar to let Simple Embedding Service work at all!
    private Func<double> SeededRandom(double initialSeed)
    {
        double seed = initialSeed;
        return () =>
        {
            seed = (seed * 9301.0 + 49297.0) % 233280.0;
            return seed / 233280.0;
        };
    }

From chatbot.js:

    // Seeded random number generator
    seededRandom(seed) {
        return function() {
            seed = (seed * 9301 + 49297) % 233280;
            return seed / 233280;
        };
    }

C# training example: vector utility

In the C# training application, the VectorUtils class is responsible for calculating cosine similarity, which is the heart of the comparison operation:

// Excerpt from TacTicA.FaqSimilaritySearchBot.Shared/Utils/VectorUtils.cs
// This function calculates how 'similar' two vectors (embeddings) are.

public static double CalculateCosineSimilarity(float[] vectorA, float[] vectorB)
{
    // [C# Implementation Detail: Normalization and dot product calculation 
    // to determine similarity score between 0.0 and 1.0]

    // ... actual calculation happens here ...

    // return similarityScore; 
}

Running training set will take a hour, because we are NOT using GPU's, parallelization or any other fancy staff. Because we are learning the basics and do not want overcomplicate things for now:

JavaScript client example: real-time search

The client application must then perform the same calculation in real time for every user query against the pre-computed index. The system relies on fast in-memory vector search using this very simplistic algorithm.

// Excerpt from TacTicA.FaqSimilaritySearchBot.Web/js/chatbot.js
// This function is executed when the user submits a query.

function performSimilaritySearch(queryVector, documentIndex) {
    let bestMatch = null;
    let maxSimilarity = 0.0;

    // Convert user query to vector (if using the simple hash/TF-IDF approach)
    // or use ONNX runtime for transformer model encoding.

    // Iterate through all pre-calculated document vectors
    for (const [docId, docVector] of Object.entries(documentIndex)) {

        // Ensure the JS implementation of Cosine Similarity is identical to C#!
        const similarity = calculateCosineSimilarity(queryVector, docVector); 

        if (similarity > maxSimilarity) {
            maxSimilarity = similarity;
            bestMatch = docId;
        }
    }

    // Apply the configured threshold (default 0.90) for FAQ matching.
    if (maxSimilarity >= CONFIG.SimilarityThreshold) {
        // [Action: Return FAQ Response with Citation-Based Responses]
    } else {
        // [Action: Trigger RAG Fallback for Full Document Corpus Search]
    }

    return bestMatch;
}

By ensuring that the underlying vector utilities are functionally identical in both C# and JavaScript, we guarantee that the query result will be consistent, regardless of whether the embedding was calculated during the training phase or the real-time query phase.

Beyond the Simple Lookup

Our bot is far more sophisticated than a simple keyword search. It is engineered with a three-phase architecture to handle complex queries:

Phase 1: Context Database Preparation. This is the initial training where Q&A pairs and document chunks are converted to vectors and stored in an index.
Phase 2: User Query Processing. When a query is received, the system first attempts Smart FAQ Matching using the configured similarity threshold (default: 0.90). If the confidence score is high, it returns a precise answer.
Phase 3: General Knowledge Retrieval (RAG Fallback). If the FAQ match confidence is low, the system activates RAG Fallback, searching the full document corpus, performing Top-K retrieval, and generating synthesized answers with source attribution.

This sophisticated fallback mechanism ensures that every answer is citation-based, providing sources and confidence scores. Depending on the use cases you can switch ON or OFF citations as the quality of response hugely depends on the amount of Questions & Answers pairs you used during training. Low amount of Q&A would make this bot find irrelevant citations more frequently. Thus, if you simply don't have enough Q&A - bot still can be useful by returning valid URL links, but not citations. With good amount of Q&A you can notice the quality of answers higher and higher.

The nuances of Similarity Search

This hands-on exploration immediately exposes fascinating, practical insights that often remain hidden in theoretical papers.

For instance, comparing approaches side-by-side reveals that the bot can operate both with an AI model (using the transformer-based ONNX embedding) and even without it, leveraging pure hash-based embeddings. While the hash-based approach is simple, the efficacy of embeddings, even theoretically, is limited, as discussed in the paper "On the Theoretical Limitations of Embedding-Based Retrieval".

Furthermore, working directly with cosine similarity illuminates concepts like "Cosine Similarity Abuse"—a fun, practical demonstration of how one can deliberately trick non-intelligent AI systems. This is only scratch of a surface in the bigger "Prompt Injection" problem (example good reading) that truly puts a serious threat for the users of AI and software engineers who builts AI for production use.

Your next AI project starts now

Building a robust, functional bot that handles 9,000 documents across a complex project like Chromium requires technical diligence, but it does not require massive infrastructure. This project proves that the fundamental essentials of LLM and AI—tokenization, vectorization, and similarity comparison—are perfectly accessible to anyone willing to dive into the code.

The Wiki Navigator serves as a powerful demonstration of what is possible with similarity search on your own internal or corporate data.

I encourage you to explore the open-source code and see how quickly you can achieve tangible results:

Source Code: https://github.com/tacticaxyz/tactica.faq.similaritysearch
Chromium Demo: https://tactica.xyz/#/chromium-similarity-search
Rust Demo: https://tactica.xyz/#/rust-similarity-search

This is just the beginning. Future explorations can dive deeper into topics like advanced vector search techniques, leveraging languages like Rust in AI tooling, and optimizing AI for browser-based applications. Start building today!

Algorithmic Alchemy: Exploiting Graph Theory in the Foreign Exchange

Anton Yarkov — Thu, 05 Oct 2023 09:13:59 +0000

If you're familiar with the FinTech startup industry, you may have heard of Revolut, a well-known FinTech giant based in London, UK. Founded in 2015, Revolut has garnered substantial investments and become one of the fastest-growing startups in the UK, providing banking services to many European citizens.

While banking operations are often shrouded in mystery when it comes to how they generate revenue, some key figures about Revolut for the years 2020 and 2021 have shed some light on their income sources:

As illustrated, a significant portion of this neobank's revenue comes from Foreign Exchange (FX), wealth management (including cryptocurrencies), and card services. Notably, in 2021, FX became the most profitable sector.

A friend of mine, who is also a software engineer, once shared an intriguing story about his technical interview at Revolut's Software Engineering department a few years back. He was tasked with developing an algorithm to identify the most profitable way to convert two currencies using one or multiple intermediate currencies. In other words, they were looking for a strategy for Currency Arbitrage.

Currency Arbitrage is a trading strategy wherein a currency trader leverages different spreads offered by brokers for a particular currency pair through multiple trades.

It was explicitly mentioned in the task that the algorithm's foundation must be rooted in graph theory.

FX Basics

FX, or Foreign Exchange, plays a pivotal role in global trade, underpinning the functioning of our interconnected world. It's evident that FX also plays a substantial role in making banks some of the wealthiest organizations.

The profit generated from foreign exchange is primarily the difference or spread between the buying (BID) and selling (ASK) prices. While this difference might appear minuscule per transaction, it can accumulate into millions of dollars in profits given the volume of daily operations. This allows some companies to thrive solely on these highly automated financial operations.

In the realm of FX (Foreign Exchange), we always work with pairs of currencies, such as EUR/USD. In most cases, these exchanges are bidirectional (i.e., EUR/USD and USD/EUR), and the exchange rate value differs in each direction.

An Arbitrage Pair represents a numerical ratio between the values of two currencies (EUR and US Dollar, for example), determining the exchange rate between them.

Potentially, we can use multiple intermediate currencies for profitable trading, known as a sure bet.

Arbitrage sure bet is a set of pairs to be used in a circular manner. Read more

Many providers employ mathematical modeling and analysis to secure their own profits and prevent others from profiting off them. Hence, the term potentially is emphasized here.

Sure bet length refers to the number of pairs that constitute a set of potential arbitrage opportunities.

In the real world, exchange rates can vary among different banks or exchange platforms. It's not uncommon for tourists to traverse a city to find the best possible rate. With computer software, this process can be accomplished within milliseconds when you have access to a list of providers.

In practical profitable trades, multiple steps might involve conversions through various currencies across different exchange platforms. In other words, the Arbitrage Circle can be quite extensive.

Arbitrage Circle entails acquiring a currency, transferring it to another platform, conducting an exchange for other currencies, and ultimately returning to the original currency.

The exchange rate between two currencies via one or more intermediate currencies is calculated as the product of exchange rates of these intermediate transactions.

An example

For example, let's imagine we want to buy Swiss Franks for US Dollar, then exchange Franks to Japanese Yens, and then sell Yens for US Dollar again. In Autumn, 2023, we have following exchange rates:

We can buy 0.91 CHF (Swiss Frank) for 1 USD.
We can buy 163.16 Japanese Yens for 1 CHF.
We can buy 0.0067 USD for 1 Japanese Yen.

Let's present it with a table:

1           USD |   1           CHF |   1       YEN
0.91        CHF |   163.16      YEN |   0.0067  USD
----------------|-------------------|--------------
1.098901099     |   0.006128953     |   149.2537313

Now, we need to find a product of those values. A sequence of transactions becomes profitable when this product yields a value less than one:

1.098901099 * 0.006128953 * 149.2537313 = 1.005240803

As we can see the result is a larger than one, so it looks like we lost 0.05% of our money. But how many exactly? We can sort it out like this:

0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars

So, after selling 1 US Dollar in the beginning we have got 0.994 - less than 1 US Dollar in the end.

In simpler terms, Arbitrage Cycle is profitable when one unit of currency can be obtained for less than one unit of the same currency.

Let's imagine we have found an opportunity to take 0.92 CHF per 1 US Dollar in the initial transaction, instead of 0.91 CHF:

1           USD |   1           CHF |   1       YEN
0.92        CHF |   163.16      YEN |   0.0067  USD
----------------|-------------------|--------------
1.086956522     |   0.006128953     |   149.2537313

A product will be less than 1:

1.086956522 * 0.006128953 * 149.2537313 = 0.994314272

Which means, in the real currencies it will give us more than 1 US Dollar:

0.92 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 1.00571824 US Dollars

Wuolah, we got some PROFIT! Now, let's see how to automate this using graphs analysis.

So, the formula to check for profits or losses in an Arbitrage Circle of 3 Arbitrage Pairs would look like this:

USD/CHF * CHF/YEN * YEN/USD < 1.0

Graph representation

To automate those processes we can use graphs. The tables mentioned earlier can be naturally transformed into a matrix representation of a graph, where nodes represent currencies and edges represent bidirectional exchanges.

Hence, it is straightforward to represent two pairs exchange in matrix like this:

EUR  USD
 1    1  EUR 
 1    1  USD

Depending on the number of pairs involved, our matrix can expand:

EUR  USD  YEN  CHF  
 1    1    1    1  EUR 
 1    1    1    1  USD
 1    1    1    1  YEN
 1    1    1    1  CHF

Consequently, our table can become considerably larger, even for just two currencies, if we take into account more exchange platforms and resources.

To address real currency arbitrage problems, a complete graph that encompasses all relationships for currency quotes is often utilized. A three-currency exchange table might appear as follows:

   USD     CHF     YEN
{ 1.0,    1.10,   0.0067 }  USD
{ 0.91,   1.0,    0.0061 }  CHF
{ 148.84, 163.16, 1.0    }  YEN

We can employ a simple graph data structure to represent our currency pairs in memory:

class GraphNode
{
public:
    string Name;
};

class Graph
{
public:
    vector<vector<double>> Matrix;
    vector<GraphNode> Nodes;
};

Now, we only need to find out how to traverse this graph and find the most profitable circle. But there is still one problem...

Math saves us, again

Classical graph algorithms are not well-suited for working with the product of edge lengths because they are designed to find paths defined as the sum of these lengths (see implementations of any well-known classic path-finding algorithms BFS, DFS, Dijkstra or even A-Star).

However, to circumvent this limitation, there is a mathematical way to transition from a product to a sum: logarithms. If a product appears under a logarithm, it can be converted into a sum of logarithms.

On the right side of this equation, the desired number is less than one, indicating that the logarithm of this number must be less than zero:

LogE(USD/CHF) * LogE(CHF/YEN) * LogE(YEN/USD) < 0.0

This simple mathematical trick allows us to shift from searching for a cycle with an edge length product less than one to searching for a cycle where the sum of the edge lengths is less than zero.

Our matrix values converted to a LogE(x) and rounded with 2 digits after the point, now look like this:

   USD      CHF     YEN
{ 0.0,      0.1,     -5.01 }  USD
{ -0.09,    0.0,     -5.1  }  CHF
{ 5.0,      5.09,    0.0   }  YEN

Now this problem becomes more solvable using classical graph algorithms. What we need is to traverse the graph looking for most profitable path of exchange.

Graph algorithms

Every algorithm has its limitations. I mentioned some of them in my previous article.

We cannot apply classical BFS, DFS or even Dijkstra here because our graph may contain negative weights, which may lead to Negative Cycles while it traverses the graph. Negative cycles pose a challenge to the algorithm since it continually finds better solutions on each iteration.

To address this issue, the Bellman-Ford algorithm simply limits the number of iterations. It traverses each edge of the graph in a cycle and applies relaxation for all edges no more than V-1 times (where V is a number of nodes).

As such, the Bellman-Ford algorithm lies at the heart of this Arbitrage system, as it enables the discovery of paths between two nodes in the graph that meet two essential criteria: they contain negative weights and are not part of negative cycles.

While this algorithm is theoretically straightforward (and you can find billion videos about it), practical implementation for our needs requires some effort. Let's dig into it.

Bellman-Ford algorithm implementation

As the aim of this article is computer science, I will use imaginary exchange rates that has nothing to do with the real ones.

For a smoother introduction to the algorithm, let's use a graph that doesn't contain negative cycles at all:

graph.Nodes.push_back({ "USD" });
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" });
graph.Nodes.push_back({ "EUR" });
// Define exchange rates for pairs of currencies below
//                 USD    CHF   YEN   GBP   CNY   EUR
graph.Matrix = { { 0.0,   0.41, INF,  INF,  INF,  0.29 },  // USD
                 { INF,   0.0,  0.51, INF,  0.32, INF },   // CHF
                 { INF,   INF,  0.0,  0.50, INF,  INF },   // YEN
                 { 0.45,  INF,  INF,  0.0,  INF,  -0.38 }, // GBP
                 { INF,   INF,  0.32, 0.36, 0.0,  INF },   // CNY
                 { INF, -0.29,  INF,  INF,  0.21, 0.0 } }; // EUR

The code example below finds a path between two nodes using the Bellman-Ford algorithm when the graph lacks negative cycles:

vector<double> _shortestPath;
vector<int> _previousVertex;

void FindPath(Graph& graph, int start)
{
    int verticesNumber = graph.Nodes.size();

    _shortestPath.resize(verticesNumber, INF);
    _previousVertex.resize(verticesNumber, -1);

    _shortestPath[start] = 0;

    // For each vertex, apply relaxation for all the edges V - 1 times.
    for (int k = 0; k < verticesNumber - 1; k++)
        for (int from = 0; from < verticesNumber; from++)
            for (int to = 0; to < verticesNumber; to++)
                if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
                {
                    _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
                    _previousVertex[to] = from;
                }
}

Running this code for the Chinese Yuan fills the _previousVertex array and yields results like this:

Path from 4 to 0 is : 4(CNY) 3(GBP) 0(USD)
Path from 4 to 1 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF)
Path from 4 to 2 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF) 2(YEN)
Path from 4 to 3 is : 4(CNY) 3(GBP)
Path from 4 to 4 is : 4(CNY)
Path from 4 to 5 is : 4(CNY) 3(GBP) 5(EUR)

As you can observe, it identifies optimal paths between CNY and various other currencies.

And again, I will not focus on finding only one best one, as it is relatively simple task and not the goal of the article.

The above implementation works well in ideal cases but falls short when dealing with graphs containing negative cycles.

Detecting negative cycles

What we truly need is the ability to identify whether a graph contains negative cycles and, if so, pinpoint the problematic segments. This knowledge allows us to mitigate these issues and ultimately discover profitable chains.

The number of iterations doesn't always have to reach precisely V - 1. A solution is deemed found if, on the (N+1)-th cycle, no better path than the one on the N-th cycle is discovered. Thus, there's room for slight optimization.

The code mentioned earlier can be enhanced to not only find paths but also detect whether the graph contains negative cycles, including the optimization I mentioned:

vector<double> _shortestPath;
vector<int> _previousVertex;

bool ContainsNegativeCycles(Graph& graph, int start)
{
    int verticesNumber = graph.Nodes.size();

    _shortestPath.resize(verticesNumber, INF);
    _previousVertex.resize(verticesNumber, -1);

    _shortestPath[start] = 0;

    // For each vertex, apply relaxation for all the edges V - 1 times.
    for (int k = 0; k < verticesNumber - 1; k++)
    {
        updated = false;
        for (int from = 0; from < verticesNumber; from++)
        {
            for (int to = 0; to < verticesNumber; to++)
            {
                if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
                {
                    _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
                    _previousVertex[to] = from;
                    updated = true;
                }
            }
        }
        if (!updated) // No changes in paths, means we can finish earlier.
            break;
    }

    // Run one more relaxation step to detect which nodes are part of a negative cycle. 
    if (updated)
        for (int from = 0; from < verticesNumber; from++)
            for (int to = 0; to < verticesNumber; to++)
                if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
                    // A negative cycle has occurred if we can find a better path beyond the optimal solution.
                    return true;

    return false;
}

And now we play with a more intricate graph that includes negative cycles:

graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" });
graph.Nodes.push_back({ "EUR" });
graph.Nodes.push_back({ "XXX" });
graph.Nodes.push_back({ "YYY" }); // 8  (Index = 7)
//                 USD  CHF  YEN  GBP   CNY  EUR  XXX  YYY
graph.Matrix = { { 0.0, 1.0, INF, INF,  INF, INF, INF, INF },   // USD
                 { INF, 0.0, 1.0, INF,  INF, 4.0, 4.0, INF },   // CHF
                 { INF, INF, 0.0, INF,  1.0, INF, INF, INF },   // YEN
                 { INF, INF, 1.0, 0.0,  INF, INF, INF, INF },   // GBP
                 { INF, INF, INF, -3.0, 0.0, INF, INF, INF },   // CNY
                 { INF, INF, INF, INF,  INF, 0.0, 5.0, 3.0 },   // EUR
                 { INF, INF, INF, INF,  INF, INF, 0.0, 4.0 },   // XXX
                 { INF, INF, INF, INF,  INF, INF, INF, 0.0 } }; // YYY

Our program simply halts and displays a message:

Graph contains negative cycle.

We was able to indicate the problem, however, we need to navigate around problematic segments of the graph.

Avoiding negative cycles

To accomplish this, we'll mark vertices that are part of negative cycles with a constant value, NEG_INF:

bool FindPathsAndNegativeCycles(Graph& graph, int start)
{
    int verticesNumber = graph.Nodes.size();
    _shortestPath.resize(verticesNumber, INF);
    _previousVertex.resize(verticesNumber, -1);
    _shortestPath[start] = 0;

    for (int k = 0; k < verticesNumber - 1; k++)
        for (int from = 0; from < verticesNumber; from++)
            for (int to = 0; to < verticesNumber; to++)
            {
                if (graph.Matrix[from][to] == INF) // Edge not exists
                {
                    continue;
                }

                if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
                {
                    _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
                    _previousVertex[to] = from;
                }
            }

    bool negativeCycles = false;

    for (int k = 0; k < verticesNumber - 1; k++)
        for (int from = 0; from < verticesNumber; from++)
            for (int to = 0; to < verticesNumber; to++)
            {
                if (graph.Matrix[from][to] == INF) // Edge not exists
                {
                    continue;
                }

                if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
                {
                    _shortestPath[to] = NEG_INF;
                    _previousVertex[to] = -2;
                    negativeCycles = true;
                }
            }
    return negativeCycles;
}

Now, if we encounter NEG_INF in the _shortestPath array, we can display a message and skip that segment while still identifying optimal solutions for other currencies. For example, with Node 0 (representing USD):

Graph contains negative cycle.
Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 1(CHF)
Path from 0 to 2 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 3 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 4 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 5 is : 0(USD) 1(CHF) 5(EUR)
Path from 0 to 6 is : 0(USD) 1(CHF) 6(XXX)
Path from 0 to 7 is : 0(USD) 1(CHF) 5(EUR) 7(YYY)

Whoala! Our code was able to identify a number of profitable chains despite the fact that our data was "a bit dirty".

All the code examples mentioned above including test data is shared with you on my GitHub.

Even little fluctuations matter

Let's now consolidate what we've learned. Given a list of exchange rates for three currencies, we can easily detect negative cycles:

graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" }); // 3 (Index = 2)

// LogE(x) table:   USD      CHF     YEN
graph.Matrix = { { 0.0,    0.489,  -0.402 },   // USD
                 { -0.489, 0.0,    -0.891 },   // CHF
                 { 0.402,  0.89,   0.0    } }; // YEN
from = 0;
FindPathsAndNegativeCycles(graph, from);

Result:

Graph contains negative cycle.
Path from 0 to 0 is: Infinite number of shortest paths (negative cycle).
Path from 0 to 1 is: Infinite number of shortest paths (negative cycle).
Path from 0 to 2 is: Infinite number of shortest paths (negative cycle).

However, even slight changes in the exchange rates (i.e., adjustments to the matrix) can lead to significant differences:

// LogE(x) table:   USD      CHF     YEN
graph.Matrix = { { 0.0,    0.490,  -0.402 },    // USD
                 { -0.489, 0.0,    -0.891 },    // CHF
                 { 0.403,  0.891,   0.0    } }; // YEN
from = 0;
FindPathsAndNegativeCycles(graph, from);

Look, we have found one profitable chain:

Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF)
Path from 0 to 2 is : 0(USD) 2(YEN)

We can apply these concepts to much larger graphs, involving multiple currencies:

graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" }); // 5  (Index = 4)
// LogE(x) table:  USD     CHF     YEN    GBP   CNY
graph.Matrix = { { 0.0,    0.490, -0.402, 0.7,  0.413 },   // USD
                 { -0.489, 0.0,   -0.891, 0.89, 0.360 },   // CHF
                 { 0.403,  0.891,  0.0,   0.91, 0.581 },   // YEN
                 { 0.340,  0.405,  0.607, 0.0,  0.72 },    // GBP
                 { 0.403,  0.350,  0.571, 0.71, 0.0 } };   // CNY
from = 0;
runDetectNegativeCycles(graph, from);

As a result, we might find multiple candidates to get profit:

Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF)
Path from 0 to 2 is : 0(USD) 2(YEN)
Path from 0 to 3 is : 0(USD) 2(YEN) 3(GBP)
Path from 0 to 4 is : 0(USD) 2(YEN) 4(CNY)

There are two important factors, though:

Time is a critical factor in implementing arbitrage processes, primarily due to the rapid fluctuations in currency prices. As a result, the lifespan of a sure bet is exceedingly brief.
Platforms levy commissions for each transaction.

Therefore, minimizing time costs and reducing commissions are paramount, achieved by limiting the length of the sure bet.

Empirical experience suggests that an acceptable sure bet length typically ranges from 2 to 3 pairs. Beyond this, the computational requirements escalate and trading platforms impose larger commissions.

Thus, to make an income is not enough to have such technologies, but you also need access to the low-level commissions. Usually, only large financial institutions have such a resource in their hands.

Automation using smart contracts

I've delved into the logic of FX operations and how to derive profits from them, but I haven't touched upon the technologies used to execute these operations. While this topic slightly veers off-course, I couldn't omit mentioning smart contracts.

Using smart contracts is one of the most innovative ways to conduct FX operations today. Smart contracts enable real-time FX operations without delays or human intervention (except for the creation of the smart contract).

Solidity is the specialized programming language for creating smart contracts that automate financial operations involving cryptocurrencies. The world of smart contracts is dynamic and subject to rapid technological changes and evolving regulations. It's an area with considerable hype and significant risks related to wallets and legal compliance.

While there are undoubtedly talented individuals and teams profiting from this field, there are also regulatory bodies striving to ensure market rules are upheld.

Why are we looking into this?

Despite the complexity, obscurity, and unpredictability of global economics, Foreign Exchange remains a hidden driving force in the financial world. It's a crucial element that enables thousands of companies and millions of individuals worldwide to collaborate, provide services, and mutually benefit one another in a peaceful manner, transcending borders.

Of course, various factors, such as politics, regulations, and central banks, influence exchange rates and FX efficiency. These complexities make the financial landscape intricate. Yet, it's essential to believe that these complexities serve a greater purpose for the common good.

Numerous scientific papers delve into the existence and determination of exchange rates in the global economy, to mention a few:

These papers shed light on some fundamental mechanisms of Foreign Exchanges, which is still hard to understand and fit into one model.

Though, playing with code and trying to find a solution for a practical problem helped me to get a little more clue on it. I hope you enjoied this little exploration trip as much as I am.

Stay tuned!

Crafting Mazes with Graph Theory

Anton Yarkov — Wed, 06 Sep 2023 12:03:59 +0000

In our previous post, we delved into problems of pathfinding in graphs, which are inherently connected to solving mazes.

When I set out to create a maze map for the Wall-E project, I initially expected to find a quick and easy way to accomplish this task. However, I quickly found myself immersed in the vast and fascinating world of mazes and labyrinths.

I was unaware of the breadth and depth of this topic before. I discovered that mazes can be classified in seven different ways, each with numerous variations and countless algorithms for generating them.

Surprisingly, I couldn't find any algorithmic books that comprehensively covered this topic, and even the Wikipedia-page didn't provide a systematic overview. Fortunately, I stumbled upon a fantastic resource that covers various maze types and algorithms, which I highly recommend exploring.

I embarked on a journey to learn about the different classifications of mazes, including dimensional and hyperdimensional variations, perfect mazes versus unicursal labyrinths, planar and sparse mazes, and more.

How to create a maze

My primary goal was to generate a 2D map representing a maze.

While it would have been enticing to implement various maze generation algorithms to compare them, I also wanted a more efficient approach. The quickest solution I found involved randomly selecting connected cells. That's precisely what I did with mazerandom. This one-file application creates a grid table of 20 x 20 cells and then randomly connects them using a Depth-First Search (DFS) traversal. In other words, we're simply carving passages in the grid.

If you were to do this manually on paper, it would look something like this:

To achieve this algorithmically, we apply Depth-First Search to the grid of cells. Let's take a look at how it's done in the Main.cpp.

As usual, we represent the grid of cells as an array of arrays, and we use a stack for DFS:

vector<vector<int>> maze_cells; // A grid 20x20
stack<Coord> my_stack;      // Stack to traverse the grid by DFS
my_stack.push(Coord(0, 0)); // Starting from very first cell

We visit every cell in the grid and push its neighbors onto the stack for deep traversal:

...
while (visitedCells < HORIZONTAL_CELLS * VERTICAL_CELLS)
{
    vector<int> neighbours;
    // Step 1: Create an array of neighbour cells that were not yet visited (from North, East, South and West).
    // North is not visited yet?
    if ((maze_cells[offset_x(0)][offset_y(-1)] & CELL_VISITED) == 0) 
    {
        neighbours.push_back(0);
    }
    // East is not visited yet?
    if ((maze_cells[offset_x(1)][offset_y(0)] & CELL_VISITED) == 0) 
    {
        neighbours.push_back(1);
    }
    ... // Do the same for West and South...

The most complex logic involves marking the node as reachable (i.e., no wall in between) with CELL_PATH_S, CELL_PATH_N, CELL_PATH_W, or CELL_PATH_E:

...
    // If we have at least one unvisited neighbour 
    if (!neighbours.empty()) 
    {
        // Choose random neighbor to make it available
        int next_cell_dir = neighbours[rand() % neighbours.size()];

        // Create a path between the neighbour and the current cell
        switch (next_cell_dir)
        {
        case 0: // North
            // Mark it as visited. Mark connection between North and South in BOTH directions.
            maze_cells[offset_x(0)][offset_y(-1)] |= CELL_VISITED | CELL_PATH_S;
            maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_N;
            // 
            my_stack.push(Coord(offset_x(0), offset_y(-1)));
            break;

        case 1: // East
            // Mark it as visited. Mark connection between East and West in BOTH directions.
            maze_cells[offset_x(1)][offset_y(0)] |= CELL_VISITED | CELL_PATH_W;
            maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_E;
            my_stack.push(Coord(offset_x(1), offset_y(0)));
            break;
        ... // Do the same for West and South...
        }
        visitedCells++;
    }
    else
    {
        my_stack.pop();
    }
...

Finally, it calls the drawMaze method to draw the maze on the screen using the SFML library. It draws a wall between two cells if the current cell isn't marked with CELL_PATH_S, CELL_PATH_N, CELL_PATH_W, or CELL_PATH_E.

However, this maze doesn't guarantee a solution. In many cases, it will generate a map with no clear path between two points. While this randomness might be interesting, I wanted something more structured.

The only way to ensure a solution for the maze is to use a predetermined structure that connects every part of the maze in some way.

Creating a Maze Using Graph Theory

Well-known maze generation algorithms rely on graphs. Each cell is a node in the graph, and every node must have at least one connection to other nodes.

As mentioned earlier, mazes come in many forms. Some, called "unicursal" mazes, act as labyrinths with only one entrance, which also serves as the exit. Others may have multiple solutions. However, the process of generation often starts with creating a "perfect" maze.

A "perfect" maze, also known as a simply-connected maze, lacks loops, closed circuits, and inaccessible areas. From any point within it, there is precisely one path to any other point. The maze has a single, solvable solution.

If we use a graph as the internal representation of our maze, constructing a Spanning Tree ensures that there is a path from the start to the end.

In computer science terms, such a maze can be described as a Spanning Tree over the set of cells or vertices.

Multiple Spanning Trees may exist, but the goal is to ensure at least one solution from the start to the end, as shown in the example below:

The image above depicts only one solution, but there are actually multiple paths. No cell is isolated and impossible to reach. So, how do we achieve this?

I discovered a well-designed mazegenerator codebase by @razimantv that accomplishes this, generating mazes in SVG file format.

Therefore, I forked the repository and based my solution on it. Kudos to @razimantv for the elegant OOP design, which allowed me to customize the results to create visually appealing images using the SFML library or generate a text file with the necessary map description for my Wall-E project.

I refactored the code to remove unnecessary components and focus exclusively on rectangular mazes.

However, I retained support for various algorithms to build a spanning tree.

I also added comments throughout the codebase for easier comprehension, so I don't need to explain it in every detail here. The main pipeline can be found in \mazegenerator\maze\mazebaze.cpp:

/**
 * \param algorithm Algorithm that is used to generate maze spanning tree.
 */
void MazeBase::GenerateMaze(SpanningtreeAlgorithmBase* algorithm)
{
    // Generates entire maze spanning tree
    auto spanningTreeEdges = algorithm->SpanningTree(_verticesNumber, _edgesList);

    // Find a solution of a maze based on Graph DFS.
    _Solve(spanningTreeEdges);

    // Build a maze by removing unnecessary edges.
    _RemoveBorders(spanningTreeEdges);
}

I introduced visualization using the SFML graphics library, thanks to a straightforward Draw function.

While DFS is the default algorithm for creating a Spanning Tree, there are multiple algorithms available as options.

The result is a handy utility that generates rectangular "perfect" mazes and displays them on the screen:

As you can see, it contains exactly one input and one output at the left top and right bottom corners. The code still generates SVG file, which is a nice addition (though, it is the core function of the original codebase).

Now, I can proceed with my experiments in the Wall-E project, and I leave you here, hoping that you're inspired to explore this fascinating world of mazes and embark on your own journey.

Stay tuned!

Universal implementation of BFS, DFS, Dijkstra and A-Star algorithms

Anton Yarkov — Sat, 05 Aug 2023 21:50:29 +0000

It turns out that well-known algorithms like BFS, DFS, Dijkstra, and A-Star are essentially variations of the same algorithm.

In other words, it is possible to implement a universal data structure that can switch between these algorithms without requiring changes to its core components. While there are some limitations to consider, exploring this approach is interesting.

You can find all the working code for these algorithms on my GitHub repository here. I recommend experimenting with the code while reading this article since practical experience enhances learning more than just theoretical understanding.

Graph representation

Let's consider a graph with 25 nodes arranged in a 5x5 grid, where we aim to find a path from Node 0 in the top left corner to Node 24 in the bottom right corner:

( 0  ) - ( 1  ) - ( 2  ) - ( 3  ) - ( 4  )
  |        |        |        |        |
( 5  ) - ( 6  ) - ( 7  ) - ( 8  ) - ( 9  )
  |        |        |        |        |
( 10 ) - ( 11 ) - ( 12 ) - ( 13 ) - ( 14 )
  |        |        |        |        |
( 15 ) - ( 16 ) - ( 17 ) - ( 18 ) - ( 19 )
  |        |        |        |        |
( 20 ) - ( 21 ) - ( 22 ) - ( 23 ) - ( 24 )

Each of the mentioned algorithms is capable of achieving this, but they have their own limitations:

Both BFS and DFS algorithms operate on unweighted graphs, disregarding edge weights. Although they can find any path, they do not guarantee the optimal path.
Both Dijkstra's and A-Star algorithms work on weighted graphs but should not be used with graphs containing negative weights. A-Star is usually faster due to its optimization, which incorporates Euclidean coordinates during path finding.

In this article, I do not cover the basic concepts, hoping that you are already familiar with them. If the terminology mentioned above seems daunting to you, you should probably learn the basics as well. However, playing around with these code examples can still be exciting.

To account for these limitations, let's assign imaginary coordinates to each node (X, Y):

(0, 0) - (0, 1) - (0, 2) - (0, 3) - (0, 4)
   |        |        |        |       |
(1, 0) - (1, 1) - (1, 2) - (1, 3) - (1, 4)
   |        |        |        |       |
(2, 0) - (2, 1) - (2, 2) - (2, 3) - (2, 4)
   |        |        |        |       |
(3, 0) - (3, 1) - (3, 2) - (3, 3) - (3, 4)
   |        |        |        |       |
(4, 0) - (4, 1) - (4, 2) - (4, 3) - (4, 4)

Finally, lets assign some weight for every edge in the graph:

(0, 0) -1- (0, 1) -1- (0, 2) -1- (0, 3) -2- (0, 4)
   |          |          |          |         |
   2          1          1          2         2
   |          |          |          |         |
(1, 0) -2- (1, 1) -1- (1, 2) -2- (1, 3) -1- (1, 4)
   |          |          |          |         |
   2          1          1          1         1
   |          |          |          |         |
(2, 0) -1- (2, 1) -1- (2, 2) -1- (2, 3) -2- (2, 4)
   |          |          |          |         |
   2          1          1          1         2
   |          |          |          |         |
(3, 0) -2- (3, 1) -2- (3, 2) -1- (3, 3) -2- (3, 4)
   |          |          |          |         |
   2          1          1          2         2
   |          |          |          |         |
(4, 0) -2- (4, 1) -1- (4, 2) -2- (4, 3) -2- (4, 4)

In C++, this structure may be represented as follows:

class GraphNode
{
public:
    int X;
    int Y;
};

class Graph
{
public:
    vector<vector<pair<int, int>>> Edges;
    vector<GraphNode> Nodes;
};

The edges list in the Graph is represented by an array of arrays, where the index corresponds to the number of the exit node for each edge in the graph. Then, every element contains a pair of values:

The number of the entering node for each edge in the graph.
The weight of the edge.

Using this simple construct, we can traverse every node in the graph and obtain all the necessary information about its connections:

int toNode = graph.Edges[fromNode][neighbourIndex].first;
int weight = graph.Edges[fromNode][neighbourIndex].second;

Now, let's create some custom connections within the graph to observe the effect on how our universal algorithm works. Since this code is not the main focus here, I will provide links to the relevant methods:

Alternatively, it is also possible to lazily generate all the connections and weights in this graph with even less code. However, this approach might not provide a comprehensive understanding of the actual differences in how the algorithms traverse the graph.

Universal algorithm

At the core of the universal path-finding algorithm lies the universal data structure, which we will refer to as the "Queue" for the purposes of this project. However, it is not a classic FIFO (First-In-First-Out) data structure. Instead, it is a general structure that allows us to implement node queuing during traversal while being able to change the queuing mechanism based on the algorithm being used. The interface for this "Queue" is simple:

class pathFindingBase
{
public:
  virtual void insert(int node) = 0;
  virtual int getFirst() = 0;
  virtual bool isEmpty() = 0;
};

Before we delve into the details of the Queue, let's examine the traversal algorithm itself.

Essentially, it closely resembles a typical A-Star or Dijkstra algorithm. First, we need to initialize a set of collections that enable us to:

Maintain a list of nodes that have not been processed yet (colored white), are currently being processed (colored gray), and have been processed/visited (colored black).
Keep track of the current distance of the shortest path from the start node to each node in the collection.
Store a list of pairs of previous-next nodes that allows us to reconstruct the final path afterward.

main.cpp#L18

const int INF = 1000000;
const int WHITE = 0;
const int GREY = 1;
const int BLACK = 2;

/// <summary>
/// Universal algorithm to apply Path search using BFS, DFS, Dijkstra, A-Star.
/// </summary>
vector<int> FindPath(Graph& graph, int start, int finish, int finishX, int finishY)
{
  int verticesNumber = graph.Nodes.size();

  vector<int> nodeColor(verticesNumber, WHITE); // All the nodes are White colored initially
  vector<int> shortestPath(verticesNumber, INF); // Current shortest path found from Start to i is some large/INFinite number from the beginning.
  vector<int> previousVertex(verticesNumber, -1); // Index of the vertex/node that is predecessor of i-th vertex in a shortest path to it.

  // We should use pointers here because we want to pass the pointer to a data-structure
  // so it may receive all the updates automatically on every step.
  shared_ptr<vector<int>> ptrShortestPath = make_shared<vector<int>>(shortestPath);
  shared_ptr<Graph> ptrGraph = make_shared<Graph>(graph);

Next, we need to initialize our data structure. By using the code provided in the GitHub repository, you can simply uncomment the necessary line of code. The code is not designed to select the data structure based on a parameter because I want you to actively experiment with it to gain a better understanding (yes, I'm a tough guy :D).

  //////////////////////////////////////////////////
  // TODO
  // UNCOMMENT DATA STRUCTURE YOU WANT TO USE:

  //dfsStack customQueue;
  //bfsQueue customQueue;
  //dijkstraQueue customQueue(ptrShortestPath);
  //aStarQueue customQueue(finishX, finishY, ptrGraph, ptrShortestPath);

  // END OF TODO
  /////////////////////////////////////////////////

Finally, the algorithm itself. Essentially, it is a combination of all three algorithms with some additional checks. We initialize a "customQueue" and execute the algorithm until it becomes empty. When examining each neighboring node in the graph, we enqueue every node that potentially needs to be traversed next. Then, we call the getFirst() method, which extracts only one node that should be traversed next in the algorithm.

main.cpp#L48

  customQueue.insert(start);
  nodeColor[start] = BLACK;
  ptrShortestPath->at(start) = 0;

  while (!customQueue.isEmpty()) // Traverse nodes starting from start node.
  {
    int current = customQueue.getFirst();

    if (current == finish) // If we found finish node, then let's print full path.
    {
      vector<int> path;

      int cur = finish;
      path.push_back(cur);

      while (previousVertex[cur] != -1) // Recover path node by node.
      {
        cur = previousVertex[cur];
        path.push_back(cur);
      }

      reverse(path.begin(), path.end()); // Since we are at the finish node, reverse list to be at start.

      return path;
    }

    for (int neighbourIndex = 0; neighbourIndex < graph.Edges[current].size(); neighbourIndex++)
    {
      int to = graph.Edges[current][neighbourIndex].first;
      int weight = graph.Edges[current][neighbourIndex].second;

      if (nodeColor[to] == WHITE) // If node is not yet visited.
      {
        nodeColor[to] = GREY; // Mark node as "in progress".
        customQueue.insert(to);
        previousVertex[to] = current;
        ptrShortestPath->at(to) = ptrShortestPath->at(current) + weight; // Calculate cost of moving to this node.
      }
      else // Select the most optimal route.
      {
        if (ptrShortestPath->at(to) > ptrShortestPath->at(current) + weight)
        {
          ptrShortestPath->at(to) = ptrShortestPath->at(current) + weight;
        }
      }
    }

    nodeColor[current] = BLACK;
  }

  return {};
}

Up until this point, the implementation does not differ significantly from other examples you may find in books or on the internet. However, here is where the key aspect lies - getFirst() is the method that serves the main purpose as it determines the exact order of node traversal.

BFS queue

Let's take a closer look at the inner workings of our queue data structure. The queue interface for BFS is the simplest one. bfsQueue.h#L11:

#include <queue>
#include "pathFindingBase.h"

class bfsQueue : public pathFindingBase
{
private:
  queue<int> _queue;

public:
  virtual void insert(int node)
  {
    _queue.push(node);
  }

  virtual int getFirst()
  {
    int value = _queue.front();
    _queue.pop();
    return value;
  }

  virtual bool isEmpty()
  {
    return _queue.empty();
  }
};

In reality, we could simply replace the custom queue interface here with the standard C++ queue provided by the STL (Standard Template Library). However, the goal here is universality. Now, you only need to uncomment the line in the main method and run this algorithm:
//bfsQueue customQueue; // UNCOMMENT TO USE BFS

As a result, BFS finds the path 24<-19<-14<-9<-8<-7<-6<-1<-0.

(0, 0) - (0, 1) - (0, 2) - (0, 3) - (0, 4)
                                       |
                                    (1, 4)
                                       |
                                    (2, 4)
                                       |
                                    (3, 4)
                                       |
                                    (4, 4)

If we consider weights, the final cost of this path will be 11. However, remember that neither BFS nor DFS consider weights. Instead, they traverse all nodes in the graph hoping to find the desired node sooner or later.

DFS queue

DFS doesn't look very different. We only replace the STD queue with a stack. dfsStack.h#L11:

#include <stack>
#include "pathFindingBase.h"

class dfsStack : public pathFindingBase
{
private:
  stack<int> _queue;

public:
  virtual void insert(int node)
  {
    _queue.push(node);
  }

  virtual int getFirst()
  {
    int value = _queue.top();
    _queue.pop();
    return value;
  }

  virtual bool isEmpty()
  {
    return _queue.empty();
  }
};

DFS finds the path 24<-23<-22<-21<-20<-15<-10<-5<-0 with a cost of 15 (it doesn't prioritize finding the optimal cost). Interestingly, it traverses in the opposite direction compared to BFS:

(0, 0)
   | 
(1, 0) 
   |
(2, 0)
   |
(3, 0)
   | 
(4, 0) - (4, 1) - (4, 2) - (4, 3) - (4, 4)

Dijkstra queue

Now, Dijkstra's algorithm is the most well-known greedy search algorithm in a graph. Despite its known limitations (inability to handle negative paths, cycles, etc.), it remains popular and efficient enough.

It is important to note that the getFirst() method in this implementation uses a greedy approach to select nodes for traversal. dijkstraQueue.h#L17:

#include <queue>
#include "pathFindingBase.h"

class dijkstraQueue : public pathFindingBase
{
private:
  vector<int> _queue;
  shared_ptr<vector<int>> _shortestPaths;

public:
  dijkstraQueue(shared_ptr<vector<int>> shortestPaths) : _shortestPaths(shortestPaths) { }

  virtual void insert(int node)
  {
    _queue.push_back(node);
  }

  virtual int getFirst()
  {
    int minimum = INF;
    int minimumNode = -1;

    for (int i = 0; i < _queue.size(); i++)
    {
      int to = _queue[i];
      int newDistance = _shortestPaths->at(to);

      if (minimum > newDistance) // Greedy selection: select node with minimum distance on every step
      {
        minimum = newDistance;
        minimumNode = to;
      }
    }

    if (minimumNode != -1)
    {
      remove(_queue.begin(), _queue.end(), minimumNode);
    }

    return minimumNode;
  }

  virtual bool isEmpty()
  {
    return _queue.empty();
  }
};

Dijkstra's algorithm finds the SHORTEST and most OPTIMAL path 24<-19<-18<-13<-12<-7<-6<-1<-0 with a cost of 10:

(0, 0) -1- (0, 1)
             |
             1 
             |
           (1, 1) -1- (1, 2)
                         |
                         1 
                         |
                      (2, 2) -1- (2, 3)
                                    |
                                    1 
                                    |
                                  (3, 3) -1- (3, 4)
                                               |
                                               1 
                                               |
                                             (4, 4)

A-Star

The A-Star algorithm is particularly suited for cases where a path is sought in a Euclidean space with coordinates, such as maps. This is why it is widely used in games. It not only utilizes a "blind" greedy search based on minimal weights but also considers the Euclidean distance to the goal. As a result, it is usually much more efficient than Dijkstra's algorithm in practical scenarios (refer to my other GitHub project for more details). aStarQueue.h#L18:

class aStarQueue : public pathFindingBase
{
private:
  vector<int> _queue;
  shared_ptr<vector<int>> _shortestPaths;
  shared_ptr<Graph> _graph;
  int _finishX;
  int _finishY;

  /// <summary>
  /// Euclidian distance from node start to specified node id.
  /// </summary>
  int calcEuristic(int id)
  {
    return sqrt(
      pow(abs(
        _finishX > _graph->Nodes[id].X ?
        _finishX - _graph->Nodes[id].X :
        _graph->Nodes[id].X - _finishX), 2) +
      pow(abs(
        _finishY > _graph->Nodes[id].Y ?
        _finishY - _graph->Nodes[id].Y :
        _graph->Nodes[id].Y - _finishY), 2));
  }

public:
  aStarQueue(int finishX, int finishY, shared_ptr<Graph> graph, shared_ptr<vector<int>> shortestPaths)
    :
    _shortestPaths(shortestPaths),
    _graph(graph)
  {
    _finishX = finishX;
    _finishY = finishY;
  }

  virtual void insert(int node)
  {
    _queue.push_back(node);
  }

  virtual int getFirst()
  {
    int minimum = INF;
    int minimumNode = -1;

    for (int i = 0; i < _queue.size(); i++)
    {
      int to = _queue[i];
      int newDistance = _shortestPaths->at(to);
      int euristic = calcEuristic(to);

      if (minimum > newDistance + euristic)
      {
        minimum = newDistance + euristic;
        minimumNode = to;
      }
    }

    if (minimumNode != -1)
    {
      _queue.erase(remove(_queue.begin(), _queue.end(), minimumNode), _queue.end());
    }

    return minimumNode;
  }

  virtual bool isEmpty()
  {
    return _queue.empty();
  }
};

As a result, we obtain the same results as Dijkstra's algorithm because it provides the most optimal route.

It is possible that this example might be too simplistic to demonstrate the real differences in performance among these algorithms. If you are interested in exploring the potential of these algorithms, please refer to my other project, which implements these algorithms efficiently and employs a more visual approach with a wide range of test data.

Downsides

However, there is a problem with our Dijkstra's and A-Star algorithms...
The above implementation uses a vector (a dynamic array []) within our universal data structure. On every call to getFirst(), it takes O(N) time to find the required node in the vector. Consequently, assuming that the main algorithm also takes O(N*M) time, where M is the average number of neighbors, the overall complexity could become almost cubic. This would lead to significant performance degradation on large graphs.

While this sample is useful for grasping the overall idea that all four algorithms are not fundamentally different, the devil lies in the details. Implementing all four algorithms efficiently using a universal data structure is challenging.

For optimal performance (which is typically the primary concern in 99% of cases), more effort should be directed towards optimizations. For example, it makes a lot of sense to use priority queue instead of an array for both Dijkstra's and A-Star algorithms.

Speaking about optimizations of A-Star algorithm, it makes a lot of sense to mention a few links that will open a deep world of optimizations: A* Optimizations and Improvements by Lucho Suaya and JPS+: Over 100x Faster than A* by Steve Rabin.

Final word

The goal of this article was to show how relevant all traversing algorithms are to each other. But example of a graph used in this article is definitely too simplistic to demonstrate the real differences in performance among these algorithms. Therefore, use these examples primarily to gain a conceptual understanding, rather than for production purposes.

If you are interested in exploring the potential of these algorithms, please read my next article based on my other project, which implements these algorithms efficiently and employs a more visual approach with a wide range of test data.

Stay tuned!

Exploring well-known path finding algorithms with SFML graphics library

Anton Yarkov — Thu, 03 Aug 2023 18:23:10 +0000

In my last post I have shown a way to unify implementation of the most well-known graph-traversal algorithms. Now let's make it more visually appealing and look into the performance differences.

The story behind

A few years ago, Yandex organized a contest called Robots Couriers with an enticing prize: a ticket to a closed self-driving conference for professionals. The contest resembled a game, with participants tasked with finding optimal routes on a map and optimizing delivery using robotic couriers.

As I delved into the topic, I discovered that despite route finding being a solved problem, it continued to be of interest to the professional game development community. Between 2010 and 2020, engineers made significant optimizations to the A* algorithm, particularly beneficial for AAA games with massive maps. Reading articles and research papers on these optimizations was an exciting experience.

Furthermore, the contest requirements were designed to enable easy assessment of program outputs by the contest's testing system. As a result, there was little emphasis on visualization.

I found it intriguing to explore this field and develop a small application that uses well-known graph algorithms to find routes on a grid map. To visualize my findings, I employed the SFML graphics library.

Goal

This project builds upon one of my previous endeavors, where I demonstrated that four well-known path-finding algorithms (BFS, DFS, Dijkstra's, and A*) are not fundamentally different and can be implemented in a universal way. However, it was challenging to showcase significant performance differences among these algorithms in that project.

In this article, I aim to use improved test data and design something visually exciting. While the Yandex Contest task mentioned earlier aligns well with my goals, I will not solve their specific problem here since it heavily relies on their test system, which is currently unavailable.

Instead, I will extract general ideas for input parameters from that contest and create my own implementation.

Imaginary world

Imagine a technically advanced and innovative city where the future has arrived long ago. In this city, the majority of orders are delivered by courier robots, and it has become a rarity for a person to deliver an order from a cafe. In this task, we invite you to participate in finding optimal routes to deliver orders efficiently.

Let's envision the city as an N × N map. For simplicity, we assume that each robot occupies exactly one cell, and each cell can either be passable or not for the robots. In one step, a robot can move in any of the four cardinal directions (up, down, left, or right) if the target cell is free.

And I'm ignoring the rest of orginial task:
~~At the beginning of the test, you need to output the number of robots you want to use to deliver orders and their initial coordinates. The construction of each robot will cost Costc rubles.~~

Next, T iterations of the simulation will be performed. One iteration represents one virtual minute and consists of 60 seconds. At each iteration, your program will be given the number of new orders, and in response, the program should tell you what actions each robot performs (60 actions per robot).

For each successfully delivered order, you will receive max(0, MaxTips - DeliveryTime) dollars in tips, where MaxTips is the maximum number of tips for one order, and DeliveryTime is the time from the moment the order appeared to its delivery in seconds.

The total number of points that you earn in one test is calculated by the formula TotalTips - R × Costc, where TotalTips is the total number of tips earned, R is the number of robots used, Costc is the cost of building one robot. The Costc and MaxTips values are set in each test. If you earned less tips than you spent on making robots, your total points will be 0. You will also receive 0 points for the test if you perform any incorrect action.

Input

The program uses standard input to read the parameters. This approach allows us to specify test data of various complexities using input files.

The first line of input contains three natural numbers: N (the size of the city map), MaxTips (the maximum number of tips per order), and Costc (the cost of building one robot). I ignore both MaxTips and Costc parameters for my first implementation and maybe will consider that in future.

Following that, each of the next N lines contains N characters representing the city map. Each string can consist of two types of characters:

'#' - indicates a cell occupied by an obstacle.
'.' - indicates a free space.

Next, you will be provided with two natural numbers: T and D (T ≤ 100,000, D ≤ 10,000,000). T represents the number of interaction iterations, and D represents the total number of orders.

Output

Your task is to visualize the map and the optimal routes using the SFML graphics library.

Modelling the maps

I'm fun of maps represented as a grid of cells. Thus, I prefer to render all the results and map itself as a grid on cell by cell basis.

There is also option to execute path search right on grid without using any additional data structure (and I have implemented this as well for the learning purposes: see in code).

But because of a grid, it is easy to represent map as a graph using one way or other. I prefer to use adjacency list of cells for most of the algorithms like BFS, Dijkstra's and A-Star. For algorithms like Bellman-Ford it may make sense to use Edges List instead of Adjacency List. That's why if you explore the codebase then you will find all of it and they all are working examples.

To split the logic and responsibility I have a Navigator entity that is responsible for executing path finding according to the orders and tasks configuration that is specified via App Config file and related map files.

App Config looks like this:

{
    "font": "../../data/arial.ttf",
    "map": "../../data/maps/test_29_yandex_weighten_real_map",
    "shadow": false,
    "map_": "../../data/maps/test_08_low_res_simple_map",
    "map__": "../../data/maps/test_10",
    "map___": "../../data/maps/test_07_partially_blocked_map",
    ...

Note, that "map_", "map__", etc. are not really configuration properties. They are ignored during application run. Since there is no way to comment part of JSON file, I use underline in the property name so it can stay in config file, but not used.

Map file looks like this:

25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
###...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20

This is one of the simplest examples that contain either blocked or not blocked cells. I have prepared a lot of various examples of input parameters and test data. Starting from very small parts that let you to debug and learn the code, finishing by a huge piece of map (from the real existing city) that allow us to measure the performance of a Graph algorithm.

How do we draw maps

When map contains only cells with binary state (either blocked or non-blocked), this basically means that any edge of a graph either exists or not.

To find a path in the graph we have to represent it efficiently. Like in my previous post, I have used adjacency list with the relationship as Vector[NodeId]->points to->Vector[Neighbour Nodes]:

typedef std::vector<std::vector<std::shared_ptr<Cell>>> Graph;

Interestingly enough, when we exploring grids it's not really necessary to use graphs at all. We are capable to traverse grid using BFS/DFS algorithms cell by cell without thinking about edges. See method _GetPathByBFSOnGrid.

First, initialization code reads the file and converts it into the grid row by row and column by column:

bool RectangularMap::LoadMap(const std::string& filepath, bool shadow)
{
...
  // Fill the grid.
  _verticesNumber = 0;
  for (int row = 0; row < _height; row++)
  {
    ...
    for (int col = 0; col < _width; col++)
    {
      int x = col;
      int y = row;
      if (line[col] == BLOCK_CELL)
      {
        // Create a shared pointer here to safely pass pointers between the classes.
        _grid[row][col] = std::make_shared<Cell>(x, y, line[col], blockColor, shadow, _scaleFactor);
      }
      else
      {
        ...
      }
    }
  }

  // Make a graph
  InitialiseGraph();
...
}

Then, it creates an actual graph as an adjacency list:

void RectangularMap::InitialiseGraph()
{
  MapBase::InitialiseGraph();
  ...
  unordered_set<int> visited;

  for (int rr = 0; rr < _grid.size(); rr++)
  {
    for (int cc = 0; cc < _grid[rr].size(); cc++)
    {
      if (_grid[rr][cc]->GetId() > -1)
      {
        for (int i = 0; i < 4; i++)
        {
          int r = rr + dr[i];
          int c = cc + dc[i];

          if (r >= 0 && c >= 0 && r < _width && c < _height &&
              _grid[r][c]->GetId() > -1)
          {
            if (_isNegativeWeighten)
            {
              ...
            }
            else
            {
              _adjacencyList[_grid[rr][cc]->GetId()].push_back(_grid[r][c]);
            }
          }
        }
      }
    }
  }
}

Grid represenation is useful to draw on screen using SFML library. We can draw by creating a geometric objects (this is exactly what I do for small maps):

...
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
  for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
  {
    _grid[j][i]->Draw(_window, _scaleFactor);
  }
}
...
sf::RectangleShape tile;
tile.setSize(sf::Vector2f(_cellSize - 5, _cellSize - 5));
tile.setPosition(sf::Vector2f(_x * _cellSize, _y * _cellSize));
tile.setFillColor(_color);
window.draw(tile);

Or we can do it efficiently pixel by pixel for larger maps:

sf::Uint8* pixels = new sf::Uint8[_width * _height * 4];

for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
  for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
  {
    int index = (_grid[j][i]->GetY() * _width + _grid[j][i]->GetX());

    sf::Color color = _grid[j][i]->GetColor();
    pixels[index * 4] = color.r;
    pixels[index * 4 + 1] = color.g;
    pixels[index * 4 + 2] = color.b;
    pixels[index * 4 + 3] = color.a;
  }
}

sf::Texture texture;
texture.create(_width, _height);
texture.update(pixels);
sf::Sprite sprite;
sprite.setTexture(texture);
sprite.setScale(cellSize, cellSize);
_window.draw(sprite);

Finally, let's see how a map defined by file test_25_xmax would look like.

Originally, file defines this:

..............C.................
..............#.................
.............###................
............#####...............
...........#######..............
..........##1###2##.............
.........###########............
........##3######4###...........
.......###############..........
......#################.........
.....###################........
....#####################.......
.............###................
.............###................
.............###................

And a map renderred with SFML looks like this:

Because I wanted all of that to be controlled by user with keyboard, I left all the user-behavior logic in the main.cpp. I like to call it “Controller” logic.

SFML library makes it very easy to handle keyboard events:

while (window.isOpen())
{
  Event event;
  while (window.pollEvent(event))
  {
    if (event.type == Event::Closed)
      window.close();

    if (event.type == Event::KeyPressed && event.key.code == Keyboard::Space)
    {
      ... Do what you need here
    }
  }
}

The main idea is user triggers (press of a SPACE button) reading the map file and renderring the map, and then by a second trigger (second press of a SPACE button) to load routing task and calculate the shortest path between two points on map:

...
if (navigator->IsReady())
{
  navigator->Navigate(); // Finding route between two points
}
else
{
  if (map->IsReady()) // Second SPACE press runs the routing
  {
    skipReRendering = true;
    if (navigator->LoadTasks(filepath))
    {
      navigator->SetMap(map);
    }
  }
  else // Load and draw map
  {
    drawLoading(window, font);
    if (!map->LoadMap(filepath, shadowed))
    {
      return 0;
    }
    drawProcessing(window, font);
  }
}
...

We need to go deeper

I wanted to play with more Graph algorithms, and they all have their limitations, so I decided to implement also a multi-color maps that can be represented by multi-weighted graphs.

Every cell is colored and the color means that edge not only exists, but also applies some weight (or fee, or fine, you name it). So, edge might be blocked, half blocked, not blocked, ... you got the idea.

Thus, I have implemented multi-color maps that look more joyful and look like a game-ready (example from file test_31_multi_weight_graph_map):

Some of the configuration files contain more complex maps from really existing cities, like test_29_yandex_weighten_real_map:

As a challenge, now we should handle maps with very flexible configuration. RectangularMap.cpp essentially contains a lot of logic inside, including all the graph algorithms and even more than needed (because I like to play with things, even if it's not particularly useful for now).

I have implemented BFS#Line 598, Dijkstra#Line 299, A-Star#Line 356, Bellman-Ford#Line 428 algorithms and a number of additional "utility" algorithms like Topological Sort, Single Source Path, that are not useful for the current application state (because they work on Directly Acyclic Graphs, which are not type of Graphs I currently use), but I have some ideas to use it in future improvements.

I didn't polish all the code and didn't get it ideal enough, but it allows me (and, I hope, will allow you) to play with the code and compare performance metrics.

Sorry about some commented lines there and there, maybe some dirty code...it's all way of learning :). To grasp an idea what's inside, I recommend you to review the RectangularMap.h.

There is also some fun features like a Focus feature that allows to render only particular part of a map. It changes focus by re-rendering the necessary part using Observer pattern when user presses the PgDown or PgUp buttons. It is pretty easy to improve this feature and implement "Zoom" functionality. Take it as a home work, if you like it.

Focus feature with map file test_29_yandex_weighten_real_map in work:

Classes diagram looks like this:

Run and play

I believe, the most joyful part is just running this little application, playing with variations of its configuration and algorithms. You can do a lot of experiments by using various map files as input parameters with different test data as well as change the logic in the code.

After start you need to press SPACE an application will render map according to the configuration file and it makes a lot of sense to start exploring from simplest test cases moving forward to the most complex one.

Pressing SPACE one more time executes the routing algorithms and finds path between the start and one nearest order. BTW It's not yet done, but it is easy to implement reading all the rest of orders available in map configuration files and execute path finding to all of them.

Here is route found on map defined by file test_18_yandex_super_high_res:

It also capable to find routes in the maps that are simulating existing cities, like test_29_yandex_weighten_real_map:

Finding efficient paths between two coordinates becomes challenging for algorithms like BFS, but can be easily done by A-star.

Based on the cells found in the map configuration files, application will treat map as a weighted or non-weighted graph and will select the right algorithm for it (and you can easily change this as well). It's easy to see the difference between BFS and A-Star performance:

Final words

With this I want to leave you alone and let you play with these code examples. I hope you will find it fascinating and will learn a lot from it.

Stay tuned!

Tip: Debug your Roslyn Source Generator with JetBrains Rider IDE

Anton Yarkov — Sun, 05 Feb 2023 20:05:06 +0000

.NET Compiler Platform becomes bigger thing, and in the same time, toolset is growing around it. So, it becomes easier to be used.

While writing code that parses/analyzes your code is not a simple task, it might be helpful in various ways. One way I just learned (thanks to my colleagues) is a refactoring.

Usually, code of your source analyzer and/or generator will not be the easiest one to read and maintain. But the idea is it doesn't always need to! The idea is that you have to use source generator as a temporary solution that makes refactoring an easier task for you and your team. And after some refactoring is done, you can simply throw away that code as a legacy one.

I think there is a lot of examples on youtube and in the internet, so I don't need to share another "sample". Instead, I will share most recent practical

Tip of the day

To debug C# Source Generator based on Roslyn .NET Compiler Platform in Rider IDE you need to install Rider 2023 EAP (yes, early preview) and then follow instructions from https://github.com/JoanComasFdz/dotnet-how-to-debug-source-generator-vs2022

If you haven't use Rider IDE for some reason, you should try it. It much more efficient than Visual Studio, especially at big monolithic projects (you know what I mean, if you work at enterprise). Though, debugging source generators was not possible till recently. From know it all yours!

API versioning notes

Anton Yarkov — Sun, 27 Nov 2022 20:59:03 +0000

I have finished watching a series of lessons on Designing & Versioning HTTP/REST APIs from well known author Jeffrey Richter who is an author of the best-sellers CLR via C# and Windows API via C++.

I do definitely recommend it to watch (and read the books as well, if you didn't) for those who design Back-End APIs. And especially for those who think that doing API is simple (probably, impressed by several Hello-World prototypes made during the week-ends).

One important thing to note in this article is that it is really important to combine some practice when you do theoretical learning.

This recommendation will work for developers of any level of experience and do not depend on how well-known the author of the book/course is. It is always easy to watch and read something and put a sign "learned" on it. But actual implementation will always put some impediments and this is where things get really interesting.

Now, let's take one piece of advice from the course and let's dive into the topic which is not fully uncovered in the course: on Versioning HTTP APIs part of course. Details I will cover here are really important for the implementation.

REST API everywhere

Most of the public API's go with REST or RESTful approach. Those gRPC, SOAP, GraphQL and other protocols are good for its own purposes, but REST is covering most of the needs:

It's available for any type of client: old/new browsers, smartphones, low-end computers, Raspberri Pi's and even consoles.
It uses well-known HTTP language for all the features that API needs, like handling errors, passing auth tokens (headers), transferring all the types of content, bandwidth-control, etc. etc.
Tons of examples in the internet out there,
etc.

And, truly saying, for prototypes, local businesses, quick and cheap development it is all you need. All other protocols have been created to solve much more specific needs like scaling, handling low-bandwidth channels, enterprise solutions, etc.

But this simplicity and low entry threshold plays a bad role when it comes to product quality of your Public API. Very few non-senior developers know that Public API's must be backward compatible and sometimes even forward compatible. Tiny portion of developers know how to achieve it.

What's wrong with Public APIs?

API versioning plays crucial role in making your API really desirable for your happy clients. Since the time you have published your API for the first time, things never will be fun for you.

You have to maintain all the base of the clients from version 1.0-pre-alpha till the version 99999...9.0 unless you have been smart enough to publish your Public API Policy of Use. Didn't you? :D

In this policy you can recommend all your clients to update on every release. But it's still just a recommendation.

You can also not guarantee stability of your old versions, but that really depends on your customer relationships.

In any way, you have to label your API version and make sure that clients potentially understand how it works based on documentation and policies that you have provided.

Just follow someone's recommendations in API versioning. What can go wrong?

API version is a label that should tell your clients what to expect. There are various ways of doing so, to mention a few:

As you can see, there are many ways to tell your API version to the client. And before you take the first approach in the list, I should tell you that it's not always "up to you". Let's review why you may want to use one or another way.

Basically, there is only 2 approaches that differ a lot:

Put your API version in the URL
Put your API version in the parameters

In various sources I've seen approach #1 marked as outdated. However, there are still reasons to keep using it. Let's review those.

Why to pass Version in the URL

Most of the API Management systems do use "API version in the URI" as a default approach, such as Axway, MuleSoft Anypoint, Google Apigee, Boomi, AWS API portal, Nginx API Management.
Services co-located behind a DNS endpoint MUST use the same versioning mechanism, so if you already have something (maybe legacy) versioned this way, you better stick with it.

Why to pass Version as a parameter:

We can guarantee the stability of their REST API's URL paths, even through future versions of the API.
You can always return a DEFAULT resource without a version even specified. etc.
Easily change from -preview or -beta to the released and thus, make your development a bit more agile and iterative.
Gives MORE transparency to the clients -> more information on the date of release
Split out API BEHAVIOUR from RESOURCE.
Support Group versioning feature that allows developers to look up a single version number and use it across multiple endpoints. Group version numbers are well known, and services SHOULD reject any unrecognized values.

Phew. Quite a few notes, ha?

Fun thing is that nothing of that is actually mentioned in the course. That's why I wanted to bring this example of the need for questions, which appear right after you start practicing.

More to consider for Public API

Approach to API Versioning should not be afterthought. Each time you want to change a mandatory parameter, or payload formats, replace some old error codes or change a behavior...consider adding new API methods and publishing new versions.

It would be even better if you embed version numbers in the data structure. You may not need that in the beginning, but you will thank yourself when you want to scale (event-driven architecture, etc.).

Conclusion

Following those rules will make your Public API clients happier and your life a bit easier (but a lot, still).

As you may notice, in general, there are many "up to you's" in the API versioning, starting from policies and right to the technical details. But that is not usually part of any book or a course and this is something you have to solve on your own.

Next time, before finishing your training course, take your time to practice a little bit. I'm sure you will find many places to raise a hand and discuss with your experienced colleagues or a community.

Resources

Microsoft API guidelines
ASP.NET versioning examples

GraphQL trade offs

Anton Yarkov — Sat, 12 Nov 2022 19:17:34 +0000

It's very easy to fall in love with technology sold by professional marketers. However, software engineering is hard because there are no one solution to fit every case.

GraphQL is under the focus for a couple of years already. Before you add this nice-looking abbreviation to your resume, I would like to share summarized points and thoughts on it based on production experience. There is a fresh good material from famous Alex Xu I would like you to watch first, so I don't need to get into details here and do not repeat here.

While I fully support concerns mentioned in the video, there are a few things I would like to add:

GraphQL is not going to replace REST or SOAP.

It's just one more way to build an API in a bit different but definitely not "the best one because the new one". I would even say it's more like a SOAP way for even more specific business-cases. Below I will give more details on that point by showing parallels in between.

GraphQL is created to solve a few specific problems

It is covering the cases where:

You're doing business where most of the users are running from "smartphones". Such users are frequently switching networks/ISPs while they go and may work with unreliable or poor connection. Basically, GraphQL allows you to execute less number of requests from the mobile application to the API. However, the devil is in the details.
You can easily fit all the data (that you need to use on the client/UI) into a single data model (or data graph). It might be because you work in the Big Data, or there are uniform way of represent the information from various sources.
GraphQL allows you to optimize your development team throughput by letting your Front-End team think on what they want to get from the API, instead of your back-end team propose their data-model or guess on what is the most optimal API and data model. It's not very efficient to wait for API change (by Back-End engineers) every time you need to change the UI side. Thus, UI developers are happy because they can play with data and find various ways to use it or show it. However, are they knowledgeable enough to do this safely? This benefit comes with a cost.

GraphQL brings trade offs

It requires you to be ready for a few things, though:

You have to generate the schema of the API, just like in case of SOAP. That's nothing new and may look normal when you are alone responsible for both Back-End and Front-End (building a Hello World). And it's OK while your team fits in one room (or shares 2 pizza :) ) and can easily speak to each other very quickly. However, if your team is large and/or updates API objects frequently, you can quickly get tired of this process. Every time back-end engineers update API and regenerate schema, they have to connect with some peers that need to pick-up their updates. They have to spend more effort on building and maintaining additional CI automation steps, as well as communicate better and more frequently using chats, messengers, etc. Clearly, your development process becomes more tightly coupled and fragile. It doesn't enable so much flexibility in experimentation as REST.
It takes control of your API performance out of the hands of your back-end development team and into the clients hands (UI/Client development team). Using its strong typing GraphQL enables so-called Client‐specified queries. In worse cases it leads to N+1 problem. Flexibility that GraphQL provides to the Client team comes with the possibility to make unpredictably slow database queries. Of course this can be mitigated by manual or automated testing, but worth keeping in mind. And definitely it might not be acceptable for some cases.

On GraphQL schema-stitching

To resolve a problem of coupling there is an idea of schema-stitching. In simple words, you can take two or more GraphQL schemas, and merge them altogether for the client's use, while generating them separately. Schema Federation is a way to go.

The problem, though, is that even this idea was far from a perfect solution. That's why companies building complicated tooling around GraphQL and, specifically, Apollo recently (as of summer 2022) introduced Feration v2.0 and an idea of supergraph.

To my opinion, this all a sign of problems at the core of the protocol. It adds unnecessary cognitive load and architecture complexity to the world of software sandcastles, which become even more fragile.

The End

Clearly, GraphQL narrows down the number of use cases it solves and is not a silver bullet. You have to evaluate trade-offs mentioned in the video and listed above before you get amazed on the benefits it provides.

References

GraphQL Specification
GraphQL over HTTP
Introducing GraphQLinq strongly typed GraphQL queries with LINQ to GraphQL
GraphQL API with .NET 5 and Hot Chocolate
Short GraphQL example in Node.js and Express JS framework
Introduction to GraphQL
Creating a GraphQL back-end with .NET GraphQL library
Getting started with GraphQL and HotChocolate
GraphQL schema design from the creator of HotChocolate GraphQL library
GraphQL and ASP NET Core - .NET Oxford - November 2019
Building Modern APIs with GraphQL
Getting started with GraphQL and HotChocolate
GraphQL Part 2 - Setting up project
Beyond REST with GraphQL in .Net core - Irina Scurtu
GraphQL Server with .NET Core Tutorial
GraphQL Schema Design
GraphQL for dotnet developers
Владимир Цукур — GraphQL — API по-новому
GraphQL #0 Введение
Статьи и презентации про GraphQL
Redux не нужен. GraphQL и Apollo Client
Разработка GraphQL API на ASP.NET Core // Бесплатный урок OTUS
Apollo GraphQL with React. Полный курс
Why Swagger is dead

Writing self-documented code with low cognitive complexity

Anton Yarkov — Sun, 11 Jul 2021 15:06:44 +0000

In this article, I will share practical and straightforward advice on how to stop (holy wars) arguing about code quality and find measurable arguments about the necessity of refactoring, simplification, adding comments or documentation for the code. While I’m going to refer to exact commercial tools in the second half of the article, I should say that I’m not affiliated anyhow with the tool's authors. The tools are available via free community licenses as well as commercial licenses.

The goal of this article is not the tool itself but to tell you about useful metrics that will allow your team to write self-documented code, produce better software and improve the programmers life.

Self-documented code

I frequently get the answer "Go read the code" when I ask developers to provide documentation or explain their code. I'm sure I'm not alone. Many developers feel their code self-documented by default. Not many people understand that creating self-documented code is a complicated design task.

Why is that? Let's take a look into the way we read code:

First, we are trying to figure out the aim of this code: WHAT was the task and the goal (and real experts also try to dig into WHY).
Next, knowing WHAT, we are reading the code to understand HOW the author achieves this.

While it's possible to do vice versa, it's tough to do in any production solution. Production code tends to be complex due to additional requirements to integrate with other system components like monitoring, logging, or security; to be resilient, scalable, configurable; to support multiple platforms, versions, etc.

Some people claim that SQL and HTML answer both HOW and WHAT at the same time. I will let myself disregard this comment here and concentrate on general-purpose languages.

Doing vice-versa-analysis, software engineers should figure out what the purpose of this code is, WHAT it mainly does, and (finally) WHAT it missing. That is usually called Mental Model. Whenever how simple or complex it is, there is always some Mental Model underlying the code (even the bad one). It might be a domain model or any other way to express the thinking process. There are many concrete rules to follow to make your code more clean, readable, and understandable. As we know, there are many books has been written on this topic. But if to sum up all of this, there is only one way to write self-documented code: the developer should write the code to uncover the Mental Model and express important model parts while hiding unnecessary implementation details. Very frequently, developers focus on implementation details like frameworks, databases, protocols, and languages, and it makes the task of understanding the model very hard.

Questions HOW and WHAT are orthogonal because there are several ways to achieve the same goal. Imagine climbers analyze the better way to reach the mountain peak by different paths. They consider many various aspects, summing their own experience and common knowledge about the mountain relief, weather and air conditions, time of the year, the level of readiness of the group, etc. Finally, they select the optimal path to climb. Optimal path doesn't explain all of these aspects but allows the group to put the flag on the peak.

As I see it, the Mental model shows the explicit dependency of the self-documented code from the author's design skills that allow him to make code more readable.

Mental model answers to a question the WHAT, while code is telling the HOW.

As I see it, the Mental model shows the explicit dependency of the self-documented code from the author's design skills that allow him to make code more readable.

Measuring readability of the code

Frederick Brooks, in his famous paper No Silver Bullet – Essence and Accident in Software Engineering specified two types of Complexity:

Essential complexity – is caused by the problem to be solved, and nothing can remove it
Accidental complexity – relates to the problems which engineers create and can fix.

Many years have passed, but we still cannot measure it precisely. The well-known metric Cyclomatic Complexity (invented in 1976) tightly relates to the lines of code. While it's an excellent way to measure code coverage, it is not a way to measure ComplexityComplexity. Here is the problem showcase:

As you can see, Cyclomatic Complexity shows the same digits for the code from left and right. However, from the developer's viewpoint, left and right pieces of code are not identically complex. The left one is harder to read and to understand. We may believe the code is finding Sum of Prime Numbers which is a famously known problem. But an experienced developer will never think it solves the task until he verifies that it's true:

Is the name of a method clearly states what the code is doing?
Is code achieving the mission?
Is code missing some use cases, and what are they? (i.e., what are the limitations of the code?)
Etc.

Now, imagine how hard it is to understand something more specific to the domains not very famous to others. Sonar Source released the Cognitive Complexity metric in 2017, and not many people know about it. However, I believe this is groundbreaking work that has to be widely adopted. As we can see, it works perfectly for the described example:

You can find all the details in their paper, and on youtube. But telling short, the metric is based on three rules:

Ignore structures that allow multiple statements to be readably shorthanded into one.
Increment (add one) for each break in the linear flow of the code
- Loop structures: for, while, do while, ...
- Conditionals, ternary operations, if, #if, #ifdef
Increment when flow-breaking structures are nested

You can find this metric using the static code analysis tools produced by Sonar Source (SonarQube, SonarCloud, and its freely available SonarLint IDE extension). SonarQube is available in free community edition.

In Sonar Cloud look into Project -> Issues -> Rules -> Cognitive Complexity

It is easy to find the full report with the line-by-line explanation of the penalty assignment:

The default thresholds for code quality are:

Cognitive Complexity
15 (most of the languages)
25 (C-family languages)
Cyclomatic Complexity = 10 (all languages)

It's essential to know both Cyclomatic and Cognitive Complexity thresholds since one metric might be larger than the other and vice versa. Let’s take a look into a simple production example (here is how to find it: Sonar Cloud -> Measures -> select Complexity filter):

You can find the total complexity measurement for the group of files (folder) on the left side, and here we can see twice times difference: 134 against 64. You can see file-by-file differences as well. LoggerHelper file isn't so bad in Cyclomatic Complexity, but there are ways to improve its Cognitive Complexity. And for other files, we may see a controversial picture: Cyclomatic Complexity is bigger than Cognitive one.

Outcomes

It looks like we have a way to measure code complexity, and I wish more tools to implement this, but we already can start using this quickly and straightforwardly. The Cognitive Complexity metric still doesn't tell us how good code is expressing the mental model, but it is already excellent data for you to start moving towards good software. Using these metrics, you can start building a transparent dialogue between development and business on necessary resources and roadmaps for better code and product quality:

Measure cognitive Complexity Complexity in all parts of your codebase to assess how hard it is to introduce new developers, implement and deliver new changes, etc.
Use measurable goals for planning your development cycles and any activities for improving your code, like refactorings.
Prioritize improvements for the most critical parts of your codebase.
See the places that should cover with additional documentation.
Stop arguing and holy waring, conflicting, and stressing with colleagues on code quality.
Make the life of your colleagues more fruitful (everyone wants to achieve results on their task as quickly as possible and then meet with friends and family).

I hope I shared some exciting food for you to start digging into this and use Cognitive Complexity in everyday programmer's life.

A pragmatic guide to starting Communities of Practice in the organization

Anton Yarkov — Tue, 18 May 2021 17:25:54 +0000

Graphics made by Max Degtyarev (https://www.behance.net/maxdwork)

What is a community of practice?

A community of practice (CoP) is a group of people who share a concern or a passion for something they do and learn how to do it better as they interact regularly. Unlike a regular team, which is held together by a shared task, a community of practice is held together by the “learning value” members find in their interactions, and usually contains members of multiple existing teams.

As an example, Automation Quality Assurance engineers spread across multiple scrum teams should define their community of practice to regularly interact with each other with a goal of maintaining and improving automation best practices across teams in your organization. As counter-examples, a scrum team itself, the whole Agile Release Train, or the whole department are not communities of practice.

Three key pillars of a community of practice:

Domain is the shared domain of interest. It is a concern, a set of problems, or a passion about a topic. Members of communities of practice are all committed to their designated domain to improve their craft, collaborate with other employees, and strategize in solving relevant hurdles within a company.

Community is where members interact and learn from each other about how they can improve their work and tackle discoveries in their chosen domains. Members engage in joint activities and discussions, help each other, and share information.

Practice is where the members share knowledge, discover methods, learn cases, and exchange tools that can help the members solve common problems. This is a shared repertoire of resources: experience, stories, tools, ways of addressing recurring problems, etc.

Communities of practice can be organized around any one of three aspects of work:

Role
Business problem
Process

Why to use communities of practice?

Communities of practice (CoPs) connect people with common goals and interests for the purpose of sharing resources, strategies, innovations, and support. CoPs support the transmission and expansion of knowledge and expertise for leaders, learners, and professionals in any field or discipline. CoPs contribute to a more connected and collaborative global community in your field of expertise.

Members of the community can brainstorm new tools and processes, and try or explore new ways of communication/organization/development that still incorporates the company’s objectives. Communities of practice are not only limited to solving problems and meeting the company’s objectives. CoPs can also help you:

Reuse assets that can lower expenses,
Discuss and disseminate developments in the field, and
Identify and resolve gaps within the company.

Three characteristics or qualities define a practice:

Joint Enterprise: The members of a CoP are there to accomplish something on an ongoing basis. They have some kind of work in common and they clearly see the larger purpose of that work. They have a mission.
Mutual Engagement: The members of a CoP interact with one another not just in the course of doing their work but to clarify that work, to define how it is done, and even to change how it is done.
Shared Repertoire: The members of a CoP not only have work in common, but also methods, tools, techniques, and even language, stories, and behavior patterns unique to their domain.

Two indicators stand out from all the rest:

People have a strong sense of identity tied to the community (e.g., as technicians, salespeople, researchers and so on).
The practice itself is not fully captured in formal procedures. People learn how to do what they do and come to be seen as competent (or not) by doing it in concert with others.

Thus, the main responsibility of communities of practice is to build a community of highly engaged and collaborative colleagues to effectively grow, train, and coach each other in the domain or field, find ways to solve identical problems, and unify approaches, tools, and methods used across the organization.

Key concepts for successul implementation of CoPs

Facilitator’s role is essential

Our practical experience shows that most thriving CoPs have several attributes in common:

Someone becomes a Facilitator and dedicates some time to organizing meetings and notes, engaging in conversations, driving learning and brainstorming activities, and keeping up communication inside and outside the group.
Each community of practice decides whether they are private or public, allowing anyone to join as a listener or contributor at any time. Still, all CoPs maintain transparent and regular external communication with executive leadership (CTO, VP, CEO, etc.) and/or engineering management (Engineering Managers, Scrum Masters, Architects) about the results (even partial) of the work they have done, lessons they learnt, problems they solved. This communication might be informal (chat, email, a voice call, etc.), and it’s up to members to decide who is responsible for it. But if no one is assigned, it’s the Facilitator’s responsibility.
When only one person takes on the Facilitator role, it usually takes up to 20% of that person’s time to fulfill all the needs of the CoP.

The Facilitator’s role is essential for CoPs to be productive, as it helps to maintain healthy communication, synchronize across teams, drive engagement and motivation, and ultimately helps get important things done. It is also beneficial for person acting as a Facilitator. The work can help grow or pivot your career by gaining leadership experience, improving soft skills, and learning more about the company, teams, people, tools, and other accompanying staff.

Facilitating patterns to use

You should provide the infrastructure needed by the community to meet their objectives and be productive. This infrastructure may be information, supplies, or allotted time for discussion/interaction and so forth. A web page with links to relevant resources might be useful, but the real action in a CoP is in the interactions among members. Start small and evolve.
Keeping things simple and informal, since all members of a community of practice have their professional obligations to the company and providing them minimal responsibilities is highly recommended. Do not force them to overwork; let their creativity and ideas flow naturally. Give them the privilege of expressing their thoughts. Requiring CoP members to attend several meeting in just one day makes them feel exhausted and unproductive. Levying demands and imposing strong expectations can quickly convert a CoP into a project team focused on tasks and deliverables. The team will drive toward satisfying the boss — instead of producing and sharing new knowledge.
The success of a CoP hinges on trust between and among its members.
Do stay focused on the primary purposes of a CoP: to learn from each other through sharing and collaborating.
Appreciating and identifying the efforts of the members of the communities of practice will motivate them. Remember the reason you gathered them into a CoP in the first place. A simple gift certificate from a related event in their domain or allowing them to have at least one free day to discuss and execute their ideas makes them feel more valued in the company.

Best practices for organizing communities of practice

Use a “light hand”. Mandates to “launch” CoPs may create resistance to what could be viewed as the next corporate program to wait out.
Send a continuing message reinforcing the business value of CoPs.
Provide information to others about what CoPs are, how they operate, how to support and encourage them — and how to avoid undercutting them.
Encourage appropriate professionals to form CoPs that focus on key business issues at the unit, sector, process, function, or company level.
Seek out and subtly promote a few exemplar CoPs. Point to solid results and value added — but don’t overdo it.
Spend time with a few existing CoPs to learn first-hand how they operate.
Leverage outside events (e.g., bring attendees together afterward and de-brief the sessions attended).

Work items

It’s not a surprise that members of a CoP may generate some amount of work to do. But members of a CoP usually have their daily jobs in the Scrum teams. And it might be hard to prioritize one another. It’s helpful to go through the following steps to execute an additional amount of work desired by members of a CoP:

Decide whether some members should do this work as part of their main daily job in the Scrum team, or as an additional activity outside the group.
All the work finished as part of the team’s backlogs should be demoed in the usual cadence (i.e., at the end of iteration) and should not be treated as something different. It should also be welcoming to demo anything CoP did as an additional activity inside a CoP.

Work inside vs. outside the CoP

The rule of thumb is to decide based on work estimate: if this work item is Epic-sized, then it is a candidate for the Scrum team backlog. Otherwise (Story-sized), it can be an additional activity.

Usually, Epic-sized work items should be transparently discussed with Scrum team members (including QA, PO, SM, and devs). A member of CoP should convince team to take the item into a team backlog, plan, execute and deliver this work.

Story-sized work items can be completed relatively quickly and should not require the allocation of many resources or affect any Scrum team commitments. Thus, this work might be considered lightweight.

The ways to demo the work done by the CoP

How to demo results of CoP’s work:

Present results during a regular demo ceremony
Write and publish brief articles or results descriptions in company or unit communication vehicles
Create special communications: your CoP might periodically produce and distribute its own newsletter or blog
Invite others to special briefings where your CoP members share their learning and results
Publish articles in external journals or magazines and then distribute them internally (after clearing through proper company channels)

Why exert the effort to market your CoP’s results?

Several reasons:

To generate enthusiasm among current members
To ensure continued resources and support from your sponsor(s)
To stimulate interest in joining from high-potential prospective members
To promote interest on the part of your colleagues in finding out what the members of your CoP have learned and, as a result, to share what they have learned with your CoP
To better leverage the knowledge created and the learnings generated by your CoP

Lifecycle

Last but not least, to understand is that like any other group of people, a community of practice has phases or lifecycle stages. First, we define a new CoP. Then we have to find the best way to collaborate (including communication, learning, and working together) and run it. Later, at some point, the group may feel the need to transform to another kind of CoP or to shut down forever. Those phases are meant to be flexible, so any phase can be skipped or repeated based on your community of practice’s needs.

Figure 1. CoP lifecycle phases

Usually, groups of people need some time to pass each stage, whether fast or slow. It’s not expected that every community of practice will immediately move quickly. The four-stage Bruce Tuckman model of team development — Forming, Storming, Norming, and Performing — can be applied to CoPs. It’s normal that things change going forward and a shutdown decision may be made by the CoP members themselves. It might be helpful to consider transforming instead of shutting down, to ensure that your CoP is adaptive to changes in funding or goals.

Figure 2. Bruce Tuckman’s model of team development

Checklists

I want to start a new community of practice. What should I do?

☑ Start by creating a Community of Practice wiki-like page in the organization web portal. The page should cover following attributes:

☐ The facilitator is identified (i.e. who drives creation, leads this CoP, facilitates necessary changes)
☐ The sponsor is identified (i.e. who can approve creation of this CoP based on proposal)
☐ Aspect of work selected (a role, business problem, or process to focus on)
☐ Roles identified
☐ Value/benefits
☐ Sponsorship/support (where resources or support will be needed)
☐ Interactions
☐ Outcomes
☐ List members

☐ Proposal presented to the sponsor and approvals are received
☐ First meetings scheduled

☐ Initial agreements with members received
☐ Agenda is set for the initial interaction

☐ Issues/interests listed
☐ Problems listed
☐ Goals/outcomes listed

☐ Interaction modes selected and agreed

☐ Email distribution groups
☐ 1-1 meetings
☐ Scheduled/unscheduled
☐ Conference calls/group meetings
☐ Videoconferencing

☐ Run the following reccurring practices / events using Best Practices covered above

☐ Meetings
☐ Processes
☐ Interactions

☐ Success is measured periodically and adjusted

How can I measure the success of my community of practice?

CoPs don’t just happen; it takes hard work to form and sustain them. Regardless of your role – Sponsor, Champion, Facilitator, Practice Leader, Information Integrator, or Member – all members of your CoP should take some responsibility for marketing and promoting their CoP. Each member individually, and your CoP collectively, will want to market the value of your CoP. This means generating interest in your CoP and demonstrating its value. Both members and non-members need to know the value of their CoP: what real benefits accrue to the members and the company from the investment of time, energy, and resources in the CoP?

Check if your CoP is successful with this checklist of indicators below. Complete alignment with the checklist is not expected, but the more more boxes you check, the closer to ideal your CoP is:

☑ Members of the CoP share a fairly broad consensus about who is "in" and who is "out"

☐ A shared, evolving language (e.g., special terms, jargon, "shortcuts" such as acronyms, etc.)
☐ Perspectives reflected in language that suggest a common way of viewing the world (e.g., shared analogies, examples, explanations, etc.)
☐ Shared ways of doing things together (i.e., common practices and beliefs about best practices)
☐ A widespread and shared awareness of each others’ competencies, strengths, shortcomings and contributions

☐ Members of the CoP share experiences and know-how

☐ Continuing mutual relationships – regular, work-related interactions
☐ Common tools, methods, techniques and artifacts such as forms, job aids, etc.
☐ Capture/codify new know-how

☐ Members of the CoP experiment with new ideas and novel approaches

☐ A rapid flow of information between and among members
☐ Quick diffusion of innovation among members (e.g., rapid transfer of best practices)

☐ Members of the CoP discuss common issues and interests, collaborate in solving problems

☐ Conversations come quickly to the point (i.e., no lengthy lead-ins)
☐ Problems are quickly framed (i.e., a common understanding the milieu in which they all operate)
☐ Group analyze causes and contributing factors

☐ Members of the CoP evaluate actions and effects

☐ Learning
☐ Resolving issues
☐ Solving business problems

Where to learn more

Working example of SAML Single Sign-On integration using C#

Anton Yarkov — Tue, 16 Feb 2021 21:32:22 +0000

What is Single Sign-On at all?

Suppose you have a web application that people are using to do one thing X, but you are doing it great. For example, it would be a web store allowing to order a custom T-shirt printing by uploading some funny and pretty images found in the internet.

You are looking for ways to extend its functionality by adding some more capabilities for your users, but you don't want to lose the focus on this thing that you are doing best of all.

One way would be to integrate your web application with other services, such as a cool image provider, a trends meter, a delivery service, etc. It would allow your users to seamlessly move between different services (for example: looking for a cool image, checking trends, and uploading this image to your custom printing service) and do multiple things using only your web application.

Single Sign-On simplifies authentication flow and allows your users to sign in only once (on your web application) with their login/password (or even more innovative mechanisms, like FIDO2, if you use such) and use more integrated services by simple clicks without the need to log in again and again. It allows you to extend the functionality of your product by adding more value with relatively low investments.

SAML

SAML is one of the standard ways of doing Single Sign-On. For a long time, extensive enterprise services use this mechanism as one of the most secure and proven methods to exchange sensitive authentication and authorization information, like logins, passwords, emails, user accounts, etc. But it's not that complicated to add this solution between smaller businesses and enable cool integrations.

SAML is one of the most secure way to integrate with third-party among many other options. It allows parties to use asymmetric encryption (RSA) based on secure X.509 certificates. As of 2021, the standard is in version 2.

I should note that it might be better for you to trust one of many existing boxed solutions with a proven history and from vendors responsible for their code and overall solution. However, as a developer, I know that businesses may need much more flexibility and customization in their products, so I want to provide more details and working example using C#, so you can easily reuse this with your ASP.NET application.

SAML Workflow

Usually, the "classic" SAML workflow includes 3 parties:

Service Provider - this is a third-party service you want to integrate with
Identity Provider - this is some (enterprise) trused authentication service, that is able to proof the user identify and tell the Service Provider that "he is OK!".
User Agent - a browser with your Web Store opened by a user

This "classic" scenario is suitable for the enterprise, and we are not going to stop for long here. You can see the workflow diagram below and it is explained in all details on Wikipedia.

However, we are a small business, right? So, usually, we don't have complicated agreements with Enterprise-level Identity Providers, but we still need to integrate with third-party. Let's see how it should look like for us.

First step of the integration

The first thing is an agreement with some service provider to have an integration with your service. This time we focus on SAML protocol specifically, but I know about tenish more custom integration algorithms used by many small and medium-sized services. They use custom HTTP API, REST, WCF, XML, and JSON-based data formats, JWTokens and OAuth, and sometimes even combine all things. Whatever option is used, they need to provide you with some configuration parameters to establish an initial test connection.

For SAML-based integrations, they will ask you to provide so-called "metadata information." That's a small XML file that contains information about your service. This file is being used by service providers representatives to automatically create a certification (aka test) endpoint that would allow you to test the connection, resolve all the roadblocks and certify everything before you go public.

The critical part here is the XML content of this file that must be signed with your private X.509 certificate (aka private key, in terms of RSA). Of course, you have to buy one. Some providers allow using self-signed credentials for testing purposes. That's a matter of your agreement with the service provider.

I've prepared some code that is open source and publicly available on my GitHub account. This small console application allows you to generate a Metadata.xml file and properly sign it with the private key.

Now, you should send your Public X.509 Certificate (as a *.crt file, or PEM text) and this Metadata.xml via secure channel.

As soon as service provider replies with some connection endpoints, the first part might be over.

Integration workflow

You have a web application that implements some authentication workflow and allows users to sign in with their login and password. It means that you are the Identity Provider, and by doing this, you can eliminate some redundant steps and make a process simpler. So, imagine that we combine Identity Provider and your Web Store into one entity, like this:

It simplifies the overall picture. However, it's not that simple under the hood. What actually should happen in the end is we should have an XML document called SAMLResponse prepared and encoded in Base64. You have to send this document via an HTTP POST request to the service provider to authenticate the user and automatically redirect his browser to the third-party target service — see detailed steps in the diagram below.

Again, I've prepared a set of utility classes written in C#, so you can easily see how to execute those steps in your web application.

Below, you can find my comments on every important aspect of that process. But I believe, it will be much more easy to follow the steps in class SamlIntegrationSteps.cs -> method BuildEncodedSamlResponse(...).

Step 1. Creating SAML assertion XML is not harder than create a usual XML document. But you have to follow the SAML specification and documentation provided by your Service Provider to use the appropriate field names. Working example is here SamlAssertionAlgorithms.cs.

AssertionType assertion = new AssertionType
{
    ID = ...Assertion Id ...,
    IssueInstant = ...UTC Time...,
    Version = "2.0",
    Issuer = new NameIDType
    {
        Value = "...your Web Store URL here..."
    },
    Subject = new SubjectType
    {
        Items = new object[]
        {
            new NameIDType
            {
                Format = "urn:oasis:names:tc:SAML:2.0:nameid-format:emailAddress",
                Value = userData.GetUserEmail()
            },
            new SubjectConfirmationType
            {
                Method = "urn:oasis:names:tc:SAML:2.0:cm:bearer",
                SubjectConfirmationData = new SubjectConfirmationDataType
                {
                    NotOnOrAfter = ...UTC Time....AddMinutes(3),
                    NotOnOrAfterSpecified = true,
                    Recipient = settings.Recipient
                }
            }
        }
    },
    Conditions = new ConditionsType
    {
        NotBefore = ...UTC Time...,
        NotBeforeSpecified = true,
        NotOnOrAfter = ...UTC Time....AddMinutes(3),
        NotOnOrAfterSpecified = true,
        Items = ...conditions that you need...
    },
    Items = new StatementAbstractType[]
    {
        new AttributeStatementType
        {
            // ReSharper disable once CoVariantArrayConversion
            Items = ...attributes array...
        },
        new AuthnStatementType
        {
            AuthnInstant = ...UTC Time...,
            SessionIndex = ...Assertion Id ...,
            AuthnContext = new AuthnContextType
            {
                ItemsElementName = new [] { ItemsChoiceType5.AuthnContextClassRef },
                Items = new object[] { "urn:federation:authentication:windows" }
            }
        }
    }
};

Step 2. Signing of the SAML assertion can be done as described in official Microsoft docs. Working example is here SamlAssertionAlgorithms.cs.

Step 3. Encryption of the SAML assertion is implemented in SamlAssertionAlgorithms.cs using System.Security.Cryptography.Xml.

X509Certificate2 x509 = ...get certificate...

xmlElement.SigningKey = x509.PrivateKey;
xmlElement.SignedInfo.CanonicalizationMethod = SamlSignedXml.XmlDsigExcC14NTransformUrl;

// Create a reference to be signed. 
Reference reference = new Reference
{
    Uri = "#" + referenceValue
};

reference.AddTransform(new XmlDsigEnvelopedSignatureTransform());
reference.AddTransform(new XmlDsigExcC14NTransform());

// Add the reference to the SignedXml object. 
xmlElement.AddReference(reference);

// Add an RSAKeyValue KeyInfo (optional; helps recipient find key to validate). 
KeyInfo keyInfo = new KeyInfo();
keyInfo.AddClause(new KeyInfoX509Data(certificate));

xmlElement.KeyInfo = keyInfo;

// Compute the signature. 
xmlElement.ComputeSignature();

// Put the sign as the first child of main Request tag.
xmlAssertion?.InsertAfter(xmlElement, xmlAssertion.ChildNodes[0]);

Step 4. Adding the assertion document to the SAMLResponse is just about adding XML:

XmlDocument encryptedAssertion = new XmlDocument();

// Add namespaces
XmlDeclaration xmlDeclaration = encryptedAssertion.CreateXmlDeclaration("1.0", "UTF-8", null);
XmlElement encryptedRoot = encryptedAssertion.DocumentElement;
encryptedAssertion.InsertBefore(xmlDeclaration, encryptedRoot);

// Form Assertion element
XmlElement encryptedAssertionElement = encryptedAssertion.CreateElement("saml",
    "EncryptedAssertion", "urn:oasis:names:tc:SAML:2.0:assertion");
encryptedAssertion.AppendChild(encryptedAssertionElement);

// Add encrypted content
var encryptedDataNode = encryptedAssertion.ImportNode(encryptedData.GetXml(), true);
encryptedAssertionElement.AppendChild(encryptedDataNode);

// Form a document
var root = xmlDocument.DocumentElement;
var node = root.OwnerDocument.ImportNode(encryptedAssertionElement, true);
root.RemoveChild(xmlAssertionSource ?? throw new InvalidOperationException());
root.AppendChild(node);

Step 5. Signing the SAMLResponse is about almost the same as siging the Assertion. Working example is here SamlResponseAlgorithms.cs.

The End

Some service providers may avoid specific steps and do not require the signature or encryption. In this case, you may remove these parts of the code. Overall, feel free to use my examples in your apps, and I hope this will help you and your application engage users and grow the customer base.

Cheers!

Five facts about security to know in 2021

Anton Yarkov — Wed, 13 Jan 2021 10:17:40 +0000

With COVID-19 everybody went to remote work, and 2020 became a year with significant security risks at organizations' infrastructure, software, and hardware tools. I expect this trend to grow even more in 2021; it's going to affect not only organizations but also personal security while you at home.
Below you can find several facts that are might be essential and not evident for those who are non-experts in security. Please, keep those facts in mind in 2021:

It’s impossible to make unbreakable encryption, so security is about to focus on making the job of brute-force decryption too pricey to be cost-effective and achievable in the adequate timing.
The recommendation is to continually track updates in the world of encryption and hashing algorithms: your company and products should use the latest & greatest versions of security tools, security libraries, and configuration. For example, you should not use encryption algorithm 3DES and instead use at least AES/Rijndael, but even better is to use multi-layer encryption using signatures and/or RSA with public/private keys. It would not help if you still use hashing algorithms like MD5, SHA1, or SHA2. If that's the fact, then immediately jump to SHA256 or bcrypt/scrypt (assess your choice carefully - those two methods are not cheap in terms of either CPU or Memory consumption), or both like Dropbox did. Your entire infrastructure should rely on the latest versions of TLS, not TLS 1.0 or TLS 1.1.
Nobody cares about security until it hurts. So, white hat hackers are those who hurt you with relatively low cost.
The recommendation is that you pay the official companies that can provide you external security audit. It is much, much cheaper than to get down after an actual hacking attack.
In most cases, people are the weakest part of your security infrastructure.
The recommendation is to allocate some focus and time on teaching people, controlling their access to company resources, providing appropriate hardware and software. You and your colleagues should not use software that is not updating within the last year.
Security does not mean you should hide everything. Actually, using Open source solutions allows you to use highly secure and well-reviewed solutions instead of crappy custom made solutions. I would not say there are no stable proprietary solutions, but the facts they are hidden make it challenging to compare.
Regardless the type of licensing recommendation is to keep expertise in the software that you use. In other words, you should have staff who are experts in the selected tools, libraries, devices, etc.
Using latest version of Linux does not mean having full security turned on by default. You can use guides like this or this to make sure you are up to date with your operating system's latest security configuration.

In general, security is mostly about making yourself a difficult target. It’s like that joke where you go hiking with your friends and a bear attacks you. You do not need to be faster than the bear; you simply need to be faster than your slowest friend.

Stay safe!

Picture taken from open source assets

DEV Community: Anton Yarkov

The low-cost path to AI Mastery: building a Wiki Navigator with pure Similarity Search

The magic of Vector Embeddings

Ensuring algorithmic parity

C# training example: vector utility

JavaScript client example: real-time search

Beyond the Simple Lookup

The nuances of Similarity Search

Your next AI project starts now

Algorithmic Alchemy: Exploiting Graph Theory in the Foreign Exchange

FX Basics

An example

Graph representation

Math saves us, again

Graph algorithms

Bellman-Ford algorithm implementation

Detecting negative cycles

Avoiding negative cycles

Even little fluctuations matter

Automation using smart contracts

Why are we looking into this?

Links

Crafting Mazes with Graph Theory

How to create a maze

Creating a Maze Using Graph Theory

Universal implementation of BFS, DFS, Dijkstra and A-Star algorithms

Graph representation

Universal algorithm

BFS queue

DFS queue

Dijkstra queue

A-Star

Downsides

Final word

Exploring well-known path finding algorithms with SFML graphics library

The story behind

Goal

Imaginary world

Input

Output

Modelling the maps

How do we draw maps

We need to go deeper

Run and play

Final words

Links

Tip: Debug your Roslyn Source Generator with JetBrains Rider IDE

Tip of the day

API versioning notes

REST API everywhere

What's wrong with Public APIs?

Just follow someone's recommendations in API versioning. What can go wrong?

More to consider for Public API

Conclusion

Resources

GraphQL trade offs

GraphQL is not going to replace REST or SOAP.

GraphQL is created to solve a few specific problems

GraphQL brings trade offs

On GraphQL schema-stitching

The End

References

Writing self-documented code with low cognitive complexity

Self-documented code

Measuring readability of the code

Outcomes

A pragmatic guide to starting Communities of Practice in the organization

What is a community of practice?

Why to use communities of practice?

Key concepts for successul implementation of CoPs

Facilitator’s role is essential

Facilitating patterns to use

Best practices for organizing communities of practice

Work items

Work inside vs. outside the CoP

The ways to demo the work done by the CoP

Why exert the effort to market your CoP’s results?

Lifecycle

Checklists

I want to start a new community of practice. What should I do?