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.

Deconstructing AI: 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:

1. 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.
2. Querying (Query Phase): When a user submits a question, that query is also converted into a vector embedding.
3. 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.

Practicality over theory: 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.cs (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, for example, on rust similarity search example. 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 similar to one from chatbot.js
    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.

As you can see, it doesn’t take long to have a running app.

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:

1. 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.
2. 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.
3. 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
• Chromium similarity search demo
• Rust similarity search demo

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!

Developing Low-Cost AI-Based Similarity Search was originally published in optiklab on Medium, where people are continuing the conversation by highlighting and responding to this story.

NFT Wallets Unleashed: A Data Structures and Application Design Journey

Whether or not you’re caught up in the NFT hype, as a software engineer, staying abreast of recent innovations is crucial. It’s always fascinating to delve into the technologies underpinning such trendy features. Typically, I prefer to let the dust settle before jumping in, but now seems like a good time to explore “what NFTs are all about.”

Terminology

NFT stands for Non-fungible tokens. Non-fungible tokens are tokens based on a blockchain that represent ownership of a digital asset. Digital asset may be anything, from a hand-crafted image, a song, a music, a blog post or entire digital book, or even a single tweet (which is, basically, a publicly available record from a database of the well-known public company). These assets have public value and can be owned by someone.

Unlike fungible tokens, such as Bitcoins or Etheriums, which are replaceable with identical units (they have the same value and one can be exchanged for another), NFTs are unique (cannot be equally exchanged), ensuring the ownership of unique digital assets and enforcing digital copyright and trademark laws. NFTs are based on blockchain technology, guaranteeing ownership and facilitating ownership transfer.

What we build

We’re creating an NFT Wallet prototype using a C# console app with (not that famous yet) .NET CLI SDK. The System.CommandLine library, although still in beta, is promising and enables the creation of clean and efficient command-line interfaces.

The minimal requirements for NFT Wallets are as follows:

1. Keep the records of tokens’ ownership history.

2. Support Mint transactions (creating tokens).

3. Support Burn transactions (destroying tokens).

4. Support Transfer transactions (changing ownership).

We assume transactions are in JSON format, but for educational purposes, we’ll read them from a formatted JSON (text or file on disk) since we lack a real blockchain network server.

Keep it simple

To keep things simple, we’ll ignore details like specific blockchain networks, hash-generation algorithms for unique NFTs, and the persistent storage choice (in our prototype we will use an XML file on disk).

API

Considering the mentioned requirements and limits, we’ll support the following commands.

Read Inline ( — read-inline <json>)

Reads a single JSON element or an array of JSON elements representing transactions as an argument.

$> program --read-inline '{"Type": "Burn", "TokenId": "0x..."}' 
$> program --read-inline '[{"Type": "Mint", "TokenId": "0x...", "Address": "0x..."}, {"Type": "Burn", "TokenId": "0x..."}]'

Read File ( — read-file <file>)

Reads a single JSON element or an array of JSON elements representing transactions from the specified file location.

$> program --read-file transactions.json

NFT Ownership ( — nft <id>)

Returns ownership information for the NFT with the given ID.

$> program --nft 0x...

Wallet Ownership ( — wallet <address>)

Lists all NFTs currently owned by the wallet with the given address.

$> program --wallet 0x...

Reset ( — reset)

Deletes all data previously processed by the program.

$> program --reset

NFTs Transactions

From wallet transactions perspective, we need to support three types of operations as following.

Mint

{ 
  "Type": "Mint", 
  "TokenId": string, 
  "Address": string 
}

A mint transaction creates a new token in the wallet with the provided address.

Burn

{ 
  "Type": "Burn", 
  "TokenId": string 
}

A burn transaction destroys the token with the given id.

Transfer

{ 
  "Type": "Transfer", 
  "TokenId": string, 
  "From": string, 
  "To": string 
}

A transfer transaction changes ownership of a token by removing the “from” wallet address, and adds it to the “to” wallet address.

Transactions operations

In the following example of a batch of transactions, we create three new tokens, destroy one and transfer ownership for another one:

[
	{
		"Type": "Mint",
		"TokenId": "0xA000000000000000000000000000000000000000",
		"Address": "0x1000000000000000000000000000000000000000"
	},
	{
		"Type": "Mint",
		"TokenId": "0xB000000000000000000000000000000000000000",
		"Address": "0x2000000000000000000000000000000000000000"
	},
	{
		"Type": "Mint",
		"TokenId": "0xC000000000000000000000000000000000000000",
		"Address": "0x3000000000000000000000000000000000000000"
	},
	{
		"Type": "Burn",
		"TokenId": "0xA000000000000000000000000000000000000000"
	},
	{
		"Type": "Transfer",
		"TokenId": "0xB000000000000000000000000000000000000000",
		"From": "0x2000000000000000000000000000000000000000",
		"To": "0x3000000000000000000000000000000000000000"
	}
]

As seen, tokens are identified by imaginary hex-formatted values. Wallet addresses should be supported by our underlying imaginary blockchain network. Verification of these values is skipped, focusing on the efficiency of operations and storage in our NFTs wallet.

Data structure design

To support all necessary operations we have to think about efficient execution of a following three types of tasks:

• Persist information about ownership relationship between imaginary NFT token ids and NFT wallet addresses provided.
• Quickly answer what wallet contains a token, by token id.
• Quickly answer what tokens are owned by certain wallet.
• Efficiently change the ownership of the Token between the wallet addresses.

We begin by creating a class to represent a single transaction.

public class Transaction
{
 // Transaction type: Mint, Burn, Transfer, etc. 
 // As a type, we may use enum here as well.
 [JsonProperty("Type", Required = Required.Always)]
 public string Type { get; set; }

 [JsonProperty("TokenId", Required = Required.Always)]
 public string TokenId { get; set; }

 // Address of the Wallet to own Token Id created (Minted)
 [JsonProperty("Address", Required = Required.Default)]
 public string Address { get; set; }

 // From Address of the Transfer operation.
 [JsonProperty("From", Required = Required.Default)]
 public string From { get; set; }

 // To Address of the Transfer operation.
 [JsonProperty("To", Required = Required.Default)]
 public string To { get; set; }
}

In the world of NFTs, the owner is represented by a wallet address, and we add a timestamp to track when a new token is created or transferred between wallets.

public class OwnershipInfo
{
 [XmlElement("WalletAddress")]
 public string WalletAddress { get; set; }

 [XmlElement("Timestamp")]
 public DateTime Timestamp {  get; set; }
}

Most efficient algorithms should be executed with O(1), right? Hash-based collections allow us to support GET operations with O(1) efficiency, which means we have to use Dictionary< K, V > for the whole storage. But to make all operations efficient, we have to sacrifice memory as it’s not enough to have only one efficient collection. Instead, we are going to use multiple collections in memory. Let’s look at it piece by piece, first, and then discuss this solution.

Remember, in the following code we don’t verify tokens ids or wallet addresses.

Which wallet owns the token?

Since a token can be owned by only one wallet, a direct address-to-address map between Token ID (key) and Wallet Address (value) is used. This allows us to easily support the “ — nft” operation, answering the question of who the owner is.

public class TokenStorage
{
 // To easily find owning wallet by NFT token.
 public Dictionary<string, string> NftTokenWalletMap { get; set; }
}

public async Task<string> FindWalletOwnerAsync(string tokenId)
{
 if (_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId))
 {
  return await Task<string>.FromResult(_tokenStorage.NftTokenWalletMap[tokenId]);
 }

 return null;
}

