Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // aads_graphs.cpp : Defines the entry point for the console application.
- //
- #include "stdafx.h"
- #include <algorithm>
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <sstream>
- #include <string>
- #include <list>
- #define nodes 5
- #define INF 99999
- using namespace std;
- vector<vector<int>> readfromfile(string filename) {
- vector<vector<int>> distances;
- ifstream file(filename);
- string line;
- while (getline(file, line))
- {
- vector<int> lineData;
- stringstream lineStream(line);
- int value;
- // Read an integer at a time from the line
- while (lineStream >> value)
- {
- // Add the integers from a line to a 1D array (vector)
- lineData.push_back(value);
- }
- // When all the integers have been read, add the 1D array
- // into a 2D array (as one line in the 2D array)
- distances.push_back(lineData);
- }
- return distances;
- }
- void fillgraphinit(int fill[nodes][nodes]) {
- for (int row = 0; row < nodes; row++) {
- for (int col = 0; col < nodes; col++) {
- if (row == col)
- fill[row][col] = 0;
- else
- fill[row][col] = INF;
- }
- }
- //fills array with zero distances between the same nodes and infinity between different nodes
- }
- void printarr(int arr[nodes][nodes]) {
- for (int i = 0; i < nodes; ++i)
- {
- for (int j = 0; j < nodes; ++j)
- {
- cout << arr[i][j] << " ";
- }
- cout << endl;
- }
- }
- void printvec(vector<vector<int>> vec) {
- for (int i = 0; i < vec.size(); i++)
- {
- for (int j = 0; j < vec[i].size(); j++)
- {
- cout << vec[i][j] << " ";
- }
- cout << endl;
- }
- }
- void fwalg(int gr[nodes][nodes], int next[nodes][nodes], vector<vector<int>> vect) {
- for (int row = 1; row < vect.size(); row++) {
- gr[vect[row][0] - 1][vect[row][1] - 1] = vect[row][2];
- next[vect[row][0] - 1][vect[row][1] - 1] = vect[row][1] - 1;
- }
- //go row by row and fill the graph array where the
- //graph row index is the first number minus one of the value in column 0 of current row
- //graph col index is the second number minus one of the value in column 1 of current row
- //value to put into graph[row][col] is the distance between the nodes in previous columns in current row
- for (int k = 0; k < nodes; k++) {
- for (int i = 0; i < nodes; i++) {
- for (int j = 0; j < nodes; j++) {
- if (gr[i][j]>gr[i][k] + gr[k][j]) {
- gr[i][j] = gr[i][k] + gr[k][j];
- next[i][j] = next[i][k];
- }
- }
- }
- }
- }
- void printpath(int a, int b, int next[nodes][nodes]) {//a is the source node b is the target node
- a = a - 1;
- b = b - 1;
- if (next[a][b] != 0) {
- cout << a + 1 << "->";
- while (a != b) {
- a = next[a][b];
- cout << a + 1 << "->";
- }
- }
- cout << endl;
- }
- void bfsutil(list<int> *edges, int currnode, bool visited[]) {
- visited[currnode] = true;//set currently checked node as visited
- cout << currnode << " ";
- list<int>::iterator i;
- for (i = edges[currnode].begin(); i != edges[currnode].end(); ++i)
- if (!visited[*i])// if the node isn't visited then rerun the util for next nodes
- bfsutil(edges, *i, visited);
- }
- void bfs(vector< vector<int> > Edge, int currnode) {
- int count = Edge[0][0];//count of nodes
- list<int> *edges = new list<int>[count]; //list of edges
- Edge.erase(Edge.begin());//delete first line from Edges vector since it has the count of nodes and edges instead of edge data
- for (int i = 0; i < Edge.size(); i++)
- {
- edges[Edge[i][0]].push_back(Edge[i][1]);//fill list of edges with edges from file
- }
- bool *visited = new bool[count]; //list of visited nodes
- for (int i = 0; i < count; i++)
- visited[i] = false;//initialize array to all nodes not visited
- bfsutil(edges,currnode, visited);
- }
- int main()
- {
- int graph[nodes][nodes];
- int next[nodes][nodes] = { 0 };
- fillgraphinit(graph);
- vector<vector<int>> fileread = readfromfile("floyd1.txt");
- //printvec(fileread);
- fwalg(graph, next, fileread);
- //cout << endl;
- //printarr(graph);
- //cout << endl << endl;
- //printarr(next);
- printpath(5, 3, next);
- vector< vector<int> > bfsEdge;
- bfsEdge = readfromfile("graph1.txt");
- int count = bfsEdge[0][0];
- //printvec(bfsEdge);
- //cout << endl;
- bfs(bfsEdge, 0);
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement