Introduction Nikita Agarwal

GraphX Library is a aimed to build a comprehensive C++ Library which allows you to solve graph based problems out of the box. It handles various complexities and enables you to solve problems in nearly all kinds!

Solving graph problems becomes very🗲fast since learning to use this library has an easy learning curve.

Note

The library was originally built to support classes taken by Manas sir, but you can ofcourse use it for your purposes like solving problems at Codeforces, Codechef, Leetcode, etc at your own risk.

Illustration of how GraphX abstracts algorithms/code and lets you focus on just building Graph!

GraphX Library Code

You can directly copy paste following code above main function in your C++ code. Link: GraphX Library

Features

✔️ Supports 1D, 2D, 3D Graphs	✔️ Algorithms as blackbox (BFS, Dijkstra, etc)
✔️ Weighted/Unweighted Graphs	✔️ Directed/Undirected Graphs
✔️ Handling Grid Graphs	✔️ Integrated Graph Visualizer (WIP)
✔️ Advanced Graph Layering & Modelling support	✔️ Above all, an easy learning curve!

Design Philosphy

GraphX library has been designed keeping ease of learning as topmost priority. As a result, we have modelled a role division between what should Library do (Abstract out algorithms, tedious implementations, effeciency, memory management) and what should library-user (which is to just focus on building graphs using nodes & edges). This not only makes the library very easy to use but also provides great clarity and speed to programmer using the library.

Next priority has been given to depth coverage of what you can do with the library: can it handle grids? does it seamlessly supports graph modelling or 2D/3D versions of nodes? etc. After this preference has been given to speed of execution of library itself and to low level design of library itself. In upcoming v2, v3 releases we intend to make it even faster and improved LLD.

Key Takeaway

Its important to keep in mind how the library intends to provide wings to user, clear distinction between:-

Responsibility of Library: Abstract out algorithms, tedious implementations, effeciency, memory management
Responsibility of Programmer: which is to just focus on building graphs using nodes & edges

How to use this Documentation?

You should be independently be able to navigate and read each section in isolation. Below is however guide to help you effeciently use this Documentation:-

Steps to use this Documentation effeciently:

1. Design Philosphy	You should definitely start by reading Key Takeaways section in Design Philosphy
2. Pre-Requisite	Optional if you aren't comforatable with vectors or classes in C++ then read, else skip
3. Functions	Read building-Graph BFS section in that order, it will teach you how to use this library
4. Solve Problems	Read Shortest-Path Shortest-path-in-grid sections to learn how to apply library end-to-end

Pre-requisites

There are essentially two topics you should be clear with: Vectors & Classes in C++.
Even if you don't know them, it will take hardly 10 minutes with minimilistic introduction below ( :

Vectors in C++

Simplified Understanding

A vector is, essentially, a resizable array.

Minimal list of functions you should remember to leverage power of vectors:-

Declaring 1D vector	`vector< int > SampleVector; //declares an empty vector {}` `vector< int > SampleVector1(100); //declares a vector that has 100 integers {0, 0, ... 0}` `vector< int > SampleVector2(100, 7); //declares a vector that has 100 integers {7, 7, ... 7}`
Declaring 2D vector	`vector< vector< int >> SampleVec; //declares an empty 2D vector {{}}` `vector< vector< int >> SampleVec1(2, vector< int > (3)); //2D vector {{0, 0}, {0, 0}, {0, 0}}` `vector< vector< int >> SampleVec2(2, vector< int > (3, 7)); //2D vector {{7, 7}, {7, 7}, {7, 7}}`
push_back()	`SampleVector2.push_back(33); //Now it has 101 integers {7, 7, ... 7, 33}`
size()	`cout << SampleVector2.size(); //Prints size of vector which is '101' currently`
clear()	`SampleVector2.clear(); //Makes the vector empty {}`

Classes in C++

You should be clear about difference between class & objects.