Which tokens wallet owns?

To efficiently list tokens owned by a wallet, a map of Wallet Addresses (key) to lists of their Token IDs (value) is maintained, so we can easily support operation “- - wallet”.

public class TokenStorage
{
 // To easily find list of owned Tokens in the wallet.
 public Dictionary<string, List<string>> WalletNftTokensMap { get; set; }
}

public async Task<List<string>> GetTokensAsync(string walletId)
{
 var result = new List<string>();

 if (_tokenStorage.WalletNftTokensMap.ContainsKey(walletId) &&
  _tokenStorage.WalletNftTokensMap[walletId] != null)
 {
  result = _tokenStorage.WalletNftTokensMap[walletId];

  result.Sort();
 }

 return await Task.FromResult(result);
}

Ownership transfer and history

To efficinetly support the history of ownership changes for each token, we need to map Token Id (key) to a list of Owners Wallet Addresses (values). This list must be sorted in a way that we can efficiently take the last one (but still, be able to list all the history, when needed). We also want to efficiently insert new history records (to the end). Linked List is what suits well for this history-record data structure: it allows us to insert new records and take the last one with O(1) efficiency.

public class TokenStorage
{
 // To easily change the ownership.
 public Dictionary<string, NFTToken> NftTokenOwnershipMap { get; set; }
}

public class NFTToken
{
 public string TokenId { get; set; }

 /// <summary>
 /// Allows to efficiently insert new owners.
 /// </summary>
 public LinkedList<OwnershipInfo> OwnershipInfo { get; set; }
}

With these structures, we can efficiently support minting, burning, and transferring operations on NFTs in TransactionManager. Follow the comments in code.

Mint new token

private bool MintNFTToken(string tokenId, string walletAddress)
{
 // Is token really new/unique?
 if (!_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId))
 {
  // Do we know such wallet address?
  if (!_tokenStorage.WalletNftTokensMap.ContainsKey(walletAddress))
  {
   // Remember a new wallet address.
   _tokenStorage.WalletNftTokensMap.Add(walletAddress, new List<string>());
  }
  
  // Add token to the wallet to Wallet-Token records.
  _tokenStorage.WalletNftTokensMap[walletAddress].Add(tokenId);
  
  // Add Token-Wallet record.
  _tokenStorage.NftTokenWalletMap.Add(tokenId, walletAddress);

  // Create an Ownership entry in history
  var nftToken = new NFTToken
  {
   TokenId = tokenId,
   OwnershipInfo = new LinkedList<OwnershipInfo>()
  };

  // Insert the record
  nftToken.OwnershipInfo.AddFirst(
   new OwnershipInfo
   {
    WalletAddress = walletAddress,
    Timestamp = DateTime.Now
   });
  _tokenStorage.NftTokenOwnershipMap.Add(tokenId, nftToken);

  return true;
 }

 return false;
}

Burn token

