1 Replies - 1261 Views - Last Post: 05 January 2017 - 07:31 AM Rate Topic: -----

#1 homeworkhelp4u  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 05-January 17

C++ Graph Code.

Posted 05 January 2017 - 02:51 AM

"Expert" wrote this code for my client. Assignment was to write a program
that draws praph using ASCII graphics.
Amazing but it's works properly.
#include<iostream>
#include<stdio.h>
#include<cstdlib>
#include<math.h>
#include<algorithm>
#include<fstream>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include <iomanip> 

#define pi 3.1415926535
#define mod9 %1000000009
#define mod7 %1000000007
#define INF 1000000000

#define LL long long
using namespace std;
const int N = 100001;
string s;


vector< vector<pair<int, int> > > in, out;

void  get_input(string s) {
	vector<int> line;
	int number = 0;
	for (int i = 0; i<s.length(); i++) {
		if (s[i] == ' ')
			line.push_back(number), number = 0;
		else
		if (s[i] >= '0' && s[i] <= '9') number = number * 10 + s[i] - '0';
	}
	line.push_back(number);
	int v = line[0];
	for (int i = 1; i < line.size(); i += 2) {
		out[v].push_back(make_pair(line[i], line[i + 1]));
		in[line[i]].push_back(make_pair(v, line[i + 1]));
	}
}

vector<int> nodes;
int n, m, distx = 2, disty = 2;

int len(int x){
	int cnt = 0;
	while (x != 0) {
		cnt++;
		x /= 10;
	}
	return cnt;
}

string abc(int x) {
	string out;
	while (x != 0) {
		out += char('0' + x % 10);
		x /= 10;
	}
	reverse(out.begin(), out.end());
	return out;
}

char board[1001][1001];
vector<int> used;
int lsz, usz, dsz, rsz;
pair<int, int> bolo[1001][1001], tavi[1001][1001];
int dist[1001][1001];

void place(int status, int from, int to, int val, int x, int l, int r) {
	int con = 0;
	if (!used[0]) {
		if (status) board[x][l - 1] = '>', board[x][l - 2] = '-', con = 1; else
			board[x][l - 1] = '-';
		string c = abc(val);
		if (status) { for (int i = l - 2; i >= l - c.length() - 1; i--)board[x][i - con] = '-'; }
		else {
			for (int i = l - 2; i >= l - c.length() - 1; i--)
				board[x][i - con] = c[i - l + c.length() + 1];
		}
		board[x][l - c.length() - 2 - con] = '-';
		lsz = l - c.length() - 2 - con;
		board[x][l - c.length() - 3 - con] = '+';
		if (status) {
			bolo[to][from] = make_pair(x, l - c.length() - 3 - con);
			dist[to][from] += c.length() + 3 + con;
		}
		else {
			tavi[from][to] = make_pair(x, l - c.length() - 3 - con);
			dist[from][to] += c.length() + 3 + con;
		}
		used[0] = 1;
		return;
	}
	if (!used[1]) {
		if (status) board[x][r + 1] = '<', con = 1, board[x][r + 2] = '-'; else
			board[x][r + 1 + con] = '-';
		string c = abc(val);
		if (status) {
			for (int i = r + 2; i <= r + c.length() + 1; i++)
				board[x][i + con] = '-';
		}
		else {
			for (int i = r + 2; i <= r + c.length() + 1; i++)
				board[x][i + con] = c[i - r - 2];
		}
		board[x][r + c.length() + 2 + con] = '-';
		rsz = r + c.length() + 2 + con;
		board[x][r + c.length() + 3 + con] = '+';
		if (status) {
			bolo[to][from] = make_pair(x, r + c.length() + 3 + con);
			dist[to][from] += c.length() + 3 + con;
		}
		else {
			tavi[from][to] = make_pair(x, r + c.length() + 3 + con);
			dist[from][to] += c.length() + 3 + con;
		}

		used[1] = 1;
		return;
	}
	if (!used[2]) {
		if (status) board[x - 1][(l + r) / 2] = 'V', board[x - 2][(l + r) / 2] = '|', con = 1; else
			board[x - 1 - con][(l + r) / 2] = '|';
		string c = abc(val);
		if (status) {
			board[x - 2 - con][(l + r) / 2] = '|';
		}
		else {
			for (int i = 0; i < c.length(); i++)
				board[x - 2 - con][(l + r) / 2 - c.length() / 2 + i] = c[i];
		}
		board[x - 3 - con][(l + r) / 2] = '|';
		usz = x - 3 - con;
		board[x - 4 - con][(l + r) / 2] = '+';
		if (status) {
			bolo[to][from] = make_pair(x - 4 - con, (l + r) / 2);
			dist[to][from] += 4 + con;
		}
		else {
			tavi[from][to] = make_pair(x - 4 - con, (l + r) / 2);
			dist[from][to] += 4 + con;
		}

		used[2] = 1;
		return;
	}
	if (!used[3]) {
		if (status) board[x + 1][(l + r) / 2] = '^', board[x + 2][(l + r) / 2] = '|', con = 1; else
			board[x + 1 + con][(l + r) / 2] = '|';
		string c = abc(val);
		if (status) {

			board[x + 2 + con][(l + r) / 2] = '|';
		}
		else {
			for (int i = 0; i < c.length(); i++)
				board[x + 2 + con][(l + r) / 2 - c.length() / 2 + i] = c[i];
		}
		board[x + 3 + con][(l + r) / 2] = '|';
		dsz = x + 3 + con;
		board[x + 4 + con][(l + r) / 2] = '+';
		if (status) {
			bolo[to][from] = make_pair(x + 4 + con, (l + r) / 2);
			dist[to][from] += 4 + con;
		}
		else {
			tavi[from][to] = make_pair(x + 4 + con, (l + r) / 2);
			dist[from][to] += 4 + con;
		}

		used[3] = 1;
		return;
	}
}