Class is defination of a custom data-type. Thus it doesn't actually stores data (Its merely a defination!).

Whereas, once a class is declared if you use that defination to store data, you do so by creating object of that class.

Example: multiple cars could have common properties like speed, weight, etc. So we can define a class that describes these common properties (defination), and then for each different car we can create object out of this class (defination) and fill respective details.

Library Usage

There are three classes: Graph, BFS, Dijkstra. You first create object of Graph and build graph, then you can pass it to object of BFS or Dijkstra to find corresponding shortest distances.

Creating Graph


                Graph G(50); //Creates graph with 50 nodes
                G.add_edge(1, 2);
                G.add_edge(1, 3);
                G.add_edge(3, 1); //creates directed graph 2 <-- 1 <--> 3

                //Advanced: you can also add edges between 2D/3D nodes
                //This is useful for grids and graph layering
                G.add_edge({1, 2}, {3, 5}); //adds edge between two nodes (1,2) and (3,5)
                G.add_edge({1, 3, 2}, {5, 6, 3});

Breadth First Search


                Graph G(50);
                G.add_edge(1, 2);
                G.add_edge(2, 3);
                G.add_edge(3, 4);

                BFS bfs(&G); //create BFS object and supply graph G to it by reference
                bfs.run(1); // Run bfs on graph G from source node as 1
                if (bfs.is_visited(4)) //if after bfs from source node 1, node-4 is reachable?
                  cout << bfs.min_dist(4); //if yes, then print shortest distance to node-4 from node-1

Solved Problems

Minimum Jumps

Problem Statement: Minimum Jumps

Solution Link: Solution


                #include < bits/stdc++.h >
using namespace std;


//COPY THE BLACKBOX, there is no need to change anything in it.
//Check the main function at bottom for USAGE

//****************BLACKBOX START*****************
//START COPYING FROM HERE

typedef int ll;

class Hash {
  public:
  	static int hash(int x){
  		return hash({0,0,x});
  	}
  	static int hash(tuplex){
  		return hash({0,get<0>(x),get<1>(x)});
  	}
  	static int hash(tuplex){
  		int k=get<0>(x),u=get<1>(x),v=get<2>(x);
  		return k*1873*1873 + u*1873 + v;
  	}
};

class Graph {

	bool is_directed;

	public:
		vector>>adj;
    int n,N=2000000;

		Graph(int n_, bool is_directed_){
			n=n_; is_directed = is_directed_;
			adj.resize(N,vector>());
		}

		int hash(int u, int v){
			return Hash::hash({u,v});
		}
		int hash(int u, int v, int k){
			return Hash::hash({u,v,k});
		}

		void add_edge(int uR, int vR, ll c=0){
		  int u=Hash::hash(uR), v=Hash::hash(vR);
		  add_edge_internal(u,v,c);
		}
		void add_edge(tuple uR, tuple vR, ll c=0){
		  int u=Hash::hash(uR), v=Hash::hash(vR);
		  add_edge_internal(u,v,c);
		}
			void add_edge(tuple uR, tuple vR, ll c=0){
		  int u=Hash::hash(uR), v=Hash::hash(vR);
		  add_edge_internal(u,v,c);
		}


	private :

	  void add_edge_internal(int u, int v, ll c=0){
			add_edge_weighted_undirected(u,v,c);
			if(!is_directed)
				add_edge_weighted_undirected(v,u,c);
		}
		void add_edge_weighted_undirected(int u, int v, ll c) {
			pairp = make_pair(v,c);
			adj[u].push_back(p);
		}

};

class BFS {
    vectormin_dist_from_source;
    vector visited;
    Graph *g;

    public:
      BFS(Graph *g_) {
          g = g_;
          clear();
      }

	  	void clear() {
  			min_dist_from_source.clear();
  			min_dist_from_source.resize(g->N,-1);
  			visited.clear();
  			visited.resize(g->N, false);
  		}