private void BurnNFTToken(string tokenId)
{
 if (_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId))
 {
  string walletId = _tokenStorage.NftTokenWalletMap[tokenId];

  _tokenStorage.NftTokenWalletMap.Remove(tokenId);

  if (_tokenStorage.WalletNftTokensMap.ContainsKey(walletId))
  {
   _tokenStorage.WalletNftTokensMap.Remove(walletId);
  }
 }

 if (_tokenStorage.NftTokenOwnershipMap.ContainsKey(tokenId))
 {
  _tokenStorage.NftTokenOwnershipMap.Remove(tokenId);
 }
}

Transfer token

private bool ChangeOwnership(string tokenId, string oldWalletAddress, string newWalletAddress)
{
 // Validate that token is actually owned by From
 if (_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId) &&
  _tokenStorage.NftTokenWalletMap[tokenId].Equals(oldWalletAddress))
 {
  // Remove existing Wallet-Token record, it's not valid anymore.
  _tokenStorage.WalletNftTokensMap[oldWalletAddress].Remove(tokenId);
  // Add a new one.
  if (!_tokenStorage.WalletNftTokensMap.ContainsKey(newWalletAddress))
  {
   _tokenStorage.WalletNftTokensMap.Add(newWalletAddress, new List<string>());
  }
  _tokenStorage.WalletNftTokensMap[newWalletAddress].Add(tokenId);

  // Update a second map that maps back Token to Wallet.
  _tokenStorage.NftTokenWalletMap[tokenId] = newWalletAddress;

  // Now, create a new ownership history record.
  NFTToken nftToken = _tokenStorage.NftTokenOwnershipMap[tokenId];
  nftToken.OwnershipInfo.AddFirst(
   new OwnershipInfo
   {
    WalletAddress = newWalletAddress,
    Timestamp = DateTime.Now
   });

  return true;
 }

 return false;
}

Finally, our token storage data structures will look like this and will support all the necessary operations with O(1) efficiency with additional memory redundancy.

public class TokenStorage
{
 public TokenStorage()
 {
  NftTokenWalletMap = new Dictionary<string, string>();
  WalletNftTokensMap = new Dictionary<string, List<string>>();
  NftTokenOwnershipMap = new Dictionary<string, NFTToken>();
 }

 // To easily find owning wallet by NFT token.
 public Dictionary<string, string> NftTokenWalletMap { get; set; }

 // To easily find list of owned Tokens in the wallet.
 public Dictionary<string, List<string>> WalletNftTokensMap { get; set; }

 // To easily change the ownership.
 public Dictionary<string, NFTToken> NftTokenOwnershipMap { get; set; }
}

public class NFTToken
{
 public string TokenId { get; set; }

 /// <summary>
 /// Allows to efficiently insert new owners.
 /// </summary>
 public LinkedList<OwnershipInfo> OwnershipInfo { get; set; }
}

Application design

Following an Object-Oriented Programming (OOP) design, we create a number of entities:

1. All the transactions supported by a TransactionManager.
2. Every CLI command inherited from a base Command with business logic implemented in appropriate CommandHandlers.
3. ConsoleOutputHandlers play the role of a View Interface (similar to MVC concept) to print to the Console, which lets us potentially send outputs of the application to the Display, Network, Web etc.
4. We do use a NewtonsoftJson library to parse incoming requests as well as a System.Xml to work with our persisting XML-storage file.

All of this allows us to implement a set of unit tests that you also can find in the repository.

Now, thanks to System.CommandLine library, it’s easy to wire-up all the commands into a little application as following:

class Program
{
    static async Task<int> Main(string[] args)
    {
        var root = new RootCommand();
        root.Description = "Wallet CLI app to work with NFT tokens.";

        root.AddCommand(new ReadFileCommand());
        root.AddCommand(new ReadInlineCommand());
        root.AddCommand(new WalletCommand());
        root.AddCommand(new ResetCommand());
        root.AddCommand(new NftCommand());

        root.Handler = CommandHandler.Create(() => root.Invoke(args));

        return await new CommandLineBuilder(root)
           .UseHost(_ => Host.CreateDefaultBuilder(args), builder => builder
                .ConfigureServices(RegisterServices)
                .UseCommandHandler<ReadFileCommand, ReadFileCommandHandler>()
                .UseCommandHandler<ReadInlineCommand, ReadInlineCommandHandler>()
                .UseCommandHandler<WalletCommand, WalletCommandHandler>()
                .UseCommandHandler<ResetCommand, ResetCommandHandler>()
                .UseCommandHandler<NftCommand, NftCommandHandler>())
           .UseDefaults()
           .Build()
           .InvokeAsync(args);
    }

    private static void RegisterServices(IServiceCollection services)
    {
        services.AddHttpClient();
        services.AddSingleton<IFileSystem, XmlFileSystem>();
        services.AddSingleton<ITransactionsManager, TransactionsManager>();
        services.AddSingleton<IConsoleOutputHandlers, ConsoleOutputHandlers>();
    }
}

Run your Wallet

Now, we can run our little CLI. It contains a nice little help listing the commands (thanks to System.CommandLine library):

>nft.app.exe -h
Description:
  Wallet CLI app to work with NFT tokens.

Usage:
  Nft.App [command] [options]

Options:
  --version       Show version information
  -?, -h, --help  Show help and usage information

Commands:
  --read-file <filePath>  Reads transactions from the ?le in the speci?ed location.
  --read-inline <json>    Reads either a single json element, or an array of json elements representing transactions as
                          an argument.
  --wallet <Address>      Lists all NFTs currently owned by the wallet of the given address.
  --reset                 Deletes all data previously processed by the program.
  --nft <tokenId>         Returns ownership information for the nft with the given id.