int viz[1001][1001];
void build(int v) {
	nodes.push_back(v);

	vector<int> num;
	for (int i = 0; i < in[v].size(); i++)
		num.push_back(len(in[v][i].second));
	for (int i = 0; i < out[v].size(); i++)
		num.push_back(len(out[v][i].second));

	int midx = n + 6 + distx;
	int midy = m + 5 + disty + len(num[0]);

	board[midx][midy] = '[';
	string c = abc(v);
	for (int i = midy + 1; i <= midy + c.length(); i++)
		board[midx][i] = c[i - midy - 1];
	board[midx][midy + c.length() + 1] = ']';
	used.resize(6);
	used.clear();
	used.resize(6);
	usz = midx - 1;
	dsz = midx + 1;
	lsz = midy - 1;
	rsz = midy + c.length() + 2;

	for (int i = 0; i < in[v].size(); i++) {
		place(1, v, in[v][i].first, in[v][i].second, midx, midy, midy + c.length() + 1);
	}
	for (int i = 0; i < out[v].size(); i++) {
		place(0, v, out[v][i].first, out[v][i].second, midx, midy, midy + c.length() + 1);
	}
	n = dsz;
	m = rsz;

	for (int i = usz; i <= dsz; i++)
	for (int j = lsz; j <= rsz; j++)
		viz[i][j] = 1;

}
queue<pair<int, int> > q;
int d[1001][1001];
pair<int, int> from[1001][1001];
int visit[1001][1001] = { 0 };
void check(int x, int y, pair<int, int> fr) 
{
	if (x >= 1 && x <= 100 && y >= 1 && y <= 100 && visit[x][y] == 0) {
		visit[x][y] = 1;
		q.push(make_pair(x, y));
		d[x][y] = d[fr.first][fr.second] + 1;
		from[x][y] = fr;
	}
}

