Refactor the C/C++ algorithm, listed below, to use Advanced C++ features. Do NOT

Question

Refactor the C/C++ algorithm, listed below, to use Advanced

C++ features. Do NOT rewrite the entire program, as there

is only 2 hours to complete the test.

If you think you find an implementation problem in the original

code, provide a fix - noting that there are no problems

deliberately inserted into the code by the instructor.

* Replace all arrays, with appropriate STL containers.

* Where possible, insert STL algorithms, lambda functions

and functors to replace existing logic.

* Use smart pointers where pointers are needed.

*/

#include <cstdio>

#include <cstdlib>

#include <climits>

using namespace std;

class Node

{

public:

int dest;

int weight;

Node* next;

Node() {}

Node(int d, int w)

{

dest = d;

weight = w;

next = NULL;

}

};

struct Adjacency

{

Node *head;

};

struct Graph

{

int capacity;

Adjacency* array;

Graph(int v)

{

capacity = v;

array = new Adjacency[capacity];

for (int i = 0; i < capacity; ++i)

array[i].head = NULL;

}

void addEdge(int src, int dest, int weight)

{

Node* newNode = new Node(dest, weight);

newNode->next = array[src].head;

array[src].head = newNode;

newNode = new Node(src, weight);

newNode->next = array[dest].head;

array[dest].head = newNode;

}

};

struct MinNode

{

int vert;

int dist;

MinNode(int a=0, int b=0)

{

vert = a;

dist = b;

}

};

class Minimum

{

public:

int size;

int capacity;

int *pos;

MinNode **array;

Minimum(int vert, int dist)

{

MinNode* minNode = new MinNode;

minNode->vert = vert;

minNode->dist = dist;

}

Minimum(int c)

{

pos = new int[c];

size = 0;

capacity = c;

array = new MinNode*[capacity];

}

void build(int idx)

{

int smallest, left, right;

smallest = idx;

left = 2 * idx + 1;

right = 2 * idx + 2;

if (left < size &&

array[left]->dist < array[smallest]->dist)

smallest = left;

if (right < size &&

array[right]->dist < array[smallest]->dist)

smallest = right;

if (smallest != idx)

{

MinNode *smallestNode = array[smallest];

MinNode *idxNode = array[idx];

pos[smallestNode->vert] = idx;

pos[idxNode->vert] = smallest;

swap(&array[smallest], &array[idx]);

build(smallest);

}

}

void swap(MinNode** a, struct MinNode** b)

{

MinNode* t = *a;

*a = *b;

*b = t;

}

int isEmpty()

{

return size == 0;

}

MinNode* findMinimum()

{

if (isEmpty())

return NULL;

MinNode* root = array[0];

MinNode* lastNode = array[size - 1];

array[0] = lastNode;

pos[root->vert] = size - 1;

pos[lastNode->vert] = 0;

--size;

build(0);

return root;

}

void decrease(int v, int dist)

{

int i = pos[v];

array[i]->dist = dist;

while (i && array[i]->dist < array[(i - 1) / 2]->dist)

{

pos[array[i]->vert] = (i - 1) / 2;

pos[array[(i - 1) / 2]->vert] = i;

swap(&array[i], &array[(i - 1) / 2]);

i = (i - 1) / 2;

}

}

bool isLess(int v)

{

if (pos[v] < size)

return true;

return false;

}

void printArr(int dist[], int n)

{

printf("Vertex Distance from Source ");

for (int i = 0; i < n; ++i)

printf("%d %d ", i, dist[i]);

}

};

void flodget(Graph* graph, int src)

{

int cap = graph->capacity;

int* dist = new int[cap];

Minimum* min = new Minimum(cap);

for (int v = 0; v < cap; ++v)

{

dist[v] = INT_MAX;

min->array[v] = new MinNode(v, dist[v]);

min->pos[v] = v;

}

min->array[src] = new MinNode(src, dist[src]);

min->pos[src] = src;

dist[src] = 0;

min->decrease(src, dist[src]);

min->size = cap;

while (!min->isEmpty())

{

MinNode* mnode = min->findMinimum();

int u = mnode->vert;

Node* pCrawl = graph->array[u].head;

while (pCrawl != NULL)

{

int v = pCrawl->dest;

if (min->isLess(v) && dist[u] != INT_MAX &&

pCrawl->weight + dist[u] < dist[v])

{

dist[v] = dist[u] + pCrawl->weight;

min->decrease(v, dist[v]);

}

pCrawl = pCrawl->next;

}

}

min->printArr(dist, cap);

}

void main()

{

int V = 9;

Graph* graph = new Graph(V);

graph->addEdge(0, 1, 4);

graph->addEdge(0, 7, 8);

graph->addEdge(1, 2, 8);

graph->addEdge(1, 7, 11);

graph->addEdge(2, 3, 7);

graph->addEdge(2, 8, 2);

graph->addEdge(2, 5, 4);

graph->addEdge(3, 4, 9);

graph->addEdge(3, 5, 14);

graph->addEdge(4, 5, 10);

graph->addEdge(5, 6, 2);

graph->addEdge(6, 7, 1);

graph->addEdge(6, 8, 6);

graph->addEdge(7, 8, 7);

flodget(graph, 0);

}