If we read all the transactions from JSON file, then we can find XML wallet storage “WalletDb.xml” after execution is finished.

>Nft.App --read-file transactions.json

Now, let’s execute following transactions one by one and watch results:

>Nft.App --read-file transactions.json 
Read 5 transaction(s) 

>Nft.App --nft 0xA000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is not owned by any wallet 

>Nft.App --nft 0xB000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is owned by 0x3000000000000000000000000000000000000000 

>Nft.App --nft 0xC000000000000000000000000000000000000000
Token 0xC000000000000000000000000000000000000000 is owned by 0x3000000000000000000000000000000000000000 

>Nft.App --nft 0xD000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is not owned by any wallet 

>Nft.App --read-inline  "{ \"Type\": \"Mint\", \"TokenId\": \"0xD000000000000000000000000000000000000000\", \"Address\": \"0x1000000000000000000000000000000000000000\" }"
Read 1 transaction(s) 

>Nft.App --nft 0xD000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is owned by 0x1000000000000000000000000000000000000000 

>Nft.App --wallet 0x3000000000000000000000000000000000000000
Wallet 0x3000000000000000000000000000000000000000 holds 2 Tokens: 
0xB000000000000000000000000000000000000000 
0xC000000000000000000000000000000000000000 

>Nft.App -—reset 
Program was reset 

>Nft.App --wallet 0x3000000000000000000000000000000000000000
Wallet 0x3000000000000000000000000000000000000000 holds no Tokens 

Outcomes

As we can see, we were able to implement all Wallet operations with O(1) efficiency. Unfortunately, it involves trade-offs in memory usage. In production scenarios, considerations for large datasets that may not fit into a single machine’s RAM might lead to compromises. Depending on requirements, sacrificing efficiency for optimized memory usage or vice versa may be necessary.

While this example demonstrates a compromise for a standalone system, in a production environment, third-party software supporting scalable mappings with redundancy might be preferred. This introduces additional complexity but is crucial for operational efficiency in distributed systems.

This exploration provides insights into the world of NFTs and the data structures supporting their operations. I hope it was interesting and useful for you.

Stay tuned for more!

NFT Wallets Unleashed: A Data Structures and Application Design Journey was originally published in optiklab on Medium, where people are continuing the conversation by highlighting and responding to this story.

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.

The task explicitly mentioned 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 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 their exchange rate.

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 from 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 vary among banks or 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 can access 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 the exchange rates of these intermediate transactions.

An Example

Let’s imagine we want to buy Swiss Franks for US Dollars, exchange Franks for Japanese Yens, and then sell Yens for US Dollars again. In Autumn 2023, we have the following exchange rates:

1. We can buy 0.91 CHF (Swiss Frank) for 1 USD.
2. We can buy 163.16 Japanese Yens for 1 CHF.
3. 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 of less than one:

1.098901099 * 0.006128953 * 149.2537313 = 1.005240803

As we can see, the result is larger than one. 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 USD

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

This means that in the real currencies, it will give us more than 1 US Dollar. Here’s what that looks like:

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

Whoa, 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 three 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 the 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 consider more exchange platforms and resources.

To address real currency arbitrage problems, a complete graph encompassing all currency quote relationships 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    }  YE

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, logarithms are a mathematical way to transition from a product to a sum to circumvent this limitation. 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 two 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 the 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 challenge the algorithm since it continually finds better solutions on each iteration.

To address this issue, the Bellman-Ford algorithm 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 the 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 billions of 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 negative-cycle graphs.

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 halts and displays a message:

Graph contains negative cycle.

We were 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)

Whoa! Our code identified several profitable chains despite our data being “a bit dirty.”

All the code examples mentioned above, including test data, are 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);

Here’s the 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:

1. 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.
2. 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 two to three 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 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 creating 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 has considerable hype and significant risks related to wallets and legal compliance.

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

Why Are We Looking Into This?

Despite global economics' complexity, obscurity, and unpredictability, 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 peacefully benefit one another, 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 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:

• Importers, Exporters, and Exchange Rate Disconnect
• Currency choice and exchange rate pass-through
• Exchange rate puzzles and policies

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

However, playing with code and finding a solution for a practical problem helped me get more clues on it. I hope you enjoyed this little exploration trip as much as I am.

Stay tuned!

Links

• Source code with all these examples
• Sedgewick R. — Algorithms in C, Part 5: Graph Algorithms
• Bellman Ford Algorithm Code Implementation
• William Fiset’s GitHub examples — Bellman Ford On Adjacency Matrix
• William Fiset’s GitHub examples — Bellman Ford On Edge List

Algorithmic Alchemy: Exploiting Graph Theory in the Foreign Exchange was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

In my previous article, we delved into pathfinding problems 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 immersed myself in the vast, 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 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 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. It will often 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.

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 generation process often starts with creating a “perfect” maze.

A “perfect” maze, 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 a path from the start to the end.

In computer science terms, such a maze can be described as a Spanning Tree over a 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 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 generates 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, multiple algorithms are available.

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 an 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 you’re inspired to explore this fascinating world of mazes and embark on your own journey.

Stay tuned!

Crafting Mazes was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

