Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Aug 5th, 2012  |  syntax: None  |  size: 3.28 KB  |  hits: 13  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdio.h>
  2. #include "genlib.h"
  3. #include "simpio.h"
  4. #include "pqueue.h"
  5. #include "primkruskal.h"
  6.  
  7. #define MAX_CONST 10000
  8.  
  9. int graph[MAX_CONST][MAX_CONST];
  10. int nNodes;
  11. int total;
  12.  
  13. /* Prototypes */
  14. void getDist(void);
  15. bool isAUnion(edgeADT edge, int *nodeId);
  16.  
  17. /* Code */
  18. void getDist() {
  19.         int i, j;
  20.         FILE *OPEN;
  21.         string DIST_PATH;
  22.  
  23.         printf("Enter the name of the file: ");
  24.         DIST_PATH = GetLine();
  25.  
  26.         OPEN = fopen(DIST_PATH, "r");
  27.         fscanf(OPEN, "%d", &nNodes);
  28.         for(i = 0; i < nNodes; ++i) {
  29.                 for(j = 0; j < nNodes; ++j) {
  30.                         fscanf(OPEN, "%4d", &graph[i][j]);
  31.                 }
  32.         }
  33.  
  34.         fclose(OPEN);
  35.  
  36.         /* Mark all nNodes as NOT beeing in the minimum spar */
  37.         /*for(i = 0; i < nNodes; ++i) {
  38.                 inTree[i] = 0;
  39.         }*/
  40.         system("cls");
  41. }
  42.  
  43. bool isAUnion(edgeADT edge, int nodeId[]){
  44.         if(nodeId[edge.i] == nodeId[edge.j] && nodeId[edge.i] > 0) {
  45.                 return TRUE;
  46.         } else {
  47.                 return FALSE;
  48.         }
  49. }
  50.  
  51. void kruskal() {
  52.         int i, j, *nodeId, nextId = 0, temp, total = 0;
  53.         edgeADT edge;
  54.         pqueueADT queue = NewPQueue();
  55.  
  56.         getDist();
  57.         nodeId = NewArray(nNodes, int);
  58.  
  59.         for(i = 0; i < nNodes; i++) {
  60.                 for(j = 0; j < nNodes; j++) {
  61.                         if(graph[i][j] != 0 && graph[i][j] != MAX_CONST) {
  62.                                 edge.value = graph[i][j];
  63.                                 edge.i = i;
  64.                                 edge.j = j;
  65.                                 Enqueue(queue, edge);
  66.                         }
  67.                 }
  68.         }
  69.  
  70.         SortQueue(queue);
  71.  
  72.         for(i = 0; i < nNodes; i++) {
  73.                 nodeId[i] = 0;
  74.         }
  75.  
  76.         // First tree
  77.         edge = DequeueMin(queue);
  78.         nodeId[edge.i] = nextId;
  79.         nodeId[edge.j] = nextId;
  80.         nextId++;
  81.         //total += edge.value;
  82.         //printf("Adding edge %d - %d = %d\n", edge.i, edge.j, edge.value);
  83.  
  84.         // Rest of tree
  85.         while(!IsEmpty(queue)) {
  86.                 edge = DequeueMin(queue);
  87.                 if(!isAUnion(edge, nodeId)){
  88.                         if(nodeId[edge.i] == 0 && nodeId[edge.j] == 0) {    //New tree
  89.                                 nodeId[edge.i] = nextId;
  90.                                 nodeId[edge.j] = nextId;
  91.                                 nextId++;
  92.                         } else if(nodeId[edge.i] != 0 && nodeId[edge.j] != 0) {  //Merge tree
  93.                                 temp = nodeId[edge.j];
  94.                                 for(i = 0; i < nNodes; i++){
  95.                                         if(nodeId[i] == temp) {
  96.                                                 nodeId[i] = nodeId[edge.i];
  97.                                         }
  98.                                 }
  99.                         } else if(nodeId[edge.i] == 0 && nodeId[edge.j] != 0){  //Single node
  100.                                 nodeId[edge.i] = nodeId[edge.j];
  101.                         } else if(nodeId[edge.j] == 0 && nodeId[edge.i] != 0){
  102.                                 nodeId[edge.j] = nodeId[edge.i];
  103.                         }
  104.      
  105.                         printf("Adding edge %d - %d = %d\n", edge.i, edge.j, edge.value);
  106.                         total += edge.value;
  107.                 }
  108.         }
  109.  
  110.         printf("Size of graph: %d\n\n", total);
  111. }
  112.  
  113. void prims() {
  114.         edgeADT edge;
  115.         bool *nodes;
  116.         int currentNode, freeNodes, i, total;
  117.         pqueueADT queue = NewPQueue();
  118.         currentNode = 0;
  119.         total = 0;
  120.  
  121.         getDist();
  122.         freeNodes = nNodes-1;
  123.  
  124.         nodes = NewArray(nNodes, bool);
  125.  
  126.         for(i = 0; i < nNodes; i++){
  127.                 nodes[i] = 0;
  128.         }
  129.        
  130.         //Insert first node into MST
  131.         nodes[0] = 1;
  132.         freeNodes--;
  133.  
  134.         while(TRUE) {
  135.                 for(i = 0; i <= nNodes - 1; i++) {
  136.                         if(graph[currentNode][i] != 0) {
  137.                                 edge.i = currentNode;
  138.                                 edge.j = i;
  139.                                 edge.value = graph[currentNode][i];
  140.  
  141.                                 Enqueue(queue, edge);
  142.                         }
  143.                 }
  144.  
  145.                 SortQueue(queue);
  146.  
  147.                 do{
  148.                         edge = DequeueMin(queue);
  149.                 } while(nodes[edge.j]);
  150.  
  151.                 printf("Adding edge %d - %d = %d\n", edge.i, edge.j, edge.value);
  152.                 total += edge.value;
  153.                 nodes[edge.j] = 1;
  154.                 currentNode = edge.j;
  155.  
  156.                 if(freeNodes == 0) break;
  157.                 freeNodes--;
  158.         }
  159.  
  160.         printf("Size of graph: %d\n\n", total);
  161.         system( "pause" );
  162. }
create a new version of this paste RAW Paste Data