Kruskal's Algorithm in C++

A simple C++ implementation of Kruskal's algorithm for finding minimal spanning trees in networks. Though I have a previous posting that accomplishes exactly the same thing, I thought that a simple implementation would be useful, one using a straightforward Graph data structure for modelling network links and nodes, does not have a graphical user interface and does not use the Boost Graph Library, which can be complicated to use and not to everyone's preference. Pseudocode KRUSKAL(G): A = ∅ foreach v ∈ G.V: MAKE-SET(v) foreach (u, v) ordered by weight(u, v), increasing: if FIND-SET(u) ≠ FIND-SET(v): A = A ∪ {(u, v)} UNION(u, v) return A The Graph data structure The Graph data structure is described in more detail in a previous post under the section titled "An alternative Graph class". Suffice to say it provides us with a means of inserting and deleting network links so as to capture a network topology. Class outline as follows: [code language="cpp"] #include <vector> #include <algorithm> // This code is from "Algorithms in C++, Third Edition," // by Robert Sedgewick, Addison-Wesley, 2002. class Edge { public: int v, w; double wt; Edge(int v = -1, int w = -1, double wt = 0.0) : v(v), w(w), wt(wt) { } }; typedef std::shared_ptr<Edge> EdgePtr; struct EdgeSort { bool operator() ( const EdgePtr& ep1, const EdgePtr& ep2 ) { return ep1->wt < ep2->wt; } }; template <class Edge> class DenseGRAPH { private: int Vcnt, Ecnt; bool digraph; std::vector <std::vector<EdgePtr>> adj; public: DenseGRAPH(int V, bool digraph = false) : adj(V), Vcnt(V), Ecnt(0), digraph(digraph) { for ( int i = 0; i < V; i++ ) adj[i].resize( V ); } int V() const { return Vcnt; } int E() const { return Ecnt; } bool directed() const { return digraph; } void insert( EdgePtr e ) { int v = e->v; int w = e->w; if (adj[v][w] == 0) Ecnt++; adj[v][w] = e; if (!digraph) adj[w][v] = e; } void remove(EdgePtr e) { int v = e->v; int w = e->w; if (adj[v][w] != 0) Ecnt--; adj[v][w] = 0; if (!digraph) adj[w][v] = 0; } EdgePtr edge(int v, int w) const { return adj[v][w]; } // Get the weighted edges void edges( std::vector<EdgePtr>& edges ) { for( int u = 0; u < V(); ++u ) { DenseGRAPH<Edge>::adjIterator A(*this, u); for ( EdgePtr e = A.beg(); !A.end(); e = A.nxt() ) { if ( NULL != e ) { edges.push_back( e ); } } } } class adjIterator; friend class adjIterator; }; template <class Edge> class DenseGRAPH<Edge>::adjIterator { private: const DenseGRAPH &G; int i, v; public: adjIterator(const DenseGRAPH<Edge> &G, int v) : G(G), v(v), i(0) {} EdgePtr beg() { i = -1; return nxt(); } EdgePtr nxt() { for (i++; i < G.V(); i++) if (G.edge(v, i)) return G.adj[v][i]; return 0; } bool end() const { return i >= G.V(); } }; [/code] Example Consider the following 11-node network showing the network nodes and the weight values of the links connecting them: Which is built using multiple calls to the insert API as follows: [code language="cpp"] DenseGRAPH<Edge>* graph = new DenseGRAPH<Edge>( 11, true ); graph->insert( EdgePtr( new Edge( 0, 1, 1.0 ) ) ); graph->insert( EdgePtr( new Edge( 0, 2, 0.6) ) ); graph->insert( EdgePtr( new Edge( 0, 3, 1.0 ) ) ); graph->insert( EdgePtr( new Edge( 0, 4, 1.0 ) ) ); graph->insert( EdgePtr( new Edge( 0, 5, 1.1 ) ) ); graph->insert( EdgePtr( new Edge( 1, 4, 1.8 ) ) ); graph->insert( EdgePtr( new Edge( 1, 10, 1.9 ) ) ); graph->insert( EdgePtr( new Edge( 2, 3, 2.1 ) ) ); graph->insert( EdgePtr( new Edge( 2, 5, 2.3) ) ); graph->insert( EdgePtr( new Edge( 2, 6, 1.7 ) ) ); graph->insert( EdgePtr( new Edge( 3, 4, 1.7 ) ) ); graph->insert( EdgePtr( new Edge( 5, 6, 0.5 ) ) ); graph->insert( EdgePtr( new Edge( 5, 7, 0.7 ) ) ); graph->insert( EdgePtr( new Edge( 5, 8, 0.9 ) ) ); graph->insert( EdgePtr( new Edge( 5, 9, 0.9 ) ) ); graph->insert( EdgePtr( new Edge( 5, 10, 1.0 ) ) ); graph->insert( EdgePtr( new Edge( 6, 7, 1.9 ) ) ); graph->insert( EdgePtr( new Edge( 7, 8, 1.7 ) ) ); graph->insert( EdgePtr( new Edge( 8, 9, 1.6 ) ) ); graph->insert( EdgePtr( new Edge( 9, 10, 2.2 ) ) ); [/code] Implementation of Kruskal algorithm Kruskal's algorithm works by obtaining a sorted list of the network links, and then adding each least-cost link to another set while disallowing cycles: [code language="cpp"] void KruskalMST( DenseGRAPH<Edge>* graph, std::vector<EdgePtr>& mst ) { const int V = graph->V(); // Sort edges in non-decreasing order of their weight std::vector<EdgePtr> edges; graph->edges( edges ); std::sort(edges.begin(), edges.end(), EdgeSort() ); // Allocate memory for creating V ssubsets std::unique_ptr<subset[]> subsets( new subset[ V ]() ); // Create V subsets with single elements for ( int v = 0; v < V; ++v ) { subsets[v].parent = v; subsets[v].rank = 0; } for ( std::vector<EdgePtr>::iterator it = edges.begin(); it != edges.end(); ++it ) { EdgePtr edgePtr = *it; int x = Find( subsets.get(), edgePtr->v ); int y = Find( subsets.get(), edgePtr->w ); // If including this edge does't cause cycle, include it // in result and increment the index of result for next edge if ( x != y ) { mst.push_back( edgePtr ); Union( subsets.get(), x, y ); } } } [/code] Applying Kruskal then results in the following minimal spanning tree: Console output as follows: Kruskal C++ source code downloadable from here.