Behind the Scenes

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. Participants were tasked to find optimal routes on a map and optimize delivery using robotic couriers.

As I delved into the topic, I discovered that despite route finding being a solved problem, it continued to interest 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 exploring this field intriguing and developing 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 universally. However, showcasing significant performance differences among these algorithms in that project was challenging.

I aim to use improved test data in this article 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 implementation.

Imaginary World

Imagine a technically advanced and innovative city where the future has arrived long ago. In this city, courier robots deliver most orders, and it has become a rarity for someone 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 precisely 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 the original 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 when the order appeared to its delivery in seconds.

The total number of points 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, and Costc is the cost of building one robot. The Costc and MaxTips values are set in each test. If you earned fewer 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 incorrect actions.

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 MaxTips and Costc parameters for my first implementation and may consider that in the 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 receive 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 fond of maps represented as a grid of cells. Thus, I prefer to render all the results and map them as a grid on a cell-by-cell basis.

There is also an option to execute a path search right on the grid without using any additional data structure (I have implemented this for learning purposes. You can see the results in the code).

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

To split the logic and responsibility, I have a Navigator entity responsible for executing path finding according to the orders and tasks configuration specified via AppConfig 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 configuration properties. They are ignored during the application run. Since there is no way to comment on part of the JSON file, I use underlining in the property name so it can stay in the config file but not be used.

The 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 many examples of input parameters and test data. Starting from very small parts that let you debug and learn the code, finishing with a huge piece of map (from the real existing city) that allows us to measure the performance of a Graph algorithm.

How Do We Draw Maps

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

To find a path in the graph, we have to represent it efficiently. Like in my previous article, I have used an 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 exploring grids, it’s not necessary to use graphs at all. We are capable of traversing grids using BFS/DFS algorithms cell by cell without thinking about edges. See the method _GetPathByBFSOnGrid.

First, the initialization code reads the file and converts it into the grid row by row and column by column. Here’s what that looks like:

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 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 representation is useful to draw on the screen using the SFML library. We can draw it by creating geometric objects (this is precisely 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, for larger maps, we can do it pixel by pixel, which is more efficient. Here’s what that looks like:

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 what a map defined by the file test_25_xmax would look like.

Initially, the file’s definitions look like this:

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

And a map rendered with SFML looks like this:

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

The SFML library makes it 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 that pressing the space button will trigger the program to read and render the map file. Then, you can load routing tasks and calculate the shortest path between two points on a map by creating a second trigger (press the space button again). Here’s how to do that:

...
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, which all have their limitations, so I also implemented multicolor maps that multiweighted graphs can represent.

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

So now, I have implemented multicolor maps that look joyful — like a game that’s ready to play (example from file test_31_multi_weight_graph_map):

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

As a challenge, we should now handle maps with very flexible configurations. RectangularMap.cpp 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 the type of Graphs I currently use), but I have some ideas to use it in future improvements.

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

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

There are also some fun features, like a Focus feature allowing one to render only a particular map part. It changes focus by rerendering the necessary part using the Observer pattern when the user presses the PgDown or PgUp buttons. Improving this feature and implementing “Zoom” functionality is pretty easy. Use it as a homework assignment if you like it.

Focus feature with a working map file, test_29_yandex_weighten_real_map:

The Classes diagram looks like this:

Run and Play

The most joyful part is running this little application and 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 and changing the code's logic.

After starting, you need to press SPACE. An application will render a map according to the configuration file, and it makes a lot of sense to start exploring from the simplest test cases and then transition to the most complex ones.

Pressing SPACE again executes the routing algorithms and finds the path between the start and the nearest order. By the way, it’s not done yet, but it is easy to implement ways to read all the rest of the orders available in map configuration files and to execute pathfinding to all of them.

Here is the route found on the map defined by file test_18_yandex_super_high_res:

It is also capable of finding routes in the maps that simulate existing cities, like the 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, the application will treat the 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 find it fascinating and will learn a lot from it.

Stay tuned!

Links

1. Universal implementation of BFS, DFS, Dijkstra, and A-Star algorithms
2. JPS+: Over 100x Faster than A* by Steve Rabin
3. A* Optimizations and Improvements by Lucho Suaya

Exploring Well-Known Path-Finding Algorithms With SFML Graphics Library was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

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

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:

1. The number of the entering node for each edge in the graph.
2. 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:

