The hexagon game involves two players, who gradually construct a six-vertex undi

Question

The hexagon game involves two players, who gradually construct a six-vertex undirected graph with solid and dashed edges. Player 1 adds solid edges, whereas Player 2 uses dashes.

The players begin with a six-vertex graph that has no edges (Figure 1), and add new edges, one by one; Player 1 makes the first move. At each move, a player has to add a new edge between two vertices that are not connected by any old edge. Figure 2 is an example of a mid-game position, where Player 1 has to make the next move.

If Player 1 constructs a solid-line triangle, he loses the game; similarly, a dashed triangle means a loss of Player 2. For example, if the game ends as shown in Figure 3, then Player 2 has lost since he has constructed the dashed triangle

The hexagon game involves two players, who gradually construct a six-vertex undirected graph with solid and dashed edges. Player 1 adds solid edges, whereas Player 2 uses dashes. The players begin with a six-vertex graph that has no edges (Figure 1), and add new edges, one by one; Player 1 makes the first move. At each move, a player has to add a new edge between two vertices that are not connected by any old edge. Figure 2 is an example of a mid-game position, where Player 1 has to make the next move. If Player 1 constructs a solid-line triangle, he loses the game; similarly, a dashed triangle means a loss of Player 2. For example, if the game ends as shown in Figure 3, then Player 2 has lost since he has constructed the dashed triangle Implement a program for playing the hexagon game. Your program should prompt the user to enter a player number (1 or 2), and then act as the specified player. For example, if the user enters ??, the program should make the first move.

Explanation / Answer

/*graph.h*/
#ifndef _GRAPH_H_
#define _GRAPH_H_

typedef enum {UNDIRECTED=0,DIRECTED} graph_type_e;

/* Adjacency list node*/
typedef struct adjlist_node
{
int vertex; /*Index to adjacency list array*/
struct adjlist_node *next; /*Pointer to the next node*/
}adjlist_node_t, *adjlist_node_p;

/* Adjacency list */
typedef struct adjlist
{
int num_members; /*number of members in the list (for future use)*/
adjlist_node_t *head; /*head of the adjacency linked list*/
}adjlist_t, *adjlist_p;

/* Graph structure. A graph is an array of adjacency lists.
Size of array will be number of vertices in graph*/
typedef struct graph
{
graph_type_e type; /*Directed or undirected graph */
int num_vertices; /*Number of vertices*/
adjlist_p adjListArr; /*Adjacency lists' array*/
}graph_t, *graph_p;

/* Exit function to handle fatal errors*/
__inline void err_exit(char* msg)
{
printf("[Fatal Error]: %s Exiting... ", msg);
exit(1);
}

#endif

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*graph.c*/
#include
#include
#include "graph.h"

/* Function to create an adjacency list node*/
adjlist_node_p createNode(int v)
{
adjlist_node_p newNode = (adjlist_node_p)malloc(sizeof(adjlist_node_t));
if(!newNode)
err_exit("Unable to allocate memory for new node");

newNode->vertex = v;
newNode->next = NULL;

return newNode;
}

/* Function to create a graph with n vertices; Creates both directed and undirected graphs*/
graph_p createGraph(int n, graph_type_e type)
{
int i;
graph_p graph = (graph_p)malloc(sizeof(graph_t));
if(!graph)
err_exit("Unable to allocate memory for graph");
graph->num_vertices = n;
graph->type = type;

/* Create an array of adjacency lists*/
graph->adjListArr = (adjlist_p)malloc(n * sizeof(adjlist_t));
if(!graph->adjListArr)
err_exit("Unable to allocate memory for adjacency list array");

for(i = 0; i < n; i++)
{
graph->adjListArr[i].head = NULL;
graph->adjListArr[i].num_members = 0;
}

return graph;
}

/*Destroys the graph*/
void destroyGraph(graph_p graph)
{
if(graph)
{
if(graph->adjListArr)
{
int v;
/*Free up the nodes*/
for (v = 0; v < graph->num_vertices; v++)
{
adjlist_node_p adjListPtr = graph->adjListArr[v].head;
while (adjListPtr)
{
adjlist_node_p tmp = adjListPtr;
adjListPtr = adjListPtr->next;
free(tmp);
}
}
/*Free the adjacency list array*/
free(graph->adjListArr);
}
/*Free the graph*/
free(graph);
}
}

/* Adds an edge to a graph*/
void addEdge(graph_t *graph, int src, int dest)
{
/* Add an edge from src to dst in the adjacency list*/
adjlist_node_p newNode = createNode(dest);
newNode->next = graph->adjListArr[src].head;
graph->adjListArr[src].head = newNode;
graph->adjListArr[src].num_members++;

if(graph->type == UNDIRECTED)
{
/* Add an edge from dest to src also*/
newNode = createNode(src);
newNode->next = graph->adjListArr[dest].head;
graph->adjListArr[dest].head = newNode;
graph->adjListArr[dest].num_members++;
}
}

/* Function to print the adjacency list of graph*/
void displayGraph(graph_p graph)
{
int i;
for (i = 0; i < graph->num_vertices; i++)
{
adjlist_node_p adjListPtr = graph->adjListArr[i].head;
printf(" %d: ", i);
while (adjListPtr)
{
printf("%d->", adjListPtr->vertex);
adjListPtr = adjListPtr->next;
}
printf("NULL ");
}
}

int main()
{
graph_p undir_graph = createGraph(5, UNDIRECTED);
graph_p dir_graph = createGraph(5, DIRECTED);
addEdge(undir_graph, 0, 1);
addEdge(undir_graph, 0, 4);
addEdge(undir_graph, 1, 2);
addEdge(undir_graph, 1, 3);
addEdge(undir_graph, 1, 4);
addEdge(undir_graph, 2, 3);
addEdge(undir_graph, 3, 4);

addEdge(dir_graph, 0, 1);
addEdge(dir_graph, 0, 4);
addEdge(dir_graph, 1, 2);
addEdge(dir_graph, 1, 3);
addEdge(dir_graph, 1, 4);
addEdge(dir_graph, 2, 3);
addEdge(dir_graph, 3, 4);

printf(" UNDIRECTED GRAPH");
displayGraph(undir_graph);
destroyGraph(undir_graph);

printf(" DIRECTED GRAPH");
displayGraph(dir_graph);
destroyGraph(dir_graph);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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