Explanation / Answer

we can refactor c++ program to reduce the dependencies.

for this we have to see for namespace collision, use inline fuction in the code, then break dependency chain by partioning.

all these things are done to reduce the time complexity

#include <cstdio>

#include <cstdlib>

#include <climits>

using namespace std;

class Node

{

public:

int dest;

int weight;

Node* next;

Node() {}

Node(int d, int w)

{

dest = d;

weight = w;

next = NULL;

}

};

struct Adjacency

{

Node *head;

};

struct Graph

{

int capacity;

Adjacency* array;

inline Graph(int v)

{

capacity = v;

array = new Adjacency[capacity];

for (int i = 0; i < capacity; ++i)

array[i].head = NULL;

}

inline void addEdge(int src, int dest, int weight)

{

Node* newNode = new Node(dest, weight);

newNode->next = array[src].head;

array[src].head = newNode;

newNode = new Node(src, weight);

newNode->next = array[dest].head;

array[dest].head = newNode;

}

};

struct MinNode

{

int vert;

int dist;

inline MinNode(int a=0, int b=0)

{

vert = a;

dist = b;

}

};

class Minimum

{

public:

int size;

int capacity;

int *pos;

MinNode **array;

Minimum(int vert, int dist)

{

MinNode* minNode = new MinNode;

minNode->vert = vert;

minNode->dist = dist;

}

Minimum(int c)

{

pos = new int[c];

size = 0;

capacity = c;

array = new MinNode*[capacity];

}

void build(int idx)

{

int smallest, left, right;

smallest = idx;

left = 2 * idx + 1;

right = 2 * idx + 2;

if (left < size &&

array[left]->dist < array[smallest]->dist)

smallest = left;

if (right < size &&

array[right]->dist < array[smallest]->dist)

smallest = right;

if (smallest != idx)

{

MinNode *smallestNode = array[smallest];

MinNode *idxNode = array[idx];

pos[smallestNode->vert] = idx;

pos[idxNode->vert] = smallest;

swap(&array[smallest], &array[idx]);

build(smallest);

}

}

void swap(MinNode** a, struct MinNode** b)

{

MinNode* t = *a;

*a = *b;

*b = t;

}

int isEmpty()

{

return size == 0;

}

MinNode* findMinimum()

{

if (isEmpty())

return NULL;

MinNode* root = array[0];

MinNode* lastNode = array[size - 1];

array[0] = lastNode;

pos[root->vert] = size - 1;

pos[lastNode->vert] = 0;

--size;

build(0);

return root;

}

void decrease(int v, int dist)

{

int i = pos[v];

array[i]->dist = dist;

while (i && array[i]->dist < array[(i - 1) / 2]->dist)

{

pos[array[i]->vert] = (i - 1) / 2;

pos[array[(i - 1) / 2]->vert] = i;

swap(&array[i], &array[(i - 1) / 2]);

i = (i - 1) / 2;

}

}

bool isLess(int v)

{

if (pos[v] < size)

return true;

return false;

}

void printArr(int dist[], int n)

{

printf("Vertex Distance from Source ");

for (int i = 0; i < n; ++i)

printf("%d %d ", i, dist[i]);

}

};

inline void flodget(Graph* graph, int src)

{

int cap = graph->capacity;

int* dist = new int[cap];

Minimum* min = new Minimum(cap);

for (int v = 0; v < cap; ++v)

{

dist[v] = INT_MAX;

min->array[v] = new MinNode(v, dist[v]);

min->pos[v] = v;

}

min->array[src] = new MinNode(src, dist[src]);

min->pos[src] = src;

dist[src] = 0;

min->decrease(src, dist[src]);

min->size = cap;

while (!min->isEmpty())

{

MinNode* mnode = min->findMinimum();

int u = mnode->vert;

Node* pCrawl = graph->array[u].head;

while (pCrawl != NULL)

{

int v = pCrawl->dest;

if (min->isLess(v) && dist[u] != INT_MAX &&

pCrawl->weight + dist[u] < dist[v])

{

dist[v] = dist[u] + pCrawl->weight;

min->decrease(v, dist[v]);

}

pCrawl = pCrawl->next;

}

}

min->printArr(dist, cap);

}

void main()

{

int V = 9;

Graph* graph = new Graph(V);

graph->addEdge(0, 1, 4);

graph->addEdge(0, 7, 8);

graph->addEdge(1, 2, 8);

graph->addEdge(1, 7, 11);

graph->addEdge(2, 3, 7);

graph->addEdge(2, 8, 2);

graph->addEdge(2, 5, 4);

graph->addEdge(3, 4, 9);

graph->addEdge(3, 5, 14);

graph->addEdge(4, 5, 10);

graph->addEdge(5, 6, 2);

graph->addEdge(6, 7, 1);

graph->addEdge(6, 8, 6);

graph->addEdge(7, 8, 7);

flodget(graph, 0);

}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.