• Generating a list of nodes
• Creating custom connections

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

  // Traverse nodes starting from start node.
  while (!customQueue.isEmpty()) 
  {
    int current = customQueue.getFirst();
    // If we found finish node, then let's print full path.
    if (current == finish) 
    {
      vector<int> path;
      int cur = finish;
      path.push_back(cur);
      // Recover path node by node.
      while (previousVertex[cur] != -1) 
      {
        cur = previousVertex[cur];
        path.push_back(cur);
      }
      // Since we are at the finish node, reverse list to be at start.
      reverse(path.begin(), path.end()); 
      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;
        // Calculate cost of moving to this node.
        ptrShortestPath->at(to) = ptrShortestPath->at(current) + weight;
      }
      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!

Universal implementation of BFS, DFS, Dijkstra and A-Star algorithms was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

Current crypto-hype in large IT companies makes everyone believe there are experts in the topic. Folks jump into investments thinking they join to the success with someone who knows what they are doing. But it turns out it’s not.

This leads me to a question: Are cryptocurrencies the pyramids of the current decade?

This kind of comparison is not new, but as a developer highly involved in everything that happens in IT and in FinTech specifically, I find more and more parallels between two ideas. For some, they allow earning. But for the majority, they only give hope for a miracle (to become rich, achieve what they want, etc.).

Neither was the goal of cryptocurrency creation, actually. Technically, the two main big ideas behind them are:

• The idea of ​​storing information about transactions in the form of a chain of records dependent on each other — Blockchain (broke a record in the middle, the chain “breaks” and all subsequent records automatically become invalid);
• The idea of ​​confirming each new transaction by performing some valuable computing work in a distributed network of decentralized “workers” — Proof-of-work. I must say that there are other ways to confirm transactions, but so far, the idea of ​​”wasting time and electricity” has turned out to be more workable than others;

That’s it. There was no talk of any earnings or profits. At the same time, cryptocurrencies have existed for about 15 years and still cannot break through a thick layer in FinTech. For a moment, the classic pyramids (the so-called Ponzi scheme) appeared more than 100 years ago, so in comparison with this idea, cryptocurrencies are still young, and you can try to draw parallels and understand what else they can grow into.

Unhealthy signals in crypto

Cryptocurrencies can have reasonably practical uses. But at the moment, even in regulated environments, they are more often created and used for hype, marketing of individual companies and their leaders.

What can we say about countries where regulators cannot reach out to potential fraudsters? Here we very often see fraud in its purest form, attempts to “hit the jackpot and hide,” confuse end users, and sometimes even “cut” from the government investments.

In 2021, we all saw one of the last attempts to do something with cryptocurrencies: NFT — one another game in an attempt to make money on something new and incomprehensible.

What makes them attractive and remind me of a pyramid:

• The opportunity to “jump on the train of success” earlier than others and become rich. It usually comes with arguments of the right moment and the low price initially.

• Everything is based on “faith”: lack of any confirmation of declared quality or performance. Unclear “roots,” (the original companies or the people who created the product). There is no way to talk to the source. And in both cases, the explanations are vague and so abstract (and in both cases, it is intentionally so) that even technically savvy people cannot distinguish a technical Fake from an actual working model. I know it’s true for the world of science as well; however, we should distinguish the absence of proofs (in pyramids and crypto) and technically complex proofs (math, physics, etc.). In the world of cryptocurrencies, the terms are complex, so it is frequently misused, and very few specialists at the moment can talk about “crypto” in a technically correct language.

• The ability to touch the “new big idea” without the necessary knowledge. Opportunities being sold are deliberately reduced to the level of “understanding” by a client who is willing to invest. Everything is explained so that the one thinks he/she understands what it is about.

In fact, any really big ideas were based on mathematical apparatus and then had to go over a tough time check (before it became clear that the concept is vast). An unprepared person hardly has the opportunity to keep up with them on purpose.

Unhealthy trends in 2021

Unfortunately, things are only getting worse. Here are some trends of 2021:

• Every self-respecting IT company has open vacancies with the Crypto prefix. That is, more and more products will appear on the market, with the prefix crypto, blockchain, token, etc.
• Media people often jump on the hype wave. Price surges certainly have beneficiaries. For example, Elon Musk in 2021 either hated or praised individual cryptocurrencies, which led to huge jumps in the latter’s price.
• A couple of years earlier, we saw dozens of so-called ICOs, during which funds were raised, and then the organizers evaporated in an unknown direction.

Everything that happens to cryptocurrencies is someone’s attempt to hit the jackpot. In general, this is nothing more than an idea with no practically helpful solution so far. It may appear, but as long as the scales are in the balance between those “for whom it is profitable” and “for whom it is not profitable,” the latter are winning.

The financial sector is driven by technology, but it is not based on technology (Boom!). Instead, it is based but on relationships between big companies and “uncle Bob’s,” agreements and contracts, handshakes, and even personal sympathy.

A company’s success in the FinTech sector depends on negotiating with several intermediaries and issuing a financial tool with the lowest possible commission so that clients are not afraid to use it. We are not always talking about convenience or UX, here it is from case to case. Therefore, FinTech is (mainly) the B2B sector. That is, more companies are working with companies in it.

FinTech enters the B2C sector and works with end clients, but only to make the client essentially a Business (profitable for itself) and a source of profit. This is why your bank is constantly offering new tools, from insurance and protection to cost control. All this is a concern with a downside (I’m not saying that this is very bad, I state that any coin has a downside).

Many financial instruments have not changed for decades simply because they are already profitable. For the last ten years (or more), FinTech companies have been bringing their old technologies to Asia and Africa. They took it out as it is, changing nothing. They are applying essentially the same ideas to a new, not yet matured audience. Expanding the scope is good for the end customer, but it’s not always the best solution, so you need to understand that they did not do it out of kindness. That is, someone, benefits greatly from it.

Are you familiar with the structure of most Forex brokers? The idea is to find people willing to bring all their pennies and with huge leverage (10x, 100x, 1000x, etc.) from the broker to convert them into other currencies in the hope of that the rate will jump up… and there is no certainty that this will happen since trading occurs in short periods: mainly during the afternoon session of the exchange for 8 hours (from 9 am to 5 pm).

Today you are lucky, and you are left with nothing the next day.

Don’t be tricked

See the parallel with cryptocurrencies? Many people buy them only to sell them profitably and convert them back to their currency. And this immediately leads to fraudulent schemes, and states consider it their duty to protect against it. That’s why cryptocurrencies will only become widely-used when there is a way to control them. So that can convert their clients into a controllable source of profit, which is against one of crypto’s main ideas — decentralization (above). So, in anyway, the idea of ​​cryptocurrencies will degenerate into a controlled technology sold to the uninitiated in every corner under the guise of a decentralized blockchain tokens.

I am sure that many of us had or have relatives who were influenced by the classical pyramids and belief in miracles. With cryptocurrencies, they are even more vulnerable.

In the article, I draw parallels with what we are already familiar with. Want it or not, cryptocurrencies will stay with us forever, like the pyramids. And it will continue to spread.

And in order not to unknowingly fall into the trap the next time you decide to replenish the wallet of virtual “bunnies,” be vigilant, watch your feelings and sensations. Ask yourself, why are you doing this? Do you have any practical working needs? Or are you craving a quick profit at this moment? In the latter case, most likely, it will trick you.

Good luck!

Are there experts in the crypto-industry? was originally published in optiklab on Medium, where people are continuing the conversation by highlighting and responding to this story.

In this article, I will share practical and straightforward advice to stop holy wars, arguments about code quality, and the necessity of refactoring, simplifying, and adding comments or documentation for the code. While I will refer to exact commercial tools in the second half of the article, I want to say that I’m not affiliated 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 programmers’ lives.

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 is 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:

1. 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).
2. 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 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. They must also be resilient, scalable, configurable, support multiple platforms, versions, etc.