      void run(int sourceR) {
        int source = Hash::hash(sourceR);
        run_internal(source);
      }
      void run(tuple sourceR) {
        int source = Hash::hash(sourceR);
        run_internal(source);
      }
      void run(tuple sourceR) {
        int source = Hash::hash(sourceR);
        run_internal(source);
      }


      int min_dist(int targetR){
      	int target = Hash::hash(targetR);
      	return min_dist_internal(target);
      }
      int min_dist(tuple targetR){
      	int target = Hash::hash(targetR);
      	return min_dist_internal(target);
      }
      int min_dist(tuple targetR){
      	int target = Hash::hash(targetR);
      	return min_dist_internal(target);
      }

      bool is_visited(int targetR){
      	int target = Hash::hash(targetR);
      	return is_visited_internal(target);
      }
      bool is_visited(tuple targetR){
      	int target = Hash::hash(targetR);
      	return is_visited_internal(target);
      }
      bool is_visited(tuple targetR){
      	int target = Hash::hash(targetR);
      	return is_visited_internal(target);
      }

  private:
    void run_internal(int source) {
			queue q;
			q.push(source);

			visited[source] = true;
			min_dist_from_source[source] = 0;

			while(!q.empty()) {
				int cur_node = q.front();
				for (unsigned int i = 0; i < (g->adj[cur_node]).size(); ++i) {
					int adj_node =  (g->adj[cur_node])[i].first;
					if (visited[adj_node] == false) {
						visited[adj_node] = true;
						min_dist_from_source[adj_node] = min_dist_from_source[cur_node] + 1;
						q.push(adj_node);
					}
				}
				q.pop();
			}

			return;
    }

    int min_dist_internal(int target){
    	return min_dist_from_source[target];
    }

    bool is_visited_internal(int target){
    	return visited[target];
    }

};
//END COPYING HERE
//********************BLACKBOX END******************

