How to add a statement where the information is insuficient?

user_14898374 0
Viewed 92

Okay, so. I have a program that I've been working on for some time now. The project consists of finding the cheapest way to connect all cities - either by airport or road connection. I've used Kruskal's algorithm for this and interpreted that the cities are the graphs vertexes, the roads are edges between cities and that the airports connect to other cities through a "sky" vertex. However, one of the requirements for this project is that, when there's a city that isn't connected either by road or airport, it should give the user the following output: "Insuficient".

Full code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V;
    int E;
    struct Edge* edge;
};

struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = malloc(sizeof *graph);
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
};

struct subset {
    int parent;
    int rank;
};

int find(struct subset subsets[], int i)
{
    if (subsets[i].parent != i)
        subsets[i].parent
            = find(subsets, subsets[i].parent);

    return subsets[i].parent;
}

void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;

    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

int myComp(const void* a, const void* b)
{
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}

void KruskalMST(struct Graph* graph)
{
    int V = graph->V;
    struct Edge
    result[V];
    int e = 0;
    int i = 0;

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]),
          myComp);

    struct subset* subsets
        = (struct subset*)malloc(V * sizeof(struct subset));

    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];

        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }

    printf("MST edges:\n");
    printf("V1   V2   Cost\n");
    int minimumCost = 0;
    int nRoads = 0;
    int nAirports = 0;
    for (i = 0; i < e; ++i)
    {
        printf("%d -- %d == %d\n", result[i].src,
               result[i].dest, result[i].weight);
        if (result[i].dest == 0) {
            nAirports++;
        }
        else {
            nRoads++;
        }
        minimumCost += result[i].weight;
    }
    printf("Minimum Spanning Tree total cost: %d\n",minimumCost);
    printf("Number de airports: %d\n",nAirports);
    printf("Number of roads: %d",nTotal);
    }
    return;
}

int main()
{
    int v = 0;
    int a = 0;
    int edges = 0;
    int r = 0;
    int city = 0;
    int airport = 0;
    int city1 = 0;
    int city2 = 0;
    int cost = 0;

    printf("Insert the number of cities: \n");
    scanf("%d", &v);
    printf("Insert the number of airports: \n");
    scanf("%d", &a);
    printf("Insert the number of roads: \n");
    scanf("%d", &r);

    edges = a + r;

    struct Graph* graph = createGraph(v, edges);

    for (int i = 0; i < a; i++) {
        printf("Insert the city and the cost of building the airport: \n");
        scanf(" %d %d", &city, &airport);

        graph->edge[i].src = city;
        graph->edge[i].dest = 0;
        graph->edge[i].weight = airport;
    }

    for (int j = a; j < edges; j++) {
        printf("Insert the cities and the cost of the road: \n");
        scanf(" %d %d %d", &city1, &city2, &cost);

        graph->edge[j].src = city1;
        graph->edge[j].dest = city2;
        graph->edge[j].weight = cost;
    }

    KruskalMST(graph);

    return 0;
}

Example where it should not return an MST (Vertex 4 isn't connected):

Example where it should return an MST (All vertexes connected):

So far I tried to look for why it wasn't returning an error when all vertexes weren't connected and I couldn't find the spot. If I got an error I could use the setjmp/longjmp to simulate catching the error but, for that, I need to have an error first.

codeblocks c
1 Answers

From what I can derive from your code, you don't have any means for entering a vertex that hasn't got at least one connection to another vertex.

An undirected graph consist of two sets of distinct information:

  1. Vertices
  2. Edges

I think you have one array of edges where the array index itself is the vertex label, and that's fine, as long you only ever need to represent connected vertices.

The most common and compact implementation of Kruskal's algorithm in C, employs a two dimension array as [vertices][edges]. Your code consists a one "graph" containing an array of edges.

A quick search online, turns up some examples, but they all seem to work with fully connected networks. Your assignment seems to include the requirement that the network is not fully connected, therefore; you require a means for entering and storing a vertex that is not connected to anything. In other words, you need to be able to add nodes to your graph that do not connect to anything else.

Based on your code, you might be able to create unconnected islands, but you'll have to be carful that those aren't directly or indirectly connected to V0. You'll also have to add code to detect those islands.

The first thing you need is a data set that has two or more island networks. The smallest island your code will let you create is a pair of vertices connected by one road. If you create that first, and then make sure none of the remaining edges that you define are connected to that first pair in any way, you'll have at least two islands.

Then you run your program and see what happens. It will probably fail, but now you've got a data set you can work with for testing changes to your code. We call this unit testing. You need two simple data sets. One fully connected set and one that has islands. You can store program inputs in a file and pipe them into your app:

inputPartiallyConnected.txt | YourApp
inputFullyConnected.txt | YourApp

Example Partially Connected

Enter that into your program. The values on the left can be stored in a file. The bent arrows are carriage returns. Your code needs to recognize that 1 and 2 cannot be reached from any of the other nodes.

Here's the text:

6
1
8
3 8
1 2 10
3 4 11
5 6 6
4 6 7
5 4 5
5 4 1
6 3 2

You can create a fully connected version by adding a road between 2 and 4, or 1 and 3. Keep it simple.

Your Kruskal's algorithm implementation will not work correctly with multiple forests. The data set above is essentially two forests. You can prevent the user from inputting more than one forest by requiring every new edge, except the first one, includes at least one vertex that is referenced in one of the previously entered edges.

So

  • for each new edge after the first one,
  • for each vertex in the new edge,
  • search all pervious edges for that vertex.
  • If neither of them is found in the previous edges,
  • then you could issue the "Insufficient" output and discard that bad edge,
  • then prompt the user for input again.
  • Rinse and repeat.

Since, in the above test data set, we enter 1--2 followed by 3--4, we should get an Insufficient warning for literally every edge that follows, because they do not contain either 1 or 2 in their vertex sets. So once you have code that successfully reject everything but 1--2 in the above list, you can then reorder it, such that you are always constructing a fully connected graph (aka: A single tree).

If your assignment was to accept a forest of trees, then you'll have to find the islands first, and run each of them separately through the Kruskal's algorthm.

user_31504450
Related