[Java] Prim algorithm to find Minimum Spanning Tree in a graph

The minimum spanning tree (MST) is a subset of all edges in a weighted, undirected, connected graph such that the resulting graph is still connected and the sum of all edge weights is minimal.

If we are not given a list of edges, but only a list of vertices and a formula to calculate the edge weight given two graph nodes, we can run a preprocessing step to generate ALL possible edges between ALL graph nodes and calculate their weight in O(V^2).

Then, starting from a random node, we greedily choose one reachable vertex which has minimal distance from the current node. We continue exploring until all graph nodes have been touched.

There might be multiple valid MSTs for a given graph, this algorithm will return one of them.

We use a queue sorted by weight to determine which edge (and therefore node) to visit next, this ensures that if a node is reachable via multiple edges, we always pick the smallest weight for it. Since the graph is fully connected, we are ensured eventually we will have picked ONE edge between each node in the graph, and the sum of weight of all the chosen edges is minimal.

This runs using O(E) space since we might add all edges to the queue and O(E log(E)) time since for each edge we add to the queue we pay the O(log(E)) cost of insert and remove operation.

If the graph was NOT connected, this will NOT return the MST, only the MST for the connected component where the chosen start node resides. We could adapt the algorithm to verify whether there are extra nodes not yet visited, and repeat the processing for each until we have created a MST for each connected component in the graph.

In case the graph is not conencted, an alternatve can also be Kruskal's algorithm.

You can find my implementation of primMinimumSpanningTree on my Gist along with some tests in PrimMSTJTests.

[Java] Graph union find algorithm

For an undirected graph, we can compute the disjointed sets that represent all connected nodes in the subgraph where each node resides.

For each set, we elect a representative, all nodes reachable in a set will have the same representative. The resulting view will be a tree where the representative sits at the root and all connected nodes are its children.

Example applications include: quickly verify whether 2 nodes in a graph have a path to each other (they must belong to same set) or calculating the minimum number of edges to add to a graph to make it fully connected (or the opposite).

It is based on 2 operations:

find(Vertex x)

which will return for a given node, the representative of its subset. We recurse up the tree where this node resides until the representative is found. We optimize the operation for future searches by including path compression, where once a representative is found, all nodes along the same path are updated to track it. This makes it so that the find operation runs in O(inverse Ackermann(V)), which is considered O(1) but more realistically is O(log(log(...(V))) or how many times we need to apply log(x) to its result starting with V until the output is less than 1. It is an extremely slowly increasing sequence.

union(Vertex x, Vertex y)

which will connect the subtree where node x resides to the subtree of node y, unless they are already part of the same subtree. To improve efficiency we track in O(V) extra space the rank of each subtree (its depth) and when merging two subtrees, we connect the one with minimum depth to the other, so the overall height of the resulting tree is kept as flat as possible.

It uses O(V) extra space, to track for each node who is the representative of its subset and O(V) to track the rank of the subtree rooted at each node.

It runs in O(V Ackermann(V)) time since we run 2 find operation for each edge (pair of nodes) we unite and use the union by rank with path compression method.

You can check my implementation of unionFind on my Gist along with some tests in UnionFindJTests.

[git] Add git options to Gitlab pushes

Using git it is possible to specify options during push operations to perform specific actions, for example you can have a successful push autocreate the PR/MR and even set additional flags.

You can do this by adding push-options -o OPTION directly via CLI when pushing or setting them globally in your .gitconfig file.

For example, when using GitLab adding the following options to gitconfig:

[push]
    pushOption = merge_request.create
    pushOption = merge_request.target=main
    pushOption = merge_request.squash
    pushOption = merge_request.merge_when_pipeline_succeeds
    pushOption = merge_request.remove_source_branch
    pushOption = merge_request.title="TODO CHANGE ME"
    pushOption = merge_request.draft

after each push you will:

- automatically create a draft MR

- set target branch main

- set title "TODO CHANGE ME"

- assign it to you (and respect any MR template you have eg for default reviewers) 

- set the flags to squash commits on merge

- set the flag to delete source branch on merge

- enable the automerge when all configured checks (pipeline success, required approvals, etc) pass

This small automation will likely help you speed up your development and help you include the CM concepts in your CICD pipelines

[Java] Workflow management in microservices

Also published on Medium.

[Google Sheets] Import data from Yahoo Finance

DISCLAIMER: This is not a stock picking recommendation, the tickers shown are used as example and not provided as financial or investment advice.

Google Sheets offers the GOOGLEFINANCE function which can be used to import market data.

Usage is simple, for example to get the price of a stock, first search for it on Google Finance, then look at the quote URL it generates and copy the exchange:ticker value into the function.

In this example we try to get the quote for A200 ETF traded on the Australian ASX exchange. The URL shows ASX:A200 after the quote part, therefore we should use:

=GOOGLEFINANCE("ASX:A200")

So far, so good. Sometimes however Google does not show data for a particular ticker, or it shows data only in another currency or from another exchange. 

For example, another ETF XESC shows quotes from many exchanges but is also traded on the German XETRA (XESC.DE), which is not sourced by Google. Or the CHSPI ETF traded on the Swiss Six exchange (CHSPI.SW) is simply not found at all.

[Windows 11] Default show more options explorer right click menu (old UI behavior)

One change with Windows 11 is that the right click menu in Explorer was replaced with some condensed version where the old behavior is hidden behind a "Show more options" entry. This makes some actions slower to find and quite annoying, for example 7-zip or Notepad++

To revert it to the nicer old UI you can add a personal registry key, by typing this in a command prompt:

reg.exe add "HKCU\Software\Classes\CLSID\{86ca1aa0-34aa-4e8b-a509-50c905bae2a2}\InprocServer32" /f /ve

Then logout and login again or restart explorer process to see the effect take place.

This is setting an override on the default config found under (which remains untouched):

Computer\HKEY_LOCAL_MACHINE\SOFTWARE\Classes\CLSID\{86ca1aa0-34aa-4e8b-a509-50c905bae2a2}\InProcServer32

To undo the change, simply delete the registry key created by the command.

[Tampermonkey] Disable Bing Chat search integrations

When using Bing search there are multiple places that integrate the Chat functionality with the ChatGPT AI. Some of these integrations are annoying and can be easily disabled by installing the Tampermonkey browser extension then adding a couple scripts to modify the displayed webpage and its behavior.

• Disable switch to Chat on page scroll up event:

 // ==UserScript==  
 // @name    Disable Bing Search Engine Scroll  
 // @namespace  your-namespace  
 // @description Disables scrolling on the Bing search engine page to prevent accidental scrolling into the Bing chat feature.  
 // @match   https://www.bing.com/*  
 // @version   1  
 // @grant    none  
 // ==/UserScript==  
   
 window.addEventListener("wheel", e=>{  
 if(e.target.className.includes("cib-serp-main")) e.stopPropagation();  
 });  

• Disable sidebar Chat autosearch functionality when disaplying search results:

 // ==UserScript==  
 // @name    Disable Bing Chat autosearch  
 // @namespace  your-namespace  
 // @description Disables the Bing Chat autosearch functionality on the right side of results when doing a search.  
 // @match   https://www.bing.com/*  
 // @version   1  
 // @grant    none  
 // ==/UserScript==  
   
 const element = document.getElementById("sydwrap_wrapper");  
 element.remove();  
 const element1 = document.getElementById("b_sydTigerCont");
 element1.remove();

Remember that of course these scripts might stop working one day if Microsoft decides to change something on their side, when that happens they will simply need to be updated.