SHARE
TWEET

Untitled

a guest Apr 21st, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Graph ADT interface for Ass2 (COMP2521)
  2. #include "CentralityMeasures.h"
  3. #include "Dijkstra.h"
  4. #include "PQ.h"
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <assert.h> /////======i included this, are we allowed? I think.
  8.  
  9.  
  10. static double* createValueArray (int noNodes);
  11. static void accumulateBetweenness(ShortestPaths paths, double *values, int *dividers);
  12.  
  13. //for each node, iterate through the adjacency list,
  14. //count the number of outincident edges and add that to the corresponding values array
  15. NodeValues outDegreeCentrality(Graph g){
  16.     //printf("Entering out deg func\n");
  17.     assert(g!= NULL);
  18.     NodeValues throwAway = {0};
  19.     int numNodes = numVerticies(g);
  20.     //printf("num nodes %d\n", numNodes);
  21.     throwAway.noNodes = numNodes;
  22.     throwAway.values = createValueArray(numNodes);
  23.     for (int v = 0; v < numNodes; v++){
  24.         int count = 0;
  25.         AdjList outIncList = outIncident(g, v);
  26.         AdjList curr = outIncList;
  27.         if (curr == NULL){ //edge case1 - no items in adjlist
  28.             count = 0;
  29.             throwAway.values[v] = count;
  30.             //printf("count = %d\n", count);
  31.             continue;
  32.         }
  33.         if (curr->next == NULL){//edge case 2 - 1 item in adj list
  34.             count = 1;
  35.             throwAway.values[v] = count;
  36.             //printf("count = %d\n", count);
  37.             continue;
  38.         }
  39.         while (curr->next != NULL){ //iterate through list
  40.             count ++;
  41.             curr = curr->next;
  42.         }
  43.         count ++; //add one extra to count for the first one.
  44.         throwAway.values[v] = count;
  45.         //printf("count = %d\n", count);
  46.     }
  47.     return throwAway;
  48. }
  49. NodeValues inDegreeCentrality(Graph g){
  50.     assert(g!= NULL);
  51.     NodeValues throwAway = {0};
  52.     int numNodes = numVerticies(g);
  53.     //printf("num nodes %d\n", numNodes);
  54.     throwAway.noNodes = numNodes;
  55.     throwAway.values = createValueArray(numNodes);
  56.     for (int v = 0; v < numNodes; v++){
  57.         int count = 0;
  58.         AdjList inIncList = inIncident(g, v);
  59.         AdjList curr = inIncList;
  60.         if (curr == NULL){ //edge case1 - no items in adjlist
  61.             count = 0;
  62.             throwAway.values[v] = count;
  63.             //printf("count = %d\n", count);
  64.             continue;
  65.         }
  66.         if (curr->next == NULL){//edge case 2 - 1 item in adj list
  67.             count = 1;
  68.             throwAway.values[v] = count;
  69.             //printf("count = %d\n", count);
  70.             continue;
  71.         }
  72.         while (curr->next != NULL){ //iterate through list
  73.             count ++;
  74.             curr = curr->next;
  75.         }
  76.         count ++; //add one extra to count for the first one.
  77.         throwAway.values[v] = count;
  78.         //printf("count = %d\n", count);
  79.     }
  80.     return throwAway;
  81. }
  82. NodeValues degreeCentrality(Graph g) {
  83.     assert(g!= NULL);
  84.     NodeValues throwAway = {0};
  85.     int numNodes = numVerticies(g);
  86.     //printf("num nodes %d\n", numNodes);
  87.     throwAway.noNodes = numNodes;
  88.     throwAway.values = createValueArray(numNodes);
  89.     for (int v = 0; v < numNodes; v++){
  90.         int count = 0;
  91.         AdjList outIncList = outIncident(g, v);
  92.         AdjList curr = outIncList;
  93.         if (curr == NULL){ //edge case1 - no items in adjlist
  94.             count = 0;
  95.             throwAway.values[v] = count;
  96.             //printf("count = %d\n", count);
  97.             continue;
  98.         }
  99.         if (curr->next == NULL){//edge case 2 - 1 item in adj list
  100.             count = 1;
  101.             throwAway.values[v] = count;
  102.             //printf("count = %d\n", count);
  103.             continue;
  104.         }
  105.         while (curr->next != NULL){ //iterate through list
  106.             count ++;
  107.             curr = curr->next;
  108.         }
  109.         count ++; //add one extra to count for the first one.
  110.         throwAway.values[v] = count;
  111.         //printf("count = %d\n", count);
  112.     }
  113.         for (int v = 0; v < numNodes; v++){
  114.         int count = 0;
  115.         AdjList inIncList = inIncident(g, v);
  116.         AdjList curr = inIncList;
  117.         if (curr == NULL){ //edge case1 - no items in adjlist
  118.             count = 0;
  119.             throwAway.values[v] = throwAway.values[v] + count;
  120.             //printf("count = %d\n", count);
  121.             continue;
  122.         }
  123.         if (curr->next == NULL){//edge case 2 - 1 item in adj list
  124.             count = 1;
  125.             throwAway.values[v] = throwAway.values[v] + count;
  126.             //printf("count = %d\n", count);
  127.             continue;
  128.         }
  129.         while (curr->next != NULL){ //iterate through list
  130.             count ++;
  131.             curr = curr->next;
  132.         }
  133.         count ++; //add one extra to count for the first one.
  134.         throwAway.values[v] = throwAway.values[v] + count;
  135.         //printf("count = %d\n", count);
  136.     }
  137.     return throwAway;
  138. }
  139. /*This function might break if you can have edges of weight 0!
  140. because we calculate reachability using the distance array (if distance = 0).*/
  141. NodeValues closenessCentrality(Graph g){
  142.     assert(g!= NULL);
  143.     NodeValues throwAway = {0};
  144.     int numNodes = numVerticies(g);
  145.     //printf("num nodes %d\n", numNodes);
  146.     throwAway.noNodes = numNodes;
  147.     throwAway.values = createValueArray(numNodes);
  148.  
  149.  
  150.     for (int v = 0; v< numNodes; v++){
  151.         //====according to formula ===
  152.         //v = vertex
  153.         //n = out incidence of v
  154.         //N = numNodes in graph
  155.         //can get shortest path with dijk.dist[v]
  156.         //the sum of the shortest paths of v to all other nodes
  157.  
  158.         //count the number of out incident edges of v. -- should make into new function.
  159.         /*AdjList outIncList = outIncident(g, v);
  160.         AdjList curr = outIncList;
  161.         int count = 0;
  162.         if (curr == NULL){ //edge case1 - no items in adjlist
  163.             count = -1; //-1 because it will add one once it finishes this loop
  164.             //printf("count = %d\n", count);
  165.         }
  166.         else if (curr->next == NULL){//edge case 2 - 1 item in adj list
  167.             count = 0; // 0 because adds one after finishes loop
  168.             //printf("count = %d\n", count);
  169.         }
  170.         while (curr->next != NULL){ //iterate through list
  171.             count ++;
  172.             curr = curr->next;
  173.         }
  174.         count ++; //add one extra to count for the first one.
  175.         int numOutInc = count;*/
  176.         int reachableNodes = 0; //will not include itself.
  177.  
  178.  
  179.         ShortestPaths shortestPaths = dijkstra(g, v);
  180.         int sumShortestPaths = 0;
  181.         for (int destVertex = 0; destVertex < numNodes; destVertex++){
  182.                 if (destVertex != v) {//we cant add the shortest path from v to v.
  183.                     if (shortestPaths.dist[destVertex] != 0) { //if the node is reachable!
  184.                         reachableNodes++;
  185.                     }
  186.                     sumShortestPaths = sumShortestPaths + shortestPaths.dist[destVertex];
  187.                 }  //add the distances up to create this sum
  188.                
  189.         }
  190.         //printf("ReachabeNodes = %d\n sumShortestPaths = %d\n numnodes = %d \n ", reachableNodes, sumShortestPaths, numNodes);
  191.         if (((numNodes - 1) == 0 )| (sumShortestPaths == 0)) { //if we are going to have a divide by 0 error.
  192.             throwAway.values[v] = 0;
  193.             continue;
  194.         }
  195.         double LHSAnswer = (double)(reachableNodes) / (numNodes-1);
  196.         double RHSAnswer = (double)(reachableNodes)/(sumShortestPaths);
  197.         //printf("LHS Answer = %lf \n, RHS Answer = %lf\n", LHSAnswer, RHSAnswer);
  198.         double answer = LHSAnswer*RHSAnswer;
  199.         throwAway.values[v] = answer;
  200.  
  201.     }
  202.  
  203.  
  204.  
  205.  
  206.     return throwAway;
  207. }
  208.  
  209. NodeValues betweennessCentrality(Graph g){
  210.     double *values = createValueArray(numVerticies(g));
  211.     int *dividers = malloc(numVerticies(g) * sizeof(int)); // Holds ints to scale values array down (because betweenness centrality for a given node is less if there are other shortest paths between two points that don't go through the node)
  212.    
  213.     for (int v = 0; v < numVerticies(g); v++) {
  214.         ShortestPaths paths = dijkstra(g, v);
  215.         accumulateBetweenness(paths, values, dividers);
  216.     }
  217.    
  218.    
  219.    
  220.    
  221.     NodeValues throwAway = {0};
  222.     return throwAway;
  223. }
  224.  
  225. NodeValues betweennessCentralityNormalised(Graph g){
  226.     NodeValues throwAway = {0};
  227.     return throwAway;
  228. }
  229.  
  230. void showNodeValues(NodeValues values){
  231.     for (int v = 0; v < values.noNodes; v++){
  232.         printf("%d: %lf\n", v, values.values[v]);
  233.     }
  234.    
  235. }
  236.  
  237. void freeNodeValues(NodeValues values){
  238.     free(values.values);
  239. }
  240.  
  241. static double * createValueArray (int noNodes){
  242.     double * values = malloc(noNodes * sizeof(double)); //malloc an array of doubles to be pointed to by the struct.
  243.     assert(values != NULL);
  244.     for (int i = 0; i < noNodes; i++){
  245.         values[i] = 0;
  246.     }
  247.     return values;
  248. }
  249.  
  250.  
  251. static void accumulateBetweenness(ShortestPaths paths, double *values, int *dividers) {
  252.         for (int u = 0; u < paths.noNodes; u++) { // Accumulating betweeness and dividers for each node with a path to the source
  253.             if (paths.src == u) continue; // skip checking path from source to source
  254.            
  255.             //paths->pred[u] =
  256.            
  257.         }
  258.     return;
  259. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top