I am having a problem building a graph from a a given text. void GraphL :: build
ID: 3838420 • Letter: I
Question
I am having a problem building a graph from a a given text.
void GraphL :: buildGraph(ifstream & inFile) {
.....
}
my header file looks is below, the nodedata class have a function named setData to read from
file and set to data. Can anyone help me please. Thank you in advance
#include <iostream>
#include "nodedata.h"
using namespace std;
class GraphL {
const static int MAXNODES = 100; // number of maximum nodes in the graph
public:
GraphL(); // Default constructor
~GraphL(); // Destructor
void buildGraph(ifstream &inFile); // builds up graph node information
// and adjacency list of edges between
// each node reading from a data file
void displayGraph() const; // Display contents of graph
void depthFirstSearch(); // Performs depth first traversal
private:
struct EdgeNode; // forward reference for the compiler
struct GraphNode { // structs used for simplicity,
//use classes if desired
EdgeNode* edgeHead; // head of the list of edges
NodeData* data; // data information about each node
bool visited;
};
struct EdgeNode {
int adjGraphNode; // subscript of the adjacent graph node
EdgeNode* nextEdge;
};
GraphNode *nodes[MAXNODES + 1]; // array of nodes
int size; // number of size in the graph
bool insertEdgeHelper(const int from, const int to); // Helps to inset edge
void depthFirstSearchHelper(int v); // Helps to do dfs
};
Explanation / Answer
Please find the below missing code which serves your purpose
******************
void GraphL :: buildGraph(ifstream & inFile) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
}
*****************
You can find the below whole working code and the output
*******************
#include <stdio.h>
#include <stdlib.h>
// A structure to represent an adjacency list node
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
// A structure to represent an adjacency list
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf(" Adjacency list of vertex %d head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf(" ");
}
}
// Driver program to test above functions
int main()
{
// create the graph given in above fugure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// print the adjacency list representation of the above graph
printGraph(graph);
return 0;
}
*****************
OUTPUT
*************
*************
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.