# Graph Algorithms – a revision of all the basic ones.

Hello friends! This post will be a short review of the the most common and basic algorithms for undirected graphs.

#### Note: This is not a post intended for folks who are not at all familiar with graphs. For beginners a better starting point would be a book like this.

We will start by discussing the basic problems and then we will have a look at some common applications.

## Basic Problem 1 : Traversal

Problem Statement: graph traversal is the problem of visiting all the nodes in a graph in a particular manner, updating and/or checking their values along the way.

#### Solution 1 : Breadth First Traversal/Search (BFS)

TL;DR: search is limited to essentially two operations: (a) visit and inspect a node of a graph, (b) gain access to visit the nodes that neighbour the currently visited node.

Points to remember:

• Layer-wise search forming layers L[0],L[1],…,L[i] of nodes
• L[i] are neighbours to L[i-1] ,  and are not present in any of the earlier layers.
• L[j] is exactly j distant from S. (assuming non-weighted edges , each with cost 1)
• BFS tree can be obtained after running BFS.
• Any edge can be present between nodes not differing by more than one layer
• Any BFS routine produces the connected component that contains the root.
• O(m+n) running time and space.
• Efficient implementation using a queue.

Steps:

1. Explore all neighbours of root. Call them level 1.
2. Then explore all neighbours of nodes of level 1. Call them level 2.
3. Keep Exploring like this 🙂

Code:

Without Queue:

 #define nodecount 10000 bool discovered[nodecount]; vector > L;//Layers void BFS(int s, vector > & adjList)//BFS for arrays, without queue, non-recursive, by @arkanathpathak { fill(discovered, discovered+nodecount, false); discovered[s] = true; for(int v=0;v)); L[0].push_back(s); while(L[i].size()!=0) { L.push_back(*(new vector)); for(int j=0;j < (int)L[i].size(); j++) { int u = L[i][j]; for(int k=0;k<(int)adjList[u].size();k++) { int v = adjList[u][k]; if(discovered[v]==false) { discovered[v] = true; L[i+1].push_back(v); } } } i++; } }

view raw
BFS, with layers
hosted with ❤ by GitHub

With Queue:

 vector adjList[N]; int visited[N]; void bfs(int u) { visited[u] = 1;//mapping the visited nodes, by default 0 queue nq;//queue used nq.push(u);//push initial node while(!nq.empty()) { int tt = nq.front(); visited[tt] = 1; nq.pop(); for(int i=0;i

view raw
BFS with Queue
hosted with ❤ by GitHub

#### Solution 2 : Depth First Traversal/Search (DFS)

TL;DR: Greedy search, where search retreats only when it encounters a dead-end of the branch,i.e. all neighbours.

Points to remember:

• Like the BFS tree, a DFS tree is obtained.
• O(m+n) running time and space.
• If an edge (x,y) is not present in the DFS tree, then one is a descendant of the other
• Can be used to produce Topological Sorting.
• Can be used to produce SCCs(Strongly connected components) using Kosaraju’s two-pass algorithm.
• Simple recursive implementation possible that makes use of recursion stacks
• Non-recursively efficiently implemented using Stacks.
• Discovery times of every node follows parenthesis structure (Source: CLRS)
• For finding all paths, we can unmark the node  as visitied when we finish the loop.
• Levels are processed in reverse order for non recursive with respect to that of recursive implementation

Steps:

1. Explore first neighbour of root.
2. Then explore the first unexplored neighbour of the first neighbour
3. Keep exploring until you reach a node with no unexplored neighbours.
4. Backtrack at that node until you reach a node with unexplored neighbours.

Code:

With Recursion:

 vector adjList[N]; int visited[N]; void dfsrecursive(int u) { visited[u] = 1; for(int i=0;i

view raw
DFS with Recursion
hosted with ❤ by GitHub

Without Recursion, with Stack:

 vector adjList[N]; int visited[N]; void dfsstack(int u) { stack nstack;//stack used in place of recursion stack visited[u] = 1; nstack.push(u); while(!nstack.empty()) { int tp = nstack.top(); nstack.pop(); for(int i=0;i

view raw
DFS with Stack
hosted with ❤ by GitHub

#### Notes on Traversal

• BFS and DFS have same running time and space efficiency
• BFS and DFS can be used to find connected components.
• BFS and DFS can be used to find connected cycles (DFS is more efficient and can be used in directed graphs also, as backward edge produces cycle).
• Classification Of Edges(directed): Tree Edge, Forward Edge(connecting to descendant), Backward Edge(connecting to ancestor), Cross Edge(all other). In DFS, only tree edge or backward edge is possible.
• Classification Of Edges(un-directed): Tree Edge, Forward Edge(discovered by an ancestor), Backward Edge(discovered by a successor), Cross Edge. In DFS, only backward or forward or tree edges are possible.In BFS, only cross edges are possible.

## Basic Problem 2 : Shortest Paths

Single Source Problem Statement:  Given a undirected weighted graph G and a source node u, find the shortest cost paths from u  to all other nodes.

#### Solution: Dijkstra’s Algorithm

TL;DR: Algorithm starts at the source vertex, u, it grows a tree, T, that ultimately spans all vertices reachable from u. Vertices are added to T in order of distance i.e., first u, then the vertex closest to u, then the next closest, and so on.

Steps:

• Initialise a set P and a set Q, with P initially storing u with cost 0, and all other in Q with cost infinity.
• Change the priorities of the nodes in Q having an edge with u as their edge costs.
• Dequeue the minimum key node and add it to P.
• Adjust the priorities of other nodes in Q so that the cost of addition gets minimised.
• At the end, the keys are the shortest path costs.

Cost of addition is given by

Code:

 int shortestdistance[N]; int explored[N]; vector > adjList[N]; // stores edges with cost void dijkstra(int node)// Does not use priority queue, O(M+N2) implementation { shortestdistance[node] = 0; explored[node] = 1; int discovered = 1; int lastadded = node; while(discovered

view raw
Dijkstra's Algorithm
hosted with ❤ by GitHub

Proof of Correctness:
Proof by Induction on set P’s size: Lets assume that the paths are correct for all the previous nodes in P for some node v. Then if there exists some path with smaller cost it must cross P some time, let’s say it crosses with edge passing from x to y. Then algorithm would have selected y before v as all edge lengths are positive, which is a contradiction.

Running Time Analysis:
Total deleteMin – O(nlogn) with Priority Queue, O(n2) without Priority Queue
Total change priorities – O(mlogn) with Priority Queue, O(m) without Priority Queue

Hence total running time = O((n+m)logn) with Priority Queue, O(m+n2) without Priority Queue

Points to remember:

• Uses Adjacency List Representation of Graph
• Much Similar to Prim’s Algorithm
• Requires all edge costs to be non-negative

Okay, now let’s look at a problem where we are not required to find the shorted distances from only one source, but from each node.

All Pairs Shortest Paths Problem Statement:  Given a undirected weighted graph G and, find the shortest cost paths between all pairs.

#### Naive Solution: Run Dijkstra’s algorithm on all nodes. O(mnlogn) = O(n3logn).

Solution 1: Floyd-Warshall Algorithm

TL;DR: Dynamic Programming approach with subproblem as shortest distance between node i and node j using only the first k vertices in between.

Points to remember:

• O(n3) running time
• No negative cost cycles should be present.
• In place implementation possible as the (k+1)th row, and (k+1)th column don’t change in one iteration.

Steps:

• Maintain n 2d arrays D[n][][], such that D[k][i][j] gives the shortest distance between i and j using only the first k vertices in between.
• Final result will be D[n-1]
• Initiate D[-1][i][j] as 0 if i==j, cost of (i,j) if edge exists, infinity otherwise.
• Using dynamic programming, find D[k+1][i][j] = min(D[k][i][j] , D[k+1][i][k+1] + D[k+1][k+1][j]).

Steps for finding the shortest paths:

1. Same kind of implementation, use a matrix N[][][]
2. N[-1][i][j] = j if (i,j) exists, undefined otherwise.
3. N[k+1][i][j] = N[k][i,k+1] if k+1 path is shorter, else N[k][i][j]
4. Now for finding the path between i,j keep following the array N and printing the nodes.

## Basic Problem 3 : Minimum Spanning Trees

Definition: A spanning tree of a graph is a tree that covers all the nodes of the original graph, e.g. BFS/DFS trees. A minimum spanning tree is a spanning tree with the minimum cost.

The MST Lemma (Cut Property): Let P and Q be two disjoint node sets that together give the union of the original graph nodes, then among all the edges between P and Q, the node with minimum edge cost must be present in an MST(there might be more than one MST)

Proof: Let T be an MST that doesn’t contain e{u,v} (the minimum edge cost), then adding e to it will produce a cycle. Traverse along that cycle , and whenever it crosses from P to Q, replace that edge with e. This produces an MST again.

The MST Cycle Lemma (Cycle Property): The costliest edge of a connected undirected graph must not be in an(any if edge costs are distinct in that cycle) MST.

Proof: Let T be an MST that contains the costliest edge e {u,v}. T-e gives two connected disjoint components, traverse along the cycle to get a cheaper edge that can be replaced with e.

Problem Statement: Find a minimum spanning tree for an undirected weighted graph.

Solution 1: Prim’s Algorithm

Point to remember: Nearly direct implementation of the MST lemma.

Steps:

• Start with a set P with some random root node u and a priority queue Q that contains all the remaining nodes of graph with key as infinity.
• Set priority of the nodes that share an edge with u as their edge cost.
• In the priority queue Q maintain a priority of the shortest edge cost from the node to P and the respective closest neighbour
• In a loop keep choosing elements from Q, s.t. d[u] is as small as possible. Add u to P.
• Update the priority of all the nodes in Q w.r.t u. i.e.,  compare their current priority with the edge cost with u and update if the edge cost is lesser.

Running Time Analysis:

• Make heap and other inititalizations – O(n)
• One iteration O(1) in look up and deletion – total of O(nlogn).
• Total iterations of ChangePriority O(m) and each individual costs O(log(n)), hence a total of O(mlogn).

Solution 2: Kruskal’s Algorithm

Points to remember:

• Uses MST lemma.
• Uses MFset( also called Union-Find) Data Structure
• O(mlogn) using MFSet
• Runtime dramatically reduces near to Ackermann Function after using path compression, goes to O(n * ackermann(m)), where ackermann(m)<= 5 for all practical purposes.

Steps:

1. Sort the edges in increasing order of cost.
2. Keep adding edges to MST, and whenever a cycle is formed, just don’t add it.

Running Time Analysis: O(mlogn) in worst case without path compression

Solution 3: Reverse- Delete Algorithm

Point to remember: Uses the cycle MST lemma

Steps:

1. Sort the edges in decreasing order of costs.
2. Keep deleting the costliest edges as long as the tree stays connected

Running Time Analysis: O(n2) with usual implementation.

Notes on MSTs

• All of them are Greedy Solutions
• It turns out that any greedy approach using either of the lemmas will work.

## Interesting Applications

#### Cycle Detection in a Graph: Detect if a directed graph contains a cycle

Points to remember:

• Direct extension of DFS.
• Cycle in a graph only if there is a back edge present in the graph.

Code 🙂

 vector adjList[N]; int visited[N]; bool dfsrecursiveandcycle(int u, int parent) { cout << "visited " << u << endl;// 🙂 visited[u] = 1; bool ans = false; for(int i=0;i

Running Time Analysis:

• Seriously?

Testing Bipartiteness

Bipartite Graph Definition: A graph whose vertices can be divided into two disjoint sets X and Y such that every edge has one end in X and other in Y. Consequently, the sets X and Y are independent sets.

Points to remember:

• Sufficient condition is the non existence of any odd cycles.
• Can use both BFS and DFS to test bipartiteness
• For BFS, check whether there is an odd cycle which can be checked by confirming if there exists an edge between two consecutive layers.
• For DFS, while performing DFS assign colors to the node with negative of parent, hence if you encounter a contradictory case, then not bipartite.

Extending these algorithms For Directed Graphs:

Points to remember:

• BFS and DFS remain the same.
• Strong Connectivity can be checked by running both forward and backward BFS/DFS and comparing the two components if they are the same.
• Strong Components will either be equal or disjoint because if s & u are mutually reachable, s & v are mutually reachable then u & v will also be mutually reachable.

Topological Ordering/Sorting in a Directed Graph:

Topological Ordering of nodes: If every directed edge is forward pointed then the ordering is a topological ordering.

Points to remember:

• A topological ordering of a graph exists iff the graph is a DAG(Directed Acyclic Graph)
• Useful in finding precedence relations
• For every DAG there must be a node with no incoming edges

Algortithms Possible:

• Recursively follow the node with no incoming edges, delete that and then recursively find the next such vertex,
• A variation of DFS, whenever a node is finished searching, add it to front of a linked list. This list will be a DAG. Note to make repeated invocations of DFS as the DFS might stop before traversing to each edge. For more information see this.

Analysis:

• O(n2) running time for raw algorithm1, and O(n+m) for DFS implementation
• To obtain O(m+n) time optimization, use the following technique for Algorithm-1:
• Store two Data Structures:
• for each w, no of active nodes that have incoming edge w.r.t. w.
• the set of all active nodes that have no incoming edges from other active nodes.

So that would be all for this post. BFS, DFS, Dijkstra, Floyd-Warshall, MST, and some interesting applications. The notes are highly influenced from the book by Kleinberg, Tardos and the book by Cormen et.al. . If you are not satisfied have a read in the books, or just post a comment and I can care to explain 🙂 .

Make sure to point out any mistakes or suggestions in the comments.

See you in the next post!

# Object Oriented Programming (OOP) in C++… short descriptions of all you need to know.

This post is highly inspired by and can be considered as some of my class notes for the Software Engineering course (CS20006) at IIT Kharagpur taught by Prof. Partha Pratim Das.

Many of the code illustrations are snapshots of the output along with the code using the application Xcode for Mac OS X. These should be followed thoroughly as these cover extra informations.

Procedural Enhancements over C:

### Pointers vs. References

• Pointers can point to NULL whereas References cannot. There is nothing defined as NULL Reference.
• Pointers can point to different variables at different times whereas for a reference, its referent is fixed.
• References make code faster since, unlike pointers, checks for NULL are not required.
• Reference “refers” to an address but does not store that address. Pointer does.
• Can not have an array of references, not allowed.
• You should never return by reference a local variable

### MACROS and Inline Functions:

• C Pre-Processor (CPP) macros are replaced textually before compilation, in turn:
• Size increases
• Speed increases
• Perfect for small code reuse
• Some expressions might turn out to be unexpected and in some cases compiler dependent.
• Scope of the variables confined to where it’s being implemented (Can be both useful and harmful)
• Inline Functions
• Act as functions, implemented as macros
• Type Checking is still performed.
• May take more space
• Implemented by using inline keyword
• are to be defined in .h files not .c/.cxx files preferably..
• Inline Functions are not always implemented inline, this is decided by the compiler based on the performance. See here for good answers.

### Default Function Arguments:

• Same function name can be used by different kind of definitions.
• Function selection based on number and types of the actual parameters at the places of invocation.
• Function selection (Overload Resolution) is performed by the compiler in the following order:
• Exact Match
• Promotion
• Standard Type Conversion (like function-to-pointer and array-to-pointer)
• User Defined Type Conversion
• Two functions having the same signature but different return types will result in a compilation error due to “attempt to re- declare”.
• Allows static polymorphism …

### New-Delete Operators:

• new Operator when called can be considered as performing these two operations:
• Allocates memory in Free Store
• Calls the constructor (discussed later)
• delete Operator when called can be considered as performing these two operations:
• Calls the Destructor
• Frees up the memory in Free Store

# Classes in C++:

### What is a Class?:

• C++ Class is an implementation of “type”
• In C++, class is the only way to implement user defined data types.
• An object (any variable of that type, also called an instance) is an aggregate(encapsulation) of data items(member variables) and methods(member functions) that can work with them.
• A Class is a layout of it’s objects.

### How to code them?

• A Class is defined by “class” keyword.
• Each member in a class has an access specifier.
• public: These members are accessible everywhere.
• private: These members are accessible inside the definition of the class
• protected: These are accessible only to it’s class definition and it’s subclass definitions.

### “this” pointer:

• follows the type – X * const , where X is the class name as the pointer address can not be changed.
• Necessity of this to the programmer:
• Distinguishing data member from non-member variable
• Explicit Use
• Member functions implicitly take this pointer as an argument.

### Constructor Functions:

• are member functions with the same name as the class
• are automatically called when an object is created, just after memory allocation.
• allow the class to initialise the state of an object
• Constructors also allocate additional memory space from the Free store (if) required for the object.
• must not have any return type , not even void.
• If users do not define any constructor then the compiler provides a default constructor.
• Default constructors are those constructors which either do not have an argument or have default arguments (ints to 0, pointers to NULL) for all parameters.  can be directly called to create anonymous objects.
• X a; invalid if no default constructor (if user defined constructor is not a default kind)
• Initializer Lists:
• Initializer lists appear as a comma separated list
• Initializer lists are required for a member object that must be passed initial arguments for construction
• Initializer lists are required for const members and reference members
• local static specifier:
• created first time you cross them
• destructed in terms of global variables
• However, scope is lexically restricted, as usual, by braces.

### Destructor Functions:

• are member functions with the name “~<class-name>
• is automatically called when an object is destroyed, just before memory is freed.
• For auto variables when the variable goes out of scope
• For objects created in the Free store, destructor is called after “delete” or “delete[]” is explicitly invoked by the programmer.
• must not have any argument
• must not have any return value
• If destructor is not called then there could be memory leaks for objects which calls “new” in the constructor.
• Also a free function (provided by default if needed)
• Provides an Automatic Life Time
• If destructor is private, or not provided by any other way… then creation of an object is a compile error.

### Copy Constructor Functions:

• Copy constructor is a special constructor which is used to initialize an object with another object of the same type.
• Functions call it for both arguments and return.
• Needs to take a reference as its argument because if not taken as reference, an infinite loop occurs as C++ itself calls the copy constructor for argument values.

### Object Layout w.r.t. memory:

• Simplistically, an object of a class must have enough space to store all members of that class.
• No space is required per object for storing function pointers for the methods declared in the class.
• Class members can also be objects.
• All objects get allocated a contiguous chunk of memory
• Arrays of Objects:
• `String arrayOfString[100]; // 100 objects created using the default constructor`
• `String arrayOfString[2] = { String(“abc”), String(“def”) }; // Using specialized constructor while creating an array of objects.`
• `String *pArrayOfString[2] = { new String(“abc”), new String(“def”) };//Using different constructor for creating array objects dynamically.`

### Const Member Functions:

• Constant Member Functions are not allowed to change the state of the object on which they are invoked.
• Type of this pointer passed to a const function is thence const X* const this
• Const Functions are declared with keyword const following member function parameter list.
• const must also be present at the definition.
• for escaping const member functions’ const-ness you can use mutable keyword

### Friends and Static Data:

• Friend Functions
• are to be declared in one or more classes
• behave like global functions and can’t be called on an object(no this pointer), they behave like global functions.
• are distinguished from members with the keyword friend
• Member of a different class may be a friend function. (e.g. friend Vector Vector::prod(Matrix *pM);)
• A class may be declared as a friend implying all member functions of that class are friends.
• Friend-ship is neither commutative nor transitive.
• It is best to avoid friend in an ideal OO Design.
• Can be used for operators in which both ways needed  (like  int+Fraction, and Fraction+int)
• Static Data Members
• A static data member is shared by all the objects of a class.
• Static data member may be public or private.
• Static data member must be initialized in a source file.
• It can be accessed
• with the class-name followed by the scope resolution operator “::”
• as a member of any object of the class
• Static Member functions:
• May be invoked with the class-name::
• May be invoked  as part of any objects interface
• this pointer is not passed to a static function
• must not refer to non-static members of its “invoking object”
• Features like Singleton Class (only one instance possible) can be implemented using static variables. {Make constructor private and store a static instance pointer, which will be returned by some method getInst() only if instance is not there

### Points to remember:

• An operator is a symbol that tells the compiler to perform specific mathematical or logical manipulations.
• can be postfix or infix for unary
• “a+b” calls either a.operator+(b) or operator+(a,b)
• These functions can either be implemented as global friend functions and/or methods.
• Overloaded operator function must not change the arity of already present operator
• precedence and associativity should not change
• Fraction& operator–(); for infix… no argument for unary operator
• Fraction operator–(int); for postfix
• Some operators can’t be overloaded, e.g. ::,.*.?:,., sizeof() etc.
• Conditional Operators like &&, ||, comma operator should not be overloaded.
• Member operators will not help if the left hand side of the operator is not of the class type…. for this reason stream operators must be friend
• Returning const from a function ensures that you can’t use operations like (a*b)=c
• Returning const ensures that overloaded “*” is compatible with the same operator on built-in types.

### Assignment Operator:

• Poly& operator=(const Poly&);
• Poly returned because it makes chain assignment possible
• Some cases in which you need to free some data before copying new data, make sure that self assignment can also take place
• Reference returned to allow (a=b)=c, kind of statements… also some operators are left associative, in that case return must be by reference… e.g. (next point)
• System defined assignment operator function makes a shallow copy.
• If there is a need to define a copy constructor then there must be a need to overload assignment operator and vice-versa.

# Inheritance

What is inheritance: We say that a class(also called the subclass or derived class) inherits another class( also called the super class or base class) if the sub class has all the data attributes of the super class. C++ provides a special syntax with which use this special relation. When we use inheritance , all data members and methods of the base class are immediately available to the derived class. The derived class, however, may extend the state and behavior of the base class by adding more attributes and methods.

• Reusability, reuses an already existing code
• Reduces cost & development time.
• Improves quality.
• In C, we had to reuse a code using a library function… which can not be customised
• In C++, we have features like inheritance and composition(code reuse by containing other classes
• Extensibility
• Data hiding, base class can decide to keep some data private so that it cannot be altered by the derived class
• Overriding

### Behaviour of Access Specifiers for members:

• public: public for derived classes.
• private: private for derived classes, can not be used by derived class members.
• protected: private for derived classes, but can be used by them.

### Accessibility based on type of inheritance:

• public: Mostly needed… and mostly used.
• private members of the base class become private members of the derived class, but can not be accessed by the derived class members!
• However, the private members of the base class will still be accessible by the methods inherited from the base class.
• public members of the base class become public members of the derived class
• private: All members of base class behave as private to the derived.
• protected: public and protected members become protected, and private members stay private.
 Public inheritance Base access specifier Derived access specifier Derived class access? Public access? Public Public Yes Yes Private Private No No Protected Protected Yes No
 Private inheritance Base access specifier Derived access specifier Derived class access? Public access? Public Private Yes No Private Private No No Protected Private Yes No
 Protected inheritance Base access specifier Derived access specifier Derived class access? Public access? Public Protected Yes No Private Private No No Protected Protected Yes No

### Order of Constructor/Destructor Calls:

• Constructor
• Base then Derived, as derived object members contain members of the base class.
• Destructor
• Derived then Base.

### Casting: A pointer of a class can be cast to it’s derived or super class pointer.

• Upcasting – Casting derived into a base class pointer
• Downcasting – Casting base into a derived class pointer.. CAN BE DANGEROUS
• Only base class part of the derived object can be seen through the base pointer.
• Hence overridden functions will also not be called by a static cast.
• Virtual Functions:
• In C++, dynamic binding is made possible only for pointer & reference data types and for methods that are declared as virtual in the base class.
• Virtual functions are called through the VFT function pointer array
• pointer to the array is stored in each object, as shown below.
• Once a function is made virtual it will automatically be virtual in it’s derived classes, as the derived class inherits. Due to this, if there is no overridden function for that virtual function, the pointer to the virtual function of the base class will be stored in the VFT of derived class.
• When a virtual function is called, the only information the compiler has is the VFT of the class in which it has been cast, hence the according index will be present in the compiled code, which in execution time will point to the VFT of the actual object.
• Any class which has even one virtual function, a VFT will be created for that, and is called a Polymorphic Class.

• Pure Virtual Functions… is a special syntax specified in C++ with which you can specify that you don’t have any definition for that member function, and hence don’t allow the construction of an object of the classes in which it is present.

### Type Casting:

• used to convert the type of an object, expression, function argument, or return value to that of another type
• (Silent) Implicit conversions and Explicit conversions.
• To perform a type cast, the compiler:
• allocates temporary storage
• Initializes temporary with value being cast
• Automatic Conversions:
• The standard C++ conversions and user-defined conversions
• Can be very handy,
• And can also be unsafe at times
• Overuse of user defined casting may lead to ambiguities
• User defined casting can be obtained by either making a constructor of type A(B &) or operator A () in class B.

Alright, Alright, Alright! That would be all for this post. Remember that there is no better method for understanding a language than to code in it. Any mistakes or suggestions should be posted in the comments. Thanks for reading!