Homework SourseIm having trouble figuring out how to code these sections fo
I\'m having trouble figuring out how to code these sections for an assignment... (Sections 4 and 5 are in a .cpp file without a main. Section 6 is in a seperate file that\'s only purpose is to test using a main method.) For further information, a link to the assignment can be found here - http://www.cs.ecu.edu/~karl/2530/fall16/Assn/Assn6/assn6.html
4. Reading the Graph
Document and define a function to read a graph. Use the adjacency list representation. Only store the graph once.
5. Printing a Graph
Document and define a function to print a graph. .
6. Testing
Test reading and echoing the graph. Do not move on until you are satisfied that this much works.
(Testing is done in the main method, not the .cpp file).
How would I code this using the following code?
#include <iostream>
using namespace std;
struct Edge{
int vertexNumber;
int weight;
struct Edge* next;
Edge( int vn, int wgt, struct Edge* nxt ){
vertexNumber = vn;
weight = wgt;
next = nxt;
};
};
struct Vertex{
struct Edge* adjacencyList;
double shortestDistance;
int vertexNumber;
Vertex(){
vertexNumber = shortestDistance = -1;
adjacencyList = NULL;
}
};
struct Graph{
int nVertices;
int nEdges;
struct Vertex* vertices;
Graph( int nVert ){
vertices = new struct Vertex[nVert];
nEdges = 0;
}
};
typedef struct Edge Edge;
typedef struct Vertex Vertex;
typedef struct Graph Graph;
int main(){
}
| 4. Reading the Graph Document and define a function to read a graph. Use the adjacency list representation. Only store the graph once. |
| 5. Printing a Graph Document and define a function to print a graph. . |
| 6. Testing Test reading and echoing the graph. Do not move on until you are satisfied that this much works. (Testing is done in the main method, not the .cpp file). |
Solution
4)
// A C Program to demonstrate adjacency list representation of graphs
#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;
}
5) to print use this code in c
// C++ program to print all paths from a source to destination.
#include<iostream>
#include <list>
using namespace std;
// A directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices in graph
list<int> *adj; // Pointer to an array containing adjacency lists
// A recursive function used by printAllPaths()
void printAllPathsUtil(int , int , bool [], int [], int &);
public:
Graph(int V); // Constructor
void addEdge(int u, int v);
void printAllPaths(int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v); // Add v to u’s list.
}
// Prints all paths from \'s\' to \'d\'
void Graph::printAllPaths(int s, int d)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
// Create an array to store paths
int *path = new int[V];
int path_index = 0; // Initialize path[] as empty
// Initialize all vertices as not visited
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print all paths
printAllPathsUtil(s, d, visited, path, path_index);
}
// A recursive function to print all paths from \'u\' to \'d\'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[],
int path[], int &path_index)
{
// Mark the current node and store it in path[]
visited[u] = true;
path[path_index] = u;
path_index++;
// If current vertex is same as destination, then print
// current path[]
if (u == d)
{
for (int i = 0; i<path_index; i++)
cout << path[i] << \" \";
cout << endl;
}
else // If current vertex is not destination
{
// Recur for all the vertices adjacent to current vertex
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (!visited[*i])
printAllPathsUtil(*i, d, visited, path, path_index);
}
// Remove current vertex from path[] and mark it as unvisited
path_index--;
visited[u] = false;
}
// Driver program
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3);
int s = 2, d = 3;
cout << \"Following are all different paths from \" << s
<< \" to \" << d << endl;
g.printAllPaths(s, d);
return 0;
}
6)
echo “set samples 2000;plot abs(sin(x));rep abs(cos(x))”|gnuplot -persist
| // A C Program to demonstrate adjacency list representation of graphs #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; } 5) to print use this code in c // C++ program to print all paths from a source to destination. #include<iostream> #include <list> using namespace std; // A directed graph using adjacency list representation class Graph { int V; // No. of vertices in graph list<int> *adj; // Pointer to an array containing adjacency lists // A recursive function used by printAllPaths() void printAllPathsUtil(int , int , bool [], int [], int &); public: Graph(int V); // Constructor void addEdge(int u, int v); void printAllPaths(int s, int d); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int u, int v) { adj[u].push_back(v); // Add v to u’s list. } // Prints all paths from \'s\' to \'d\' void Graph::printAllPaths(int s, int d) { // Mark all the vertices as not visited bool *visited = new bool[V]; // Create an array to store paths int *path = new int[V]; int path_index = 0; // Initialize path[] as empty // Initialize all vertices as not visited for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to print all paths printAllPathsUtil(s, d, visited, path, path_index); } // A recursive function to print all paths from \'u\' to \'d\'. // visited[] keeps track of vertices in current path. // path[] stores actual vertices and path_index is current // index in path[] void Graph::printAllPathsUtil(int u, int d, bool visited[], int path[], int &path_index) { // Mark the current node and store it in path[] visited[u] = true; path[path_index] = u; path_index++; // If current vertex is same as destination, then print // current path[] if (u == d) { for (int i = 0; i<path_index; i++) cout << path[i] << \" \"; cout << endl; } else // If current vertex is not destination { // Recur for all the vertices adjacent to current vertex list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) if (!visited[*i]) printAllPathsUtil(*i, d, visited, path, path_index); } // Remove current vertex from path[] and mark it as unvisited path_index--; visited[u] = false; } // Driver program int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3); g.addEdge(2, 0); g.addEdge(2, 1); g.addEdge(1, 3); int s = 2, d = 3; cout << \"Following are all different paths from \" << s << \" to \" << d << endl; g.printAllPaths(s, d); return 0; } 6) echo “set samples 2000;plot abs(sin(x));rep abs(cos(x))”|gnuplot -persist |