int main() {
  int n,m; cin>>n>>m;

  Graph g(n,false); //false here denote we are declaring an undirected graph

  int x,y;
  for(int i=0;i>x>>y;
    g.add_edge(x,y);
  }

  cin>>x>>y;

  BFS bfs(&g);
  bfs.run(x);

  if(bfs.is_visited(y))
    cout<

Number of Rooms

Problem Statement: Number of Rooms

Solution Link: Solution


                #include < bits/stdc++.h >
                using namespace std;


                //COPY THE BLACKBOX, there is no need to change anything in it.
                //Check the main function at bottom for USAGE

                //****************BLACKBOX START*****************
                //START COPYING FROM HERE

                typedef int ll;

                class Hash {
                  public:
                  	static int hash(int x){
                  		return hash({0,0,x});
                  	}
                  	static int hash(tuplex){
                  		return hash({0,get<0>(x),get<1>(x)});
                  	}
                  	static int hash(tuplex){
                  		int k=get<0>(x),u=get<1>(x),v=get<2>(x);
                  		return k*1873*1873 + u*1873 + v;
                  	}
                };

                class Graph {

                	bool is_directed;

                	public:
                		vector>>adj;
                    int n,N=2000000;

                		Graph(int n_, bool is_directed_){
                			n=n_; is_directed = is_directed_;
                			adj.resize(N,vector>());
                		}

                		int hash(int u, int v){
                			return Hash::hash({u,v});
                		}
                		int hash(int u, int v, int k){
                			return Hash::hash({u,v,k});
                		}

                		void add_edge(int uR, int vR, ll c=0){
                		  int u=Hash::hash(uR), v=Hash::hash(vR);
                		  add_edge_internal(u,v,c);
                		}
                		void add_edge(tuple uR, tuple vR, ll c=0){
                		  int u=Hash::hash(uR), v=Hash::hash(vR);
                		  add_edge_internal(u,v,c);
                		}
                			void add_edge(tuple uR, tuple vR, ll c=0){
                		  int u=Hash::hash(uR), v=Hash::hash(vR);
                		  add_edge_internal(u,v,c);
                		}


                	private :

                	  void add_edge_internal(int u, int v, ll c=0){
                			add_edge_weighted_undirected(u,v,c);
                			if(!is_directed)
                				add_edge_weighted_undirected(v,u,c);
                		}
                		void add_edge_weighted_undirected(int u, int v, ll c) {
                			pairp = make_pair(v,c);
                			adj[u].push_back(p);
                		}

                };

                class BFS {
                    vectormin_dist_from_source;
                    vector visited;
                    Graph *g;

                    public:
                      BFS(Graph *g_) {
                          g = g_;
                          clear();
                      }

                	  	void clear() {
                  			min_dist_from_source.clear();
                  			min_dist_from_source.resize(g->N,-1);
                  			visited.clear();
                  			visited.resize(g->N, false);
                  		}


                      void run(int sourceR) {
                        int source = Hash::hash(sourceR);
                        run_internal(source);
                      }
                      void run(tuple sourceR) {
                        int source = Hash::hash(sourceR);
                        run_internal(source);
                      }
                      void run(tuple sourceR) {
                        int source = Hash::hash(sourceR);
                        run_internal(source);
                      }


                      int min_dist(int targetR){
                      	int target = Hash::hash(targetR);
                      	return min_dist_internal(target);
                      }
                      int min_dist(tuple targetR){
                      	int target = Hash::hash(targetR);
                      	return min_dist_internal(target);
                      }
                      int min_dist(tuple targetR){
                      	int target = Hash::hash(targetR);
                      	return min_dist_internal(target);
                      }

                      bool is_visited(int targetR){
                      	int target = Hash::hash(targetR);
                      	return is_visited_internal(target);
                      }
                      bool is_visited(tuple targetR){
                      	int target = Hash::hash(targetR);
                      	return is_visited_internal(target);
                      }
                      bool is_visited(tuple targetR){
                      	int target = Hash::hash(targetR);
                      	return is_visited_internal(target);
                      }

                  private:
                    void run_internal(int source) {
                			queue q;
                			q.push(source);

                			visited[source] = true;
                			min_dist_from_source[source] = 0;

                			while(!q.empty()) {
                				int cur_node = q.front();
                				for (unsigned int i = 0; i < (g->adj[cur_node]).size(); ++i) {
                					int adj_node =  (g->adj[cur_node])[i].first;
                					if (visited[adj_node] == false) {
                						visited[adj_node] = true;
                						min_dist_from_source[adj_node] = min_dist_from_source[cur_node] + 1;
                						q.push(adj_node);
                					}
                				}
                				q.pop();
                			}

                			return;
                    }

                    int min_dist_internal(int target){
                    	return min_dist_from_source[target];
                    }

                    bool is_visited_internal(int target){
                    	return visited[target];
                    }

                };
                //END COPYING HERE
                //********************BLACKBOX END******************

                int main() {

                    int n,m; cin>>n>>m;

                    //initialise graph with `n*m` nodes, each cell is a node
                    Graph g(n*m,true);

                	//intiatialise a 2D array of size `n*m
                    vector>grid(n,vector(m));

                    for(int i=0;i>grid[i][j];

                      }


                   //************GRAPH CONTRUCTION BEGIN*****************

                   //iterate through every cell
                    for(int i=0;i cell above`
                          if(i-1>=0 && grid[i-1][j]=='.')
                            g.add_edge({i,j},{i-1,j});

                        // if cell below is withing the grid and a floor, create an Edge from `current cell -> cell below`
                          if(i+1 cell left`
                		  if(j-1>=0 && grid[i][j-1]=='.')
                            g.add_edge({i,j},{i,j-1});

                         // if cell right is withing the grid and a floor, create an Edge from `current cell -> cell right`
                          if(j+1