aadsgraphs

// 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;

}