You will implement an adjacency-list-based graph implementation where each node

Question

You will implement an adjacency-list-based graph implementation where each node has a label (an integer between 1 and |V|) and a set nodes representing the outgoing edges (see the last page for example). For simplicity, the nodes will store no additional values.
Implement the following operations. These will be graded based on correctness and efficiency.
DirectedGraph(String str) – Initializes a directed graph from a string. The string representing the graph is in the following format: “[v1, v2][v3, v4][v2, v3]…” where each “[vi, vj]” pair represents an edge between two vertices vi and vj. The constructor will parse the string and initialize a set of Graph Node objects.
Collection<GraphNode> getIncomingEdges(GraphNode v) – In our implementation each node does not store incoming edges, only outgoing edges. This method will return the collection of nodes that have an edge directed to the given node v.
boolean isDAG() – Returns true if the graph is a directed acyclic graph.
Collection<GraphNode> getRoots() – Returns the roots of the graph (i.e., the nodes with no incoming edges).
int edgeCount() – Returns the total number of edges in the graph.
void printAsAdjacencyMatrix() – Prints the graph as an adjacency matrix.
List<GraphNode> findCycle(GraphNode v) – Returns a cycle for v, if one exists. Note that multiple cycles may exist, but this method will only return one, represented as a list of nodes.
Hint: Note that many of these operations will rely on basic graph traversals (e.g., DFS, BFS).
Test Cases: Initialize Graph A and Graph B. Apply isDAG, getRoots, edgeCount, and printAsAdjacencyMatrix on both graphs.

Explanation / Answer

import java.util.Scanner;

public class Represent_Graph_Adjacency_Matrix
{
private final int vertices;
private int[][] adjacency_matrix;

public Represent_Graph_Adjacency_Matrix(int v)
{
vertices = v;
adjacency_matrix = new int[vertices + 1][vertices + 1];
}

public void makeEdge(int to, int from, int edge)
{
try
{
adjacency_matrix[to][from] = edge;
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
}

public int getEdge(int to, int from)
{
try
{
return adjacency_matrix[to][from];
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
return -1;
}

public static void main(String args[])
{
int v, e, count = 1, to = 0, from = 0;
Scanner sc = new Scanner(System.in);
Represent_Graph_Adjacency_Matrix graph;
try
{
System.out.println("Enter the number of vertices: ");
v = sc.nextInt();
System.out.println("Enter the number of edges: ");
e = sc.nextInt();

graph = new Represent_Graph_Adjacency_Matrix(v);

System.out.println("Enter the edges: <to> <from>");
while (count <= e)
{
to = sc.nextInt();
from = sc.nextInt();

graph.makeEdge(to, from, 1);
count++;
}

System.out.println("The adjacency matrix for the given graph is: ");
System.out.print(" ");
for (int i = 1; i <= v; i++)
System.out.print(i + " ");
System.out.println();

for (int i = 1; i <= v; i++)
{
System.out.print(i + " ");
for (int j = 1; j <= v; j++)
System.out.print(graph.getEdge(i, j) + " ");
System.out.println();
}

}
catch (Exception E)
{
System.out.println("Somthing went wrong");
}

sc.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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