Some people claim that SQL and HTML answer both HOW and WHAT at the same time. I will 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. This is usually called Mental Model. No matter how simple or complex, there is always some mental model underlying the code (even the bad one). It might be a domain model or another 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, many books have been written on this topic. But 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, making understanding the model difficult.

Questions like HOW and WHAT are orthogonal because there are several ways to achieve the same goal. Imagine climbers analyzing the better way to reach the mountain peak by different paths. They consider various aspects, sum up their own experience and common knowledge about the mountain relief, weather and air conditions, time of the year, the group's readiness level, etc. Finally, they select the optimal path to climb. The optimal path doesn’t explain all 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, allowing them to make the code more readable.

The mental model answers the WHAT, while the code tells us the HOW.

Measuring the 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 — caused by the problem to be solved, and nothing can remove it
• Accidental complexity — relates to the problems engineers create that can be fixed

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 cyclomatic complexity. 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, the left and right pieces of code are not identically complex. The left one is harder to read and understand. We may believe the code is finding the Sum of Prime Numbers, a famously known problem, but an experienced developer will never think it solves the task until they verify it’s true:

• Does the method’s name clearly state what the code does?
• Does the code achieve the mission?
• Does the code miss some use cases, and what are they? (i.e., what are the limitations of the code?)

Now, imagine how hard it is to understand something more specific about the domains that aren’t 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. The metric is based on three rules:

1. Ignore structures that allow multiple statements to be shorthanded into one.
2. 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).
3. 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 the 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. Here’s how to do that:

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 at a simple production example. To find it, you can do the following: Sonar Cloud -> Measures -> select Complexity filter

You can find the total complexity measurement for the group of files (folder) on the left side. Here, we can see the numbers doubled: 134 against 64. You can see file-by-file differences as well.

The 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 the Cognitive one.

Outcomes

It looks like we have a way to measure code complexity, and I wish more tools were available to implement this, but we can already 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 to move toward 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 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 when 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 exciting food for you to dig into this and showed you how Cognitive Complexity can be used in your daily life.

How To Write Self-Documented Code With Low Cognitive Complexity was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.

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:

1. 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.
2. 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.
3. 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

1. 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.
2. 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.
3. The success of a CoP hinges on trust between and among its members.
4. Do stay focused on the primary purposes of a CoP: to learn from each other through sharing and collaborating.
5. 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:

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

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.

Checklists

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

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:

Where to learn more

• https://www.scaledagileframework.com/communities-of-practice/
• https://teachingcommons.lakeheadu.ca/communities-practice-quick-start-guide
• https://www.organisationalmastery.com/communities-of-practice/
• https://www.nickols.us/CoPStartUpKit.pdf
• https://ktdrr.org/resources/rush/copmanual/CoP_Manual.pdf
• https://www.talent.wisc.edu/home/LinkClick.aspx?fileticket=B6rgxakCMtI%3D&portalid=0

Starting Communities of Practice in Your Organization was originally published in optiklab on Medium, where people are continuing the conversation by highlighting and responding to this story.

Who should read it

This article is for web content makers and owners of the public content platforms, web developers, and anyone who can suddenly publish content that might become a subject of DMCA claim.
A couple of examples are Twitter, GitHub, Vimeo platforms that allow users to publish pictures, videos, and source codes that might appear to violate copyright laws.

Disclaimer

Of course, when we are talking about Public resources like Twitter, it is not a problem for someone to write a web-crawler smart enough to analyze specific resources and copy/download all the possible content from it (or save the content on the user machine). In this case, your platform/web-site is simply one point in the chain of content distribution and does not know how this content is supposed to be shared after all. Since it is a separate resource with its mission and reasons to work with this information (so they might need or don’t need to satisfy DMCA rules), I don’t think it’s something you can do with it. Web-crawlers overall may become a massive problem in the DMCA applicability. On the other side, they play a substantial role as an external cache that allows people to find information lost on the original resource.