char ch1[1001][1001], ch2[1001][1001];
int pirveli, meore;
void go(pair<int, int> A, pair<int, int> B)/> {
	while (!q.empty()) q.pop();
	q.push(A);
	for (int i = 0; i <= 1000; i++)
	for (int j = 0; j <= 1000; j++)
		visit[i][j] = viz[i][j], from[i][j].first = 0, from[i][j].second = 0;
	visit[A.first][A.second] = 1;


	while (!q.empty()) {
		pair<int, int> p = q.front();

		if (p == B)/> break;
		q.pop();

		check(p.first - 1, p.second, p);
		check(p.first + 1, p.second, p);
		check(p.first, p.second + 1, p);
		check(p.first, p.second - 1, p);
	}
	vector<pair<int, int> > path;

	while (1) {
		//cout << B.first << " " << B.second << endl;
		path.push_back(B)/>;
		if (from[B.first][B.second] == A) break;
		B = from[B.first][B.second];
	}
	path.push_back(A);
	reverse(path.begin(), path.end());


	for (int i = 0; i + 1< path.size(); i++) {
		if (i == path.size() - 1 || path[i].first == path[i + 1].first)
			ch1[path[i].first][path[i].second] = '-';
		else
			ch2[path[i].first][path[i].second] = '|';
	}
	dist[pirveli][meore] += path.size();
}


int main() {
	ifstream inp;
	inp.open("graph.dat");
	in.resize(N);
	out.resize(N);
	while (getline(inp, s)) {
		get_input(s);
	}

	for (int i = 0; i < N; i++)
	if (in[i].size() + out[i].size())
		build(i);
	for (int i = 0; i < N; i++)
	for (int j = 0; j < out[i].size(); j++) {
		//cout << tavi[i][out[i][j].first].first << " " << tavi[i][out[i][j].first].second << " " << bolo[i][out[i][j].first].first << " " << bolo[i][out[i][j].first].second << endl;
		pirveli = i;
		meore = out[i][j].first;
		go(tavi[i][out[i][j].first], bolo[i][out[i][j].first]);
	}
	for (int i = 0; i <= n + 10; i++) {
		for (int j = 0; j <= m + 10; j++)
		if (!board[i][j])  if (ch1[i][j] && ch2[i][j]) board[i][j] = '+'; else if (ch1[i][j]) board[i][j] = ch1[i][j]; else
		if (ch2[i][j]) board[i][j] = ch2[i][j]; else   board[i][j] = ' ';
	}

	for (int i = 0; i <= n + 10; i++)
	for (int j = 0; j <= m + 10; j++) {
		if (board[i][j] == '|') {
			if (board[i][j - 1] == '-' && board[i][j + 1] == '-') board[i][j] = '=';
			else if (board[i][j - 1] == '-') board[i][j] = '+';
			else if (board[i][j + 1] == '-') board[i][j] = '+';

		}
		else
		if (board[i][j] == '-') {
			if (board[i - 1][j] == '|' && board[i + 1][j] == '|') board[i][j] = '=';
			else
			if (board[i - 1][j] == '|' || board[i + 1][j] == '|') board[i][j] = '+';
		}
		else
		if (board[i][j] == '+') {
			if (board[i - 1][j] == '|' && board[i + 1][j] == '|' && board[i][j - 1] == '-' && board[i][j + 1] == '-')
				board[i][j] = '=';
			else {
				if (board[i][j - 1] == ' ' && board[i][j + 1] == ' ')
					board[i][j] = '|';

				if (board[i + 1][j] == ' ' && board[i - 1][j] == ' ')
					board[i][j] = '-';
			}
		}
	}


	for (int i = 0; i <= n + 10; i++) {
		for (int j = 0; j <= m + 10; j++)
			cout << board[i][j];
		cout << endl;
	}

	for (int i = 0; i < N; i++) {
		if (out[i].size() == 0) continue;
		cout << "from vertex " << i << " :";
		for (int j = 0; j < out[i].size(); j++) {
			cout << " to vertex " << out[i][j].first << " dist=" << dist[i][out[i][j].first] - 2 << ", ";
		}
		cout << endl;
	}
	system("pause");
	return 0;
}



Is This A Good Question/Topic? 0
  • +

Replies To: C++ Graph Code.

#2 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 13491
  • View blog
  • Posts: 53,888
  • Joined: 12-June 08

Re: C++ Graph Code.

Posted 05 January 2017 - 07:31 AM

Yada-yada looking a gift horse in the mouth, but damn.. that's impressive.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1