Time limit: 500ms
Memory limit: 256mb
Description:
Complete graph operations as follows:
adjacent(G, u, v): tests whether there is an edge from the vertex u to the vertex v;
neighbors(G, u): lists all vertices v such that there is an edge from the vertex u to the vertex v, i.e., out-neighbors of u;
add_vertex(G, u): adds the vertex u, if it is not there;
add_edge(G, u, v): adds an edge from the vertex u to the vertex v, if it is not there;(If u or v are not already inserted, please add vertex u and add vertex v, too)
remove_edge(G, u, v): removes the edge from the vertex u to the vertex v, if it is there;
The exact number of nodes in the graph is unknown. You need to use a hash table with linear probing to store nodes.
-------------------------Copy the following code, complete it and submit-------------------------
/*
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
int element;
struct node* prev;
struct node* next;
}listNode;
typedef struct LinkedList {
listNode* head;
listNode* tail;
}llist;
//Create the initial LinkedList with only head node and tail node
llist* createList()
{
//Allocate memory for list L
llist* L = (llist*)malloc(sizeof(llist));
//Allocate memory for node L.head and node L.tail
listNode* head = (listNode*)malloc(sizeof(listNode));
listNode* tail = (listNode*)malloc(sizeof(listNode));
L->head = head;
L->tail = tail;
L->head->prev = NULL;
L->head->next = L->tail;
L->tail->prev = L->head;
L->tail->next = NULL;
return L;
}
//Search a linkedList to return the node of the key we are searching for
listNode* ListSearch(llist* L, int key)
{
listNode* node = L->head->next;
while (node != L->tail)
{
if (node->element == key)
{
return node;
}
node = node->next;
}
return NULL;
}
//Insert an key 'e' in the back of the LinkedList
void linkedlist_insert(llist* L, int element)
{
listNode* ulast = L->tail->prev;
//listNode unew < -allocate a new node from memory
listNode* unew = (listNode*)malloc(sizeof(listNode));
unew->element = element;
unew->prev = ulast;
unew->next = L->tail;
ulast->next = unew;
L->tail->prev = unew;
}
//Insert an key after node "p" with value "e"
void insertInPlace(llist* L, listNode* p, int element)
{
//listNode unew < -allocate a new node from memory
listNode* unew = (listNode*)malloc(sizeof(listNode));
unew->element = element;
unew->prev = p;
listNode* q = p->next;
unew->next = q;
p->next = unew;
q->prev = unew;
}
//Delete the element of node p(through p node's address)
void linkedlist_delete(llist* L, listNode* p)
{
listNode* Upred = p->prev;
listNode* Usucc = p->next;
Upred->next = Usucc;
Usucc->prev = Upred;
free(p);
}
//Display each element in the LinkedList
void display(llist* L) {
listNode* temp = L->head;
while (temp != NULL) {
if (temp == L->head) {
printf("head<->");
}
else if (temp == L->tail) {
printf("tail\n");
}
else {
printf("%d<->", temp->element);
}
temp = temp->next;
}
}
// Definition of the hash table node for linear probing
typedef struct hash_node {
int vertex; // the vertex value
llist* adj_list;
} hash_node;
// Definition of the graph ADT
typedef struct graph {
int num_vertices; // number of vertices in the graph
hash_node* nodes; // array of hash table nodes, one for each vertex
} graph;
// Create a new hash table node with a given vertex value
hash_node* new_hash_node(int vertex) {
hash_node* node = (hash_node*) malloc(sizeof(hash_node));
node->vertex = vertex;
node->adj_list = createList();
return node;
}
// Create a new graph with n vertices
graph* new_graph(int n) {
graph* G = (graph*) malloc(sizeof(graph));
G->num_vertices = n;
G->nodes = (hash_node*) malloc(n * sizeof(hash_node));
int i;
for (i = 0; i < n; i++) {
G->nodes[i].vertex = -1; // mark the node as empty
}
return G;
}
// Hash function to map a vertex value to a slot in the hash table
int hash(int vertex, int n) {
return vertex % n;
}
int hash_search(graph* G, int u){
// Find an empty slot in the hash table using linear probing
int index = hash(u, G->num_vertices);
int count_move = 0;
while (G->nodes[index].vertex != -1 && G->nodes[index].vertex != u && count_move < G->num_vertices) {
index = (index + 1) % G->num_vertices;
count_move++;
}
if(count_move >= G->num_vertices){
return -100;
}
else{
return index;
}
}
// Add a vertex u to the graph G, if it is not there
void add_vertex(graph* G, int u) {
// write down your code here
}
// Add an edge from vertex u to vertex v in the graph G, if it is not there
void add_edge(graph* G, int u, int v) {
// write down your code here
}
// Remove the edge from vertex u to vertex v in the graph G, if it is there
void remove_edge(graph* G, int u, int v) {
// write down your code here
}
// Test whether there is an edge from vertex u to vertex v
int adjacent(graph* G, int u, int v) {
// write down your code here
}
// Lists all vertices v such that there is an edge from the vertex u to the vertex v, i.e., out-neighbors of u
void neighbors(graph* G, int u) {
// write down your code here
}
void print_graph(graph* G){
for(int i = 0; i < G->num_vertices; i++){
if (G->nodes[i].vertex == -1) {
continue;
}
else{
printf("%d<->%d: ", i,
G->nodes[i].vertex);
// Print the adjacency list of vertex u
display(G->nodes[i].adj_list);
}
}
}
int main() {
int n, m;
//Enter the number of vertices in the hash table(max number, not practical number):
scanf("%d", &n);
graph* G = new_graph(n);
int u, v;
int add_nodes_number;
scanf("%d", &add_nodes_number);
for(int i = 0; i < add_nodes_number; i++){
scanf("%d", &u);
add_vertex(G, u);
}
//Enter the number of edges(practical number) to add
scanf("%d", &m);
//Enter the edges (u, v):
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
add_edge(G, u, v);
}
int test_edge_exists_number;
scanf("%d", &test_edge_exists_number);
//Enter the vertices to test (u, v):
for(int i = 0; i < test_edge_exists_number; i++){
scanf("%d%d", &u, &v);
if (adjacent(G, u, v)) {
printf("There is an edge from vertex %d to vertex %d\n", u, v);
} else {
printf("There is no edge from vertex %d to vertex %d\n", u, v);
}
}
int output_neighbor_number;
scanf("%d", &output_neighbor_number);
for(int i = 0; i < output_neighbor_number; i++){
scanf("%d", &u);
neighbors(G, u);
}
int remove_edge_exists_number;
scanf("%d", &remove_edge_exists_number);
//Enter the edges to remove (u, v):
for(int i = 0; i < remove_edge_exists_number; i++){
scanf("%d%d", &u, &v);
remove_edge(G, u, v);
}
printf("Final graph:\n");
print_graph(G);
return 0;
}
-------------------------------------------End of Code-------------------------------------------
Input:
The number of vertices in the hash table(max number, not practical number) as n.
The number of nodes to add as add_nodes_number.
The number of edges(practical number) to add as m.
If the nodes of edges to be added are not already in the graph, add nodes with add_edge function, too.
The number of edge existence queries as test_edge_exists_number.
The test_edge_exists_number vertices pair to test edge existence.
The number of vertices to output neighbors as output_neighbor_number.
The output_neighbor_number vertices to output neighbors.
The remove_edge_exists_number as the number of edges to be removed.
The remove_edge_exists_number edges to remove.
Output:
The edge existence result of given edges.
The neighbors result of given nodes.
The indexes of nodes in the hash table and nodes in the final graph.
Sample Input 1:
20
4
90 100 110 120
10
0 1
0 2
1 3
1 4
3 7
4 7
2 5
2 6
5 7
6 7
2
1 3
2 8
3
1 2 3
1
2 6
Sample Output 1:
There is an edge from vertex 1 to vertex 3
There is no edge from vertex 2 to vertex 8
head<->3<->4<->tail
head<->5<->6<->tail
head<->7<->tail
Final graph:
0<->100: head<->tail
1<->120: head<->tail
2<->0: head<->1<->2<->tail
3<->1: head<->3<->4<->tail
4<->2: head<->5<->tail
5<->3: head<->7<->tail
6<->4: head<->7<->tail
7<->7: head<->tail
8<->5: head<->7<->tail
9<->6: head<->7<->tail
10<->90: head<->tail
11<->110: head<->tail