So, what’s the problem?

It’s not that simple when we talk about such public and well-known resources like Way Back Machine (https://web.archive.org/), though. They have publicly announced mission

“is a digital archive of the World Wide Web.”

In other words, they are going to re-publish all the content they found on the internet. They are doing it straightforwardly. And authors and platform owners definitely should care about it, because it is a de-facto mirror of your web site.

Recently, I made a couple of interesting investigations and reported both to GitHub and Twitter officials. So, I think it will be valuable to share some details, so reader might understand the problem better.

Case with GitHub

Usually, when some repository becomes a subject of DCMA claim, then you couldn’t access the code repository and see this kind of message:

However, you can go straight to the Wayback Machine and find this page alive some time ago, look into it, read the whole content and, guess what? You can download the DMCA’d source code as a ZIP archive right from there.

Case with Twitter

If you go to https://twitter.com/Notices_DMCA then you can find a whole bunch of DMCA’d twitter posts.

Then, you should use your e-mail to officially request access to the original URLs via https://www.lumendatabase.org and get this information in a minute or so. Now, you can use it to find the images on the web archive.

I’m sharing this because it outlines things that you might not worry about until you reach the point of no return. And I already communicated with both GitHub and Twitter about these use cases. But guess how many more out there?

Why do I care?

Imagine how you feel if your business becomes threatened one day by somebody sharing your private assets? It’s a real issue many people are facing today.

Imagine if some source codes are not just stolen but also modified and re-published with some virus or trojan program inside?

At the end (maybe exaggerated example), imagine if you or your family member become slandered by the crowd with any photos or anything else that become publicly available. This might hurt a lot. And there are no cheap ways to do anything with it.

If all development teams followed some easy-to-use rules and frameworks and handle such cases appropriately and accurately, it would be beneficial.

So, what do I do?

Nowadays, if you develop a new “Clubhouse” startup that might reach millions of users daily, you should think about many things:
- GDPR(at least in the EU),
- copyright and DMCA (at least in the USA),
- data persistency and data retention policies,
- etc etc.
It’s not enough to put an image or an archive file on your web-site directly linked to the resource, allowing anyone to crawl all your resources and keep forever anywhere automatically. Again, this might play a GOOD or a BAD role, depending on the situation. But it would be best if you thought about potential cases in advance.

Where to start

If you feel that your database or file storage is full of content that might be a subject of DMCA, then I would start from this:

1. Go over your database of the DMCA’d content (i.e., the content, links, etc., that was a subject of a claim under DMCA) and aggregated all necessary information about the content that has to be closed from public access. This list should be available to teams building Web Crawlers via subscription mechanisms of any kind (rss, email, xml/json/rest/wcf/… files or APIs, etc.).
2. Update terms & conditions to publicly mention the rules of re-publishing content and specific steps, regulations, and requirements that you follow to protect data privacy & security and DMCA. It would help if you said that anyone who’s copying their content should be automatically responsible for following the same rules. Publish the appropriate documentation and API for developers that will help them to learn about the DMCA’d content mentioned above and automatically remove it from their databases or storage of any kind.
3. Ask the community to work together and form a list/database of the most well-known web crawlers and web-sites available on the internet (I mean web-sites that are easily available and work similarly to Wayback Machine — mirror your data). Ask every team/company that you found to follow the rules and remove DMCA’d content, provide them documentation and API mentioned above.

If you are starting a new feature that allows people to upload and share content with anyone,, then I would also recommend you to work on preventing such issues in the future as so:

1. Any resource (image, file, external link, etc.) should not be available by simple direct link, i.e., it should require additional user interaction to see the content (i.e., to make it downloadable by browser or API). Technically, this might be done using additional scripting to form a link after the user interacts with the user interface. And not after DOM (document object model) has been loaded into the browser. By doing this, you will make 100% of “simple” web crawlers unable to download the content — only the look & feel of the page. As been said in my disclaimer above: you still not protected from “smart” crawlers explicitly made for your web-site.
2. Know who crawls you, i.e., see #3 above. You can build a list of the most well-known crawlers and control their access to specific content by restricting URL access. For example, you would give access to HTML/CSS by crawling the link https://twitter.com/server1/… but limit downloading pictures from https://mycoolwebsite.com/imgserver1/… until the user interacts with the authenticated session.

I listed some of the technical and organizational solutions that I would execute to handle the issues with DMCA in a more automotive way. I know that complicates things enough for somebody who has tiny budgets.
But as problems evolve, I believe large companies should figure out cheaper ways.

Please, help me in the comments to generate more ideas and ways to handle this.

Links

• DMCA (https://en.wikipedia.org/wiki/Digital_Millennium_Copyright_Act)
• Way Back Machine (https://web.archive.org/)
• Web Crawlers (https://en.wikipedia.org/wiki/Web_crawler)
• What is DOM? (https://learnreact.design/posts/what-is-react)
• The Lumen database (https://www.lumendatabase.org)
• Twitter DMCA’d posts (https://twitter.com/Notices_DMCA)

Web crawlers make it harder to follow Digital Millennium Copyright Act, so developers have to… was originally published in optiklab on Medium, where people are continuing the conversation by highlighting and responding to this story.