Comments

Post a Comment

Popular posts from this blog

Using the Supervisor Controller Pattern to access View controls in MVVM

Image
As discussed on a StackOverflow post , this is considered bad practice, so only use this when necessary. Step 1: Create a new WPF project Step 2: Add event handling code A number of classes are needed for doing command bindings in MVVM. Create the following classes and add to your Visual Studio project: RelayCommand.cs [code language="csharp"] using System; using System.Windows.Input; namespace SupervisorControllingPattern { public class RelayCommand<T> : ICommand { private readonly Predicate<T> _canExecute; private readonly Action<T> _execute; public RelayCommand(Action<T> execute) : this(execute, null) { _execute = execute; } public RelayCommand(Action<T> execute, Predicate<T> canExecute) { if (execute == null) throw new ArgumentNullException(nameof(execute)); _execute = execute; _canExecute = canExecute; ...
Read more

Getting started with Tesseract optical character recognition (OCR) library in Visual Studio

Image
This post is a how-to guide on how to get up and running with using the tesseract optical character recognition (OCR) library in a Microsoft Visual Studio environment. The original link can be found at the following github location: https://tesseract-ocr.github.io/tessdoc/Compiling.html#windows Step 1: Build the latest library (using Software Network client) Download and extract the latest SW (Software Network https://software-network.org/) client from the following location: https://software-network.org/client/sw-master-windows-client.zip Open a DOS command prompt and run the following commands: [code language="xml"] sw setup sw build org.sw.demo.google.tesseract.tesseract-master [/code] As shown in the following screenshot: Step 2: Install git if you have not already done so You will need git to download the libraries needed for this project. Download link for obtaining the git for Windows executables etc here: https://git-scm.com/download/win...
Read more

How to send an e-mail via Google SMTP using C#

Image
First things first, some useful StackOverflow links: https://stackoverflow.com/questions/9201239/send-e-mail-via-smtp-using-c-sharp https://stackoverflow.com/questions/17462628/the-server-response-was-5-7-0-must-issue-a-starttls-command-first-i16sm1806350 To demonstrate how this is done I first create a new Visual Studio project: Some example code for sending an email via a Google email account (smtp.goolgle.com) - obviously replace this with email / credentials of your own... I put the code within a try-catch block in order to capture any errors that may occur while attempting this. [code language="csharp"] using System; using System.Net; using System.Net.Mail; namespace EmailSmtp { class Program { static void Main(string[] args) { try { // Credentials var credentials = new NetworkCredential("someEmail@gmail.com", "somePassword"); // Mail message var ...
Read more