Implement a graph ADT by defining a class \"Graph\" with the operations below. Y
ID: 3936467 • Letter: I
Question
Implement a graph ADT by defining a class "Graph" with the operations below. Your ADT should accept either a directed or undirected graph. isDirect(): tests if the graph is a digraph. Returns Boolean value. adjacent(v, u): tests whether there is an edge from the vertex v to u. returns Boolean value. neighbors(v): returns the list of all vertices that are a destination of an edge from v. addVertex(v): adds the vertex v to the graph if it is not already in the graph, otherwise an error message to be thrown. removeVertex(v): removes vertex v from the graph, if it is there. When a vertex is removed, all edges associated with that vertex should be deleted as well. addEdge(v, u): adds the edge that starts from v and ends at u. addEdge(v, u, w): adds the edge that starts from v and ends at u with weight w. removeEdge(v, u): remove the edge that connects v and u. getWeight(v, u): returns the weight of the edge from v to u. setWeight(v, u): sets the weight of the edge from v to u. isEmpty(): check whether the graph is empty or not. isComplete(): checks whether the graph is complete or not. vertices():returns the list of vertices in the graph (i.e., array, vector, ..) edges(): returns the list of edges in the graph. degree(v): return the degree of vertex v. size(): returns the number of vertices in the graph. nEdges(): returns the number of edges in the graph. clear(): Reinitializes the graph to be empty, freeing any heap storage. vertexExists(v): tests whether a vertex is in the graph or not. Returns true or false. print(): displays the list of vertices, edges and their weights if the graph is weighted. Your ADT should contain at least these constructors: Graph(), creates a graph with zero vertices. Graph(n), creates a graph with n vertices. Graph(n, digraph), where digraph is a Boolean value if true means a directed graph.Explanation / Answer
Answer: See the code below
-------------------------------------------------
using System;
using System.Collections.Generic;
namespace GraphADT
{
//Graph ADT class
abstract class Graph
{
//data members
private int nV; //number of vertices
private int nE; //number of edges
private int[,] adjMatrix; //adjaceny matrix for graph
private bool directedGraph; //flag for graph being directed graph
//constructors
//creates a graph with zero vertices
public Graph()
{
nV = 0;
nE = 0;
directedGraph = false;
}
//creates a graph with n vertices
public Graph(int n)
{
nV = n;
nE = 0;
adjMatrix = new int[n,n];
directedGraph = false;
}
//creates a digraph with n vertices
public Graph(int n, bool digraph)
{
nV = n;
nE = 0;
adjMatrix = new int[n, n];
directedGraph = digraph;
}
//methods
//tests is the graph is a diagraph.
public abstract bool isDirect();
//tests whether there is an edge from vertex v to u
public abstract bool adjacent(int u, int v);
//returns the list of all vertices that are a destination of an edge from v.
public abstract List<int> neighbours(int v);
//adds the vertex v to the graph, if not already in graph, otherwise an error message is thrown.
public abstract void addVertex(int v);
//removes vertex v from the graph, if it is there. When a vertex is removed, all edges associated
//with that vertex are also removed.
public abstract void removeVertex(int v);
//add the edge that starts from v and ends at u.
public abstract void addEdge(int v, int u);
//add the edge that starts from v and ends at u with weight w.
public abstract void addEdge(int v, int u, int w);
//returns the weight of edge from v to u.
public abstract void getWeight(int v, int u);
//sets the weight of edge from v to u.
public abstract void setWeight(int v, int u);
//checks whether graph is empty or not
public abstract bool isEmpty();
//checks whether the graph is complete or not
public abstract bool isComplete();
//returns the list of vertices in graph
public abstract List<int> vertices();
//returns the list of edges in the graph
public abstract int[][] edges();
//returns the degree of vertex v
public abstract int degree(int v);
//returns the number of vertices in graph
public abstract int size();
//returns the number of edges in graph
public abstract int nEdges();
//Reinitializes the graph to be empty, freeing any heap storage
public abstract void clear();
//tests whether a vertex is in the graph or not
public abstract bool vertexExists(int v);
//displays the list of vertices, edges and their weights, if the graph is weighted
public abstract void print();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.