In c, please implement the following 3 functions to the code below is_reachable(graph_t * g, int...
In c, please implement the following 3 functions to the code below
-
is_reachable(graph_t * g, int source, int dest) returns 0 if I can reach the destination from source, -1 otherwise ( using BFS)
-
has_cycle(graph_t * g) returns 0 if there is a cycle in the graph, -1 otherwise (using BFS or DFS)
-
print_path(graph_t * g, int source, int dest) prints any path from source to destination if there exists one (Choose either BFS or DFS, typically DFS is much simpler)
// - Do not change any of the function declarations (i.e.
graph_t* create_graph() should not have additional arguments)
// ==================================================
#ifndef MYGRAPH_H
#define MYGRAPH_H
typedef struct neighbor{
int data;
struct neighbor * next;
}neighbor_t;
// Create a node data structure to store data
typedef struct node{
int data;
struct node *next;
struct neighbor * neighbor;
}node_t;
// Create a graph data structure
typedef struct graph{
int numNodes;
int numEdges;
node_t* nodes; //an array of nodes storing all of our nodes.
}graph_t;
// Creates a graph
graph_t* create_graph(){
// Modify the body of this function as needed.
graph_t* myGraph= (graph_t *)malloc(sizeof(graph_t));
myGraph->numNodes = 0;
myGraph->numEdges = 0;
myGraph->nodes = NULL;
return myGraph;
}
// Graph Empty
// Check if the graph is empty
// Returns 0 if true (The graph is completely empty, i.e. numNodes
== 0 )
// Returns -1 if false (the graph has at least one node)
int graph_empty(graph_t* g){
if(g->numNodes == 0){
return 0;
}
return -1;
}
// Adds a new node withe the correspoding item in the
graph.
// Returns a -1 if the operation fails (otherwise returns 0 on
success).
// (i.e. the memory allocation for a new node failed).
// Duplicates nodes should not be added. For a duplicate node
returns 0.
int graph_add_node(graph_t* g, int item){
node_t* newNode = (node_t *)
malloc(sizeof(node_t));
if(newNode == NULL)
return -1;
newNode->data = item;
newNode->neighbor =
NULL;
newNode->next = NULL;
g->numNodes++;
if(g->nodes == NULL)
g->nodes =
newNode;
else
{
node_t *temp =
g->nodes;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next =
newNode;
}
return 0;
}
// Removes the node from the graph and the corresponding edges
connected
// to the node.
// Returns a -1 if the operation fails (otherwise returns 0 on
success).
// (the node to be removed doesn't exist in the graph).
int graph_remove_node(graph_t* g, int item){
if(g->nodes == NULL)
return -1;
node_t *temp =
g->nodes;
node_t *prev = NULL;
while(temp != NULL &&
temp->data != item)
{
prev =
temp;
temp =
temp->next;
}
if(temp == NULL)
return -1;
prev->next =
temp->next;
g->numNodes--;
free(temp);
return 0;
}
//Adds an edge from source to destination.
//If source or desination is not found in the graph returns
-1.
//Otherwise it returns 0 ( even for trying to add a duplicate edge
)
int graph_add_edge(graph_t * g, int source, int destination){
if(g == NULL)
return
-1;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != source)
{
temp =
temp->next;
}
if(temp == NULL)
return -1;
neighbor_t *temp_n =
temp->neighbor;
neighbor_t* new_neighbor =
(neighbor_t *) malloc(sizeof(neighbor_t));
if(new_neighbor == NULL)
return -1;
new_neighbor->data =
destination;
new_neighbor->next = NULL;
if(temp_n == NULL)
{
temp_n =
new_neighbor;
}
else
{
while(temp_n->next != NULL)
{
temp_n = temp_n->next;
}
temp_n->next
= new_neighbor;
}
g->numEdges++;
return -1;
}
//Removes an edge from source to destination.
//If source or desination is not found in the graph returns
-1.
//If no such edge exists also returns -1.
//Otherwise it returns 0
int graph_remove_edge(graph_t * g, int source, int
destination){
if(g == NULL)
return
-1;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != source)
{
temp =
temp->next;
}
if(temp == NULL)
return -1;
neighbor_t *temp_n =
temp->neighbor;
neighbor_t *prev_n = NULL;
if(temp_n == NULL)
{
return -1;
}
while(temp_n != NULL &&
temp_n->data != destination)
{
prev_n =
temp;
temp_n =
temp_n->next;
}
prev_n->next =
temp_n->next;
free(temp_n);
g->numEdges--;
return -1;
}
//Returns 0 if the node with value is in the graph, otherwise
returns -1;
int contains_node( graph_t * g, int value){
if(g->nodes == NULL)
return -1;
node_t *temp =
g->nodes;
while(temp->next != NULL)
{
if(temp->data
== value)
return 0;
}
return -1;
}
//Returns 0 if an edge from source to destination exists, -1
otherwise.
int contains_edge( graph_t * g, int source, int destintaion){
if(g == NULL)
return
-1;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != source)
{
temp =
temp->next;
}
if(temp == NULL)
return -1;
neighbor_t *temp_n =
temp->neighbor;
if(temp_n == NULL)
{
return -1;
}
while(temp_n != NULL &&
temp_n->data != destination)
{
temp_n =
temp_n->next;
}
if(temp_n == NULL)
return -1;
return 0;
}
//Returns an int array of all the neighbors of the node with
data=value.
int * getNeighbors( graph_t * g, int value ){
if(g->nodes == NULL)
return
NULL;
node_t *temp = g->nodes;
while(temp != NULL &&
temp->data != value)
{
temp =
temp->next;
}
if(temp == NULL ||
temp->neighbor == NULL)
return NULL;
neighbor_t *temp_n = temp->neighbor;
while(temp_n != NULL)
{
return
temp_n->data;
}
return NULL;
}
// Returns the number of neighbors for value.
int numNeighbors( graph_t * g, int value ){
if(g->nodes == NULL)
return 0;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != value)
{
temp =
temp->next;
}
if(temp == NULL ||
temp->neighbor == NULL)
return 0;
int neighbor_count = 0;
neighbor_t *temp_n = temp->neighbor;
while(temp_n != NULL)
{
neighbor_count++;
temp_n =
temp_n->next;
}
return neighbor_count;
}
// Prints the the graph using BFS
// For NULL or empty graph it should print nothing.
void graph_print(graph_t * g){
if(g == NULL)
return;
node_t * temp = g->nodes;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
// Graph Size
// Returns the number of nodes in the graph
unsigned int graph_num_nodes(graph_t* g){
return g->numNodes;
}
// Graph Size
// Returns the number of edges in the graph
unsigned int graph_num_edges(graph_t* g){
return g->numEdges;
}
// Free graph
// Removes a graph and ALL of its elements from memory.
// This should be called before the proram terminates.
void free_graph(graph_t* g){
if(g == NULL)
return;
node_t *temp = g->nodes;
while(temp != NULL)
{
prev = temp;
temp = temp->next;
free(prev);
}
free(g);
}
#endif
Homework Answers
// ==================================================
#ifndef MYGRAPH_H
#define MYGRAPH_H
typedef struct neighbor{
int data;
struct neighbor * next;
}neighbor_t;
// Create a node data structure to store data
typedef struct node{
int data;
struct node *next;
struct neighbor * neighbor;
}node_t;
// Create a graph data structure
typedef struct graph{
int numNodes;
int numEdges;
node_t* nodes; //an array of nodes storing all of our nodes.
}graph_t;
// Creates a graph
graph_t* create_graph(){
// Modify the body of this function as needed.
graph_t* myGraph= (graph_t *)malloc(sizeof(graph_t));
myGraph->numNodes = 0;
myGraph->numEdges = 0;
myGraph->nodes = NULL;
return myGraph;
}
// Graph Empty
// Check if the graph is empty
// Returns 0 if true (The graph is completely empty, i.e. numNodes
== 0 )
// Returns -1 if false (the graph has at least one node)
int graph_empty(graph_t* g){
if(g->numNodes == 0){
return 0;
}
return -1;
}
// Adds a new node withe the correspoding item in the
graph.
// Returns a -1 if the operation fails (otherwise returns 0 on
success).
// (i.e. the memory allocation for a new node failed).
// Duplicates nodes should not be added. For a duplicate node
returns 0.
int graph_add_node(graph_t* g, int item){
node_t* newNode = (node_t *)
malloc(sizeof(node_t));
if(newNode == NULL)
return -1;
newNode->data = item;
newNode->neighbor =
NULL;
newNode->next = NULL;
g->numNodes++;
if(g->nodes == NULL)
g->nodes =
newNode;
else
{
node_t *temp =
g->nodes;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next =
newNode;
}
return 0;
}
// Removes the node from the graph and the corresponding edges
connected
// to the node.
// Returns a -1 if the operation fails (otherwise returns 0 on
success).
// (the node to be removed doesn't exist in the graph).
int graph_remove_node(graph_t* g, int item){
if(g->nodes == NULL)
return -1;
node_t *temp =
g->nodes;
node_t *prev = NULL;
while(temp != NULL &&
temp->data != item)
{
prev =
temp;
temp =
temp->next;
}
if(temp == NULL)
return -1;
prev->next =
temp->next;
g->numNodes--;
free(temp);
return 0;
}
//Adds an edge from source to destination.
//If source or desination is not found in the graph returns
-1.
//Otherwise it returns 0 ( even for trying to add a duplicate edge
)
int graph_add_edge(graph_t * g, int source, int destination){
if(g == NULL)
return
-1;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != source)
{
temp =
temp->next;
}
if(temp == NULL)
return -1;
neighbor_t *temp_n =
temp->neighbor;
neighbor_t* new_neighbor =
(neighbor_t *) malloc(sizeof(neighbor_t));
if(new_neighbor == NULL)
return -1;
new_neighbor->data =
destination;
new_neighbor->next = NULL;
if(temp_n == NULL)
{
temp_n =
new_neighbor;
}
else
{
while(temp_n->next != NULL)
{
temp_n = temp_n->next;
}
temp_n->next
= new_neighbor;
}
g->numEdges++;
return -1;
}
//Removes an edge from source to destination.
//If source or desination is not found in the graph returns
-1.
//If no such edge exists also returns -1.
//Otherwise it returns 0
int graph_remove_edge(graph_t * g, int source, int
destination){
if(g == NULL)
return
-1;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != source)
{
temp =
temp->next;
}
if(temp == NULL)
return -1;
neighbor_t *temp_n =
temp->neighbor;
neighbor_t *prev_n = NULL;
if(temp_n == NULL)
{
return -1;
}
while(temp_n != NULL &&
temp_n->data != destination)
{
prev_n =
temp;
temp_n =
temp_n->next;
}
prev_n->next =
temp_n->next;
free(temp_n);
g->numEdges--;
return -1;
}
//Returns 0 if the node with value is in the graph, otherwise
returns -1;
int contains_node( graph_t * g, int value){
if(g->nodes == NULL)
return -1;
node_t *temp =
g->nodes;
while(temp->next != NULL)
{
if(temp->data
== value)
return 0;
}
return -1;
}
//Returns 0 if an edge from source to destination exists, -1
otherwise.
int contains_edge( graph_t * g, int source, int destintaion){
if(g == NULL)
return
-1;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != source)
{
temp =
temp->next;
}
if(temp == NULL)
return -1;
neighbor_t *temp_n =
temp->neighbor;
if(temp_n == NULL)
{
return -1;
}
while(temp_n != NULL &&
temp_n->data != destination)
{
temp_n =
temp_n->next;
}
if(temp_n == NULL)
return -1;
return 0;
}
//Returns an int array of all the neighbors of the node with
data=value.
int * getNeighbors( graph_t * g, int value ){
if(g->nodes == NULL)
return
NULL;
node_t *temp = g->nodes;
while(temp != NULL &&
temp->data != value)
{
temp =
temp->next;
}
if(temp == NULL ||
temp->neighbor == NULL)
return NULL;
neighbor_t *temp_n = temp->neighbor;
while(temp_n != NULL)
{
return
temp_n->data;
}
return NULL;
}
// Returns the number of neighbors for value.
int numNeighbors( graph_t * g, int value ){
if(g->nodes == NULL)
return 0;
node_t *temp =
g->nodes;
while(temp != NULL &&
temp->data != value)
{
temp =
temp->next;
}
if(temp == NULL ||
temp->neighbor == NULL)
return 0;
int neighbor_count = 0;
neighbor_t *temp_n = temp->neighbor;
while(temp_n != NULL)
{
neighbor_count++;
temp_n =
temp_n->next;
}
return neighbor_count;
}
// Prints the the graph using BFS
// For NULL or empty graph it should print nothing.
void graph_print(graph_t * g){
if(g == NULL)
return;
node_t * temp = g->nodes;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
// Graph Size
// Returns the number of nodes in the graph
unsigned int graph_num_nodes(graph_t* g){
return g->numNodes;
}
// Graph Size
// Returns the number of edges in the graph
unsigned int graph_num_edges(graph_t* g){
return g->numEdges;
}
// Free graph
// Removes a graph and ALL of its elements from memory.
// This should be called before the proram terminates.
void free_graph(graph_t* g){
if(g == NULL)
return;
node_t *temp = g->nodes;
while(temp != NULL)
{
prev = temp;
temp = temp->next;
free(prev);
}
free(g);
}
#endif
int is_reachable(graph_t * g, int source, int dest) {
node_t * temp = g->nodes;
bool isSourceFound = false;
while(temp != NULL)
{
if (temp->data == source && !isSourceFound) {
isSourceFound = true;
}
if (isSourceFound) {
if (temp->data == dest) {
return 0;
}
}
temp = temp->next;
}
return -1;
}
int has_cycle(graph_t * g) {
node_t * temp = g->nodes;
node_t * nextTemp = g->nodes->next->next;
while(temp != NULL && temp != g->nodes)
{
if (nextTemp == NULL) {
return -1;
}
if (temp->data == nextTemp->data) {
return 0;
break;
}
temp = temp->next;
nextTemp = nextTemp->next->next;
}
return -1;
}
void print_path(graph_t * g, int source, int dest) {
node_t * temp = g->nodes;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
Add Answer to:
In c, please implement the following 3 functions to the
code below
is_reachable(graph_t * g, int...
Improve the speed of public T get(int i) by having it work backward from the end...
Improve the speed of public T get(int i) by having it work backward from the end of the array if you attempt to get a member which is closer to the end than the start. This improvement will be tested through timing tests on large lists. The method should still return null if i is not a valid index. Code import java.util.Iterator; public class DLList<T> implements Iterable<T> { private static class Node<T> { public Node<T> prev, next;...
PROMPT: Consider a graph G. A connected component is a maximal subset of nodes that induces a connected sub graph. It’s maximal in the sense that you cannot add a node with the resulting induced sub g...
PROMPT:
Consider a graph G. A connected component is a maximal subset of
nodes that induces a connected sub graph. It’s maximal in the sense
that you cannot add a node with the resulting induced sub graph
remaining connected.The following function
numComponents returns the number of connected
components in an undirected graph.
QUESTION:
What is the time complexity for this function? The time
complexity should be a function of the number of nodes |V| and the
number of edges |E|....
Class PNode { //JAVA COMPLETE TODO Marked answers // Basic node int deg; // The degree of a term ...
class PNode { //JAVA COMPLETE TODO Marked answers // Basic node int deg; // The degree of a term float coeff; // The coefficient of a term PNode next; PNode(int d, float c) { // Constructor: builds a node with given data next = null; deg = d; coeff = c; } PNode(int d, float c, PNode n) { // Constructor: builds a node with given reference next = n; deg = d; coeff = c; } // Basic node...
This is a code for linked list, it is about adding a node in the middle...
This is a code for linked list,
it is about adding a node in the middle of a list, I am really
confused why int i = 2? can't it be 0?
Add to the Middle • Allocate memory and store data for new node Traverse to node just before the required position of new node Change next pointers to include new node in between struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; struct node *temp head; for(int...
This program uses C++. This program reads in a line from the user and prints it...
This program uses C++. This program reads in a line from the user and prints it out in a certain format. An example would be Input: 1 2 3 4 5 would result Output: [{1}, {2}, {3}, {4}, {5}]. When quotations marks are added into the input the format becomes different. For instance, Input 1 2 "3 4 5" would result in [{1}, {2}, {3 4 5}]. When I ad multiple quotation marks into the input, it will only use...
please answer all the question in C++ language Section 4 (29 points) Missing Code doublyLinkedList::isEmptyListo) return...
please answer all the question in C++ language
Section 4 (29 points) Missing Code doublyLinkedList::isEmptyListo) return (head == NULL); 30. Consider the accompanying statements. The operation returns true if the list is empty: otherwise, it returns false. The missing code is struct node Type int value; nodeType *link; node Type head, *, *, *newNode; newNode = new node Type: 31. What is the effect of the following statement? newNode->value = 23; 32. What is the purpose of the following code?...
Create the code for GraphAlgorithm.prim() so that the MST main routine can run properly public class...
Create the code for GraphAlgorithm.prim() so that the MST main routine can run properly public class MSTmain { public static void main(String[] args) { MyGraph G = new MyGraph(6); G.insertEdge(0, 2, 5); G.insertEdge(2, 0, 5); G.insertEdge(1, 0, 1); G.insertEdge(0, 1, 1); G.insertEdge(0, 5, 8); G.insertEdge(5, 0, 8); G.insertEdge(1, 2, 7); G.insertEdge(2, 1, 7); G.insertEdge(1, 3, 5); G.insertEdge(3, 1, 5); G.insertEdge(2, 3, 1); G.insertEdge(3, 2, 1); G.insertEdge(1, 5, 9); G.insertEdge(5, 1, 9); G.insertEdge(3, 4, 3); G.insertEdge(4, 3, 3); G.insertEdge(4, 2, 7);...
Using the provided table interface table.h and the sample linked list code linkedList.c, complete an implementation...
Using the provided table interface table.h and the sample linked list code linkedList.c, complete an implementation of the Table ADT. Make sure that you apply the concepts of design by contract (DbC) to your implementation. Once you have fully implemented the table, create a main.c file that implements a testing framework for your table. Your table implementation must ensure that values inserted are unique, and internally sorted within a linked list. table.h #ifndef _TABLE_H #define _TABLE_H //----------------------------------------------------------------------------- // CONSTANTS AND...
Having code issues wth my C++ program. My program checks if two binary trees are similar...
Having code issues wth my C++ program. My program checks if two binary trees are similar and if they're not they return false. My program is return true with different binary trees. Could use some help thanks #include <iostream> #include <string> using namespace std; //Struct of Nodes struct BinarySearchTree { int data; BinarySearchTree *left; BinarySearchTree *right; }; // Inserting nodes into BST BinarySearchTree* insert( BinarySearchTree* node, int val) { if (node == NULL) { BinarySearchTree *newNode = new BinarySearchTree(); newNode->data...
I need help with todo line please public class LinkedList { private Node head; public LinkedList()...
I need help with todo line please public class LinkedList { private Node head; public LinkedList() { head = null; } public boolean isEmpty() { return head == null; } public int size() { int count = 0; Node current = head; while (current != null) { count++; current = current.getNext(); } return count; } public void add(int data) { Node newNode = new Node(data); newNode.setNext(head); head = newNode; } public void append(int data) { Node newNode = new Node(data);...
PROMPT:
Consider a graph G. A connected component is a maximal subset of
nodes that induces a connected sub graph. It’s maximal in the sense
that you cannot add a node with the resulting induced sub graph
remaining connected.The following function
numComponents returns the number of connected
components in an undirected graph.
QUESTION:
What is the time complexity for this function? The time
complexity should be a function of the number of nodes |V| and the
number of edges |E|....
This is a code for linked list,
it is about adding a node in the middle of a list, I am really
confused why int i = 2? can't it be 0?
Add to the Middle • Allocate memory and store data for new node Traverse to node just before the required position of new node Change next pointers to include new node in between struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; struct node *temp head; for(int...
please answer all the question in C++ language
Section 4 (29 points) Missing Code doublyLinkedList::isEmptyListo) return (head == NULL); 30. Consider the accompanying statements. The operation returns true if the list is empty: otherwise, it returns false. The missing code is struct node Type int value; nodeType *link; node Type head, *, *, *newNode; newNode = new node Type: 31. What is the effect of the following statement? newNode->value = 23; 32. What is the purpose of the following code?...
Most questions answered within 3 hours.
-
Using MARS simulator, write MIPS programs according to
the following scenarios: Receive a positive integer number...
asked 46 minutes ago -
An object in front of a concave mirror has a real image that is
11.5 cm...
asked 1 hour ago -
Consider the reaction, C3 H8 + O2 --> CO2 + H2O. How many
moles of O2...
asked 2 hours ago -
You and your opponent both roll a fair die. If you both roll the
same number,...
asked 3 hours ago -
In a study of the accuracy of fast food drive-through orders,
Restaurant A had 257 accurate...
asked 3 hours ago -
Identify and describe in detail the four categories of
institutions that could be included in a...
asked 3 hours ago -
In python
class Customer:
def __init__(self, customer_id, last_name, first_name, phone_number, address):
self._customer_id = int(customer_id)
self._last_name =...
asked 3 hours ago -
What is an example of a limitation in implementing a new
ERP system and how it...
asked 3 hours ago -
In a section of 9.7cm of an artery with a radius of 2.6mm there
is a...
asked 3 hours ago -
the two carboxylic acid groups of aspartic acid have different
acidities with pKa values of 2.1...
asked 3 hours ago -
Would CuCO3 aqueous salt combined with calcium chloride
form a solid precipitate? If so, what would...
asked 3 hours ago -
How do ECM Solutions assist in embedding a culture of continuous
improvement in an organization? (Project...
asked 3 hours ago