"Vulnerability Edge" rev_01

/********* Pleasedontcode.com **********

    Pleasedontcode thanks you for automatic code generation! Enjoy your code!

    - Terms and Conditions:
    You have a non-exclusive, revocable, worldwide, royalty-free license
    for personal and commercial use. Attribution is optional; modifications
    are allowed, but you're responsible for code maintenance. We're not
    liable for any loss or damage. For full terms,
    please visit pleasedontcode.com/termsandconditions.

    - Project: "Vulnerability Edge"
    - Source Code NOT compiled for: ESP8266 NodeMCU V1.0
    - Source Code created on: 2024-12-01 10:05:37

********* Pleasedontcode.com **********/

/****** SYSTEM REQUIREMENTS *****/
/****** SYSTEM REQUIREMENT 1 *****/
    /* Let G = (V, E) be a weighted, undirected, acyclic, */
    /* connected graph with weight function w : V → Z. */
    /* Let  n be the number of vertices in G. Observe */
    /* that such a graph has exactly n − 1 edges. We are */
    /* also given  a cost c : E → Z per edge. Since G is */
/****** END SYSTEM REQUIREMENTS *****/

/* START CODE */

/****** DEFINITION OF LIBRARIES *****/
#include <Arduino.h> // Include Arduino library for basic functions

/****** FUNCTION PROTOTYPES *****/
void setup(void);
void loop(void);

// Define constants and global variables
#define INF 1000000 // Define a constant for infinity
const int MAX_VERTICES = 100; // Define maximum number of vertices
int weights[MAX_VERTICES]; // Array to hold weights of vertices
int edgeCount = 0; // Counter for edges
struct Edge {
    int u, v, cost;
} edges[MAX_VERTICES]; // Array to hold edges
int visited[MAX_VERTICES]; // Array to track visited vertices
// Assuming Node structure is defined elsewhere
struct Node {
    int vertex;
    Node* next;
};
Node* adjList[MAX_VERTICES]; // Adjacency list for graph

// Depth First Search function
int dfs(int vertex) {
    visited[vertex] = 1;
    int sum = weights[vertex];
    Node *temp = adjList[vertex];
    while (temp) {
        if (!visited[temp->vertex]) {
            sum += dfs(temp->vertex);
        }
        temp = temp->next;
    }
    return sum;
}

// Find the edge with the smallest vulnerability
void findMinVulnerability() {
    int minVulnerability = INF, minEdgeIndex = -1;

    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int cost = edges[i].cost;

        // Temporarily remove the edge
        memset(visited, 0, sizeof(visited));
        visited[v] = 1; // Prevent DFS to v from u
        int sumH1 = dfs(u);

        memset(visited, 0, sizeof(visited));
        visited[u] = 1; // Prevent DFS to u from v
        int sumH2 = dfs(v);

        // Restore edge and compute vulnerability
        int vulnerability = cost - abs(sumH1 - sumH2);
        if (vulnerability < minVulnerability) {
            minVulnerability = vulnerability;
            minEdgeIndex = i;
        }
    }

    // Use Serial.print instead of printf
    Serial.print("Edge with the smallest vulnerability: ");
    Serial.print(edges[minEdgeIndex].u);
    Serial.print(" ");
    Serial.println(edges[minEdgeIndex].v);
}

void addEdge(int u, int v, int cost) {
    // Add edge to the adjacency list
    Node* newNode = new Node();
    newNode->vertex = v;
    newNode->next = adjList[u];
    adjList[u] = newNode;

    // Increment edge count
    edgeCount++;
}

void setup(void)
{
    // Initialize Serial communication
    Serial.begin(115200);

    // put your setup code here, to run once:
    Serial.println("Enter the number of vertices: ");
    while (Serial.available() == 0) {} // Wait for input
    int n = Serial.parseInt(); // Read number of vertices

    Serial.println("Enter the weights of vertices:");
    for (int i = 1; i <= n; i++) {
        while (Serial.available() == 0) {} // Wait for input
        weights[i] = Serial.parseInt(); // Read weights
    }

    Serial.println("Enter the edges and their costs (u v cost):");
    while (true) {
        int u, v, cost;
        if (Serial.available() > 0) {
            u = Serial.parseInt();
            v = Serial.parseInt();
            cost = Serial.parseInt();
            if (u == 0 && v == 0 && cost == 0) break; // Use a break condition
        }

        addEdge(u, v, cost);
        addEdge(v, u, cost); // For undirected graph

        edges[edgeCount].u = u;
        edges[edgeCount].v = v;
        edges[edgeCount].cost = cost;
        edgeCount++;
    }

    findMinVulnerability();
}

void loop(void)
{
    // put your main code here, to run repeatedly:
}

/* END CODE */