/*

A Graph is a data structure made up of elements (vertices) that are connected to other elements (vertices)
through edges with functions to determine adjacencies between vertices. This is implemented through
an Edge struct and a Graph class which has functions to add edges between any two of ten different
vertices and to print the resulting graph.


*/



// Max number of vertices in the graph
#define MAX_VERTICES 10

// Structure to represent an edge between two vertices
struct Edge {
  int vertex;
  Edge* next;
};

// Graph class that contains an adjacency list
class Graph {
  private:
    // Array of adjacency lists for each vertex
    Edge* adjList[MAX_VERTICES];
    int numVertices;

  public:
    // Constructor to initialize the graph
    Graph(int vertices) {
      numVertices = vertices;
      for (int i = 0; i < numVertices; i++) {
        adjList[i] = NULL;
      }
    }

    // Add an edge between two vertices (undirected graph)
    void addEdge(int u, int v) {
      // Add edge from u to v
      Edge* newEdge = new Edge;
      newEdge->vertex = v;
      newEdge->next = adjList[u];
      adjList[u] = newEdge;

      // Add edge from v to u (since it's undirected)
      newEdge = new Edge;
      newEdge->vertex = u;
      newEdge->next = adjList[v];
      adjList[v] = newEdge;
    }

    // Print the adjacency list for each vertex
    void printGraph() {
      for (int i = 0; i < numVertices; i++) {
        Serial.print("Vertex ");
        Serial.print(i);
        Serial.print(": ");
        Edge* temp = adjList[i];
        while (temp != NULL) {
          Serial.print(temp->vertex);
          Serial.print(" -> ");
          temp = temp->next;
        }
        Serial.println("NULL");
      }
    }
};

// Initialize the graph
Graph graph(MAX_VERTICES);

void setup() {
  // Start the Serial communication for printing
  Serial.begin(9600);

  // Example: adding edges to the graph
  graph.addEdge(0, 1);
  graph.addEdge(0, 4);
  graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(1, 4);
  graph.addEdge(2, 3);
  graph.addEdge(3, 4);

  // Print the graph
  graph.printGraph();
}

void loop() {
  // Nothing to do here
}