Implicit Graph

Implicit Graphs:

Some graphs don't need to be stored or explicitly generated for the graph to be traversed or operated upon. Such graphs are called as Implicit graphs.

Implicit graphs come in two flavors:

1. The edges can be determined easily: Example: The graph of chess knight movements on an 8*8 chessboard. The vertices are the cells in the chessboard. Two squares are connected if they differ by two squares horizontally and one vertically( or the other way round).
2. The edges can be determined with some rules: Example: A graph contains N vertices. There is an edge between two vertices i and j if (i+j) is a prime.

Graphs Data Structures

Graphs

The graph is one of the most important data structures in computer science.

Definition:

A graph (defined as $G=(V, E)$)is simply a set of vertices(V) and edges(E; storing the connectivity information between vertices in V).

We will now discuss the three basic ways to represent a graph G with vertices V and edges E.

Adjacency Matrix:

If the number of vertices is known, we can build a connectivity table as a static 2d array: 

                                                                         \[arr[V][V]\] This will have $O(V^2)$ space complexity. For an unweighted graph. set arr[i][j] to one if there is an edge between vertex i-j or zero otherwise.

For a weighted graph, set it to the weight of the edge if there is an edge else zero in case there is no edge.

For a simple graph without self-loops, the main diagonal of the matrix contains only zeros.

An adjacency Matrix is a good choice if the connectivity between two vertices in a small dense graph is frequently required.

For a large sparse graph, not a good choice. It takes O(V) time to enumerate the list of neighbors of a vertex v. You would have to scan the complete row/column corresponding to that vertex.

Adjacency List:

In the adjacency list, we have a vector of vector of pairs. Defined as vector<vector<pair<int, int> > >.

It stores the list of neighbors of each vertex u as edge information pairs. Each pair contains two pieces of information, the index of the neighboring vertex and the weight of the edge.

The space complexity of the Adjacency List is O(V+E). As E is usually much smaller than $V^2$ adjacency list are much more space-efficient than Adjacency Matrix.

With Adjacency Lists, enumeration the list of neighbors of a vertex v. If v has k neighbors it will only require O(k) time.

This is suggested the first choice of graph representation.

The Edge List: 

Is usually in the form of a vector of triples vector< pair<int, pair<int, int> >.

In the edge list, we store a list of all E edges usually in some sorted order. For directed graphs, we can store a bi-directional edge twice, one for each direction.

The space complexity is O(E). Storing graph information in Edge List complicates many graph algorithms that require enumeration of edges incident to a vertex.

Problems based on Maps

Problems:

Here is the list of problems you can do to practice maps:

• UVa 00417 - Word Index
• UVa 00484 - The Department of ... 
• UVa 00860 - Entropy Text Analyzer
• UVa 00939 - Genes
• UVa 10132 - File Fragmentation
• 6. UVa 10138 - CDVII 
• 7. UVa 10226 - Hardwood Species * 
• 8. UVa 10282 - Babelfish
• 9. UVa 10295 - Hay Points
• 10. UVa 10686 - SQF Problem
• 11. UVa 11239 - Open Source 
• 12. UVa 11286 - Conformity *
• 13. UVa 11308 - Bankrupt Baker
• 14. UVa 11348 - Exhibition
• 15. UVa 11572 - Unique Snowflakes * 
• 16. UVa 11629 - Ballot evaluation
• 17. UVa 11860 - Document Analyzer
• 18. UVa 11917 - Do Your Own Homework
• 19. UVa 12504 - Updating a Dictionary
• 20. UVa 12592 - Slogan Learning of Princess

Here is the link to the questions on Uva: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=631

Here are my solutions and hints for a few of them.

Solutions and hints

Uva 10226: Harwood Species

Simple use of maps.

                                  

#include <bits/stdc++.h>
	using namespace std;
	#define MAXINT abs(~(int)0)
	#define MININT ~(int)0
	int main(int argc, char const *argv[]) {
	int T;
	scanf("%d", &T);
	int i=1;
	getchar();
	getchar();
	while (T--) {
	map<string, float> trees;
	string s;
	int numberofTrees = 0;
	while (getline(cin, s) && s!="") {
	if(trees.find(s)!=trees.end()){
	trees[s] +=1;
	}else{
	trees[s] = 1;
	}
	numberofTrees++;
	}
	if(i>1)
	printf("\n");
	for (map<string, float>::iterator t =trees.begin();t != trees.end(); t++) {
	cout<<t->first;
	printf(" %.4f\n", (t->second/numberofTrees)*100);
	}
	i++;
	}
	return 0;
	}

