// Drake Lin
// 5/20/19
// Graphs
// given adjacency matrix, calculate edge list and incidence matrix

#include "pch.h"
#include <iostream>
#include <vector>

using namespace std;

//create Graph struct with number of vertices and edges, initial adjacency matrix
//initialize four matrices
struct Graph {
    int vertices;
    int edges;

    //big matrix to account for big graphs
    int adj[20][20];
}one, two, three, four;

//prints adjacency matrix, use vertices to limit matrix to size
//input: graph struct
//output: none
void printAdj(Graph g)
{
    cout << "Adjacency matrix: " << endl;
    for (int i = 1; i < g.vertices+1; i++)
    {
        for (int j = 1; j < g.vertices+1; j++)
        {
            cout << g.adj[i][j];
        }
        cout << endl;
    }
}

//adding edge with vertices in matrixes
//input: graph struct, vertices
//output: none
void addEdge(Graph &g, int v1, int v2)
{
    g.adj[v1][v2] = 1;
    g.adj[v2][v1] = 1;
}

//printing edge list
//input: graph struct
//output: none
void printEdge(Graph g)
{
    cout << "Edges: " << endl;
    for (int i = 0; i < 20; i++)
    {
        for (int j = i; j < 20; j++)
        {
            //detects if there is an edge in adjacency matrix
            if (g.adj[i][j] == 1)
            {
                cout << i << "," << j << endl;
            }
        }
    }
}

//calculates and prints incidence matrix
//input: graph struct
//output: none
void printInc(Graph &g)
{
    //initialize big matrix
    cout << "Incidence Matrix: " << endl;
    int inc[20][100];

    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            inc[i][j] = 0;
        }
    }


    //initialize variable used to number edges
    int vert = 0;

    for (int i = 0; i < 20; i++)
    {
        for (int j = i; j < 20; j++)
        {
            //see edges in adjacency matrix
            if (g.adj[i][j] == 1)
            {
                //print out
                inc[i][vert] = 1;
                inc[j][vert] = 1;

                //move edge number
                vert++;
            }
        }
    }

    //print out incidence matrix with size in mind
    for (int i = 1; i < g.vertices+1; i++)
    {
        for (int j = 0; j < g.edges; j++)
        {
            cout << inc[i][j];
        }
        cout << endl;
    }
}

//Graph 1: p274, Figure 6.2.1
//input: empty graph struct
//output: none
void create1(Graph &g)
{
    addEdge(g, 1, 2);
    addEdge(g, 2, 3);
    addEdge(g, 3, 4);
    addEdge(g, 2, 4);
    addEdge(g, 2, 5);
    addEdge(g, 2, 6);
    addEdge(g, 5, 6);
    addEdge(g, 6, 7);
    g.edges = 8;
    g.vertices = 7;
}

//Graph 2: p300, #1
//input: empty graph struct
//output: none
void create2(Graph &g)
{
    addEdge(g, 1, 2);
    addEdge(g, 2, 3);
    addEdge(g, 1, 5);
    addEdge(g, 3, 4);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 5, 3);
    addEdge(g, 5, 4);
    g.edges = 8;
    g.vertices = 5;
}

//Graph 3: p300, #3
//input: empty graph struct
//output: none
void create3(Graph &g)
{
    addEdge(g, 1, 2);
    addEdge(g, 3, 5);
    addEdge(g, 5, 4);
    addEdge(g, 3, 4);
    g.edges = 4;
    g.vertices = 5;
}

//Graph 4: p307, Fig. 6.7.2
//input: empty graph struct
//output: none
void create4(Graph &g)
{
    addEdge(g, 1, 2);
    addEdge(g, 1, 5);
    addEdge(g, 1, 6);
    addEdge(g, 2, 3);
    addEdge(g, 3, 4);
    addEdge(g, 2, 5);
    addEdge(g, 4, 5);
    addEdge(g, 4, 6);
    g.edges = 8;
    g.vertices = 6;
}

//prints out adjacency matrix, edge list, incidence matrix
//input: graph struct
//output: none
void printAll(Graph g)
{
    printAdj(g);
    printEdge(g);
    printInc(g);
}

//main runs through all graphs
int main()
{
    create1(one);
    cout << "Graph 1:" << endl;
    printAll(one);

    create2(two);
    cout << endl << "Graph 2:" << endl;
    printAll(two);

    create3(three);
    cout << endl << "Graph 3:" << endl;
    printAll(three);

    create4(four);
    cout << endl << "Graph 4:" << endl;
    printAll(four);
}