Uva 10282: BabelFish

Simple, simple usage of maps.

int main(int argc, char const *argv[]) {
	string line, a, b;
	std::map<string, string> dictionary;
	while (getline(cin, line)&&line!="") {
	istringstream sin(line);
	sin>>a>>b;
	dictionary[b]=a;
	}
	while (cin>>a) {
	map<string, string>::iterator it = dictionary.find(a);
	if(it==dictionary.end()){
	cout<<"eh"<<endl;
	}else{
	cout<<it->second<<endl;
	}
	}
	return 0;
	}

Uva 484: The department of redundancy department

Use map to maintain frequency, and one other container to store the data headings.

int main(int argc, char const *argv[]) {
	int ar;
	map<int, int> map;
	std::vector<int> v;
	while (scanf("%d", &ar)!=EOF) {
	if(map.find(ar)!=map.end()){
	map[ar] +=1;
	}
	else{
	map[ar] = 1;
	v.push_back(ar);
	}
	}
	for(vector<int>::iterator it=v.begin(); it!=v.end();it++){
	cout<<*it<<" "<<map[*it]<<'\n';
	}
	return 0;
	}

Uva 11286: Conformity

input the course as five integers, sort them, convert each to string and create a single string with them. Use this string as a key in your maps.

int main(int argc, char const *argv[]) {
	int n;
	while (scanf("%d", &n), n!=0) {
	map<string, int> courses;
	int max = 0;
	int counter=0;
	while (n--) {
	int arr[5];
	scanf("%d %d %d %d %d\n", &arr[0], &arr[1], &arr[2], &arr[3], &arr[4]);
	sort(arr, arr+5);
	string str = to_string(arr[0])+ to_string(arr[1])+ to_string(arr[2])+ to_string(arr[3])+ to_string(arr[4]);
	if(courses.find(str)!=courses.end()){
	courses[str] +=1;
	}else{
	courses[str] = 1;
	}
	}
	for(auto it=courses.begin();it!=courses.end();it++){
	if(it->second > max){
	max = it->second;
	counter=max;
	continue;
	}
	if(it->second==max){
	counter+=it->second;
	}
	}
	cout<<counter<<endl;
	}
	return 0;
	}

Uva Hay Points: 10295

Simple

int main(int argc, char const *argv[]) {
	int m, n;
	scanf("%d %d", &m, &n);
	map<string, int> map;
	string s;
	int dollar;
	while (m--) {
	cin>>s;
	scanf("%d", &dollar);
	map[s]= dollar;
	}
	while (n--) {
	int sum=0;
	string s;
	while (cin>>s) {
	if(s==".")
	break;
	if(map.find(s)!=map.end()){
	sum += map[s];
	}
	}
	cout<<sum<<endl;
	}
	return 0;
	}

Uva word-index 417

Use recursion to create the array up to vwxyz, than the problem is simple.

char arr[26];
	vector<string> v;
	bool comp(string a, string b){
	if(a.length()!=b.length())
	return a.length()<b.length();
	return a<b;
	}
	void generate(int counter, int start, string s){
	if(counter==5 || start==26){
	if(s!="")
	v.push_back(s);
	return;
	}
	generate(counter, start+1, s);
	generate(counter+1, start+1, s+arr[start]);
	}
	int main(int argc, char const *argv[]) {
	////generating the arr first;
	map<string, int> map;
	for(int i=0; i<26;i++){
	arr[i]=i+'a';
	}
	string s="";
	generate(0, 0, s);
	sort(v.begin(), v.end(), comp);
	int i=1;
	for(auto it=v.begin();it!=v.end();it++,i++){
	map[*it] = i;
	}
	/////////this completes the preperation for the map
	string t;
	while(getline(cin, t)&&t!=""){
	if(map.find(t)!=map.end())
	cout<<map[t]<<endl;
	else
	cout<<0<<endl;
	}
	return 0;
	}