Consider the java Graph class below which represents an undirected graph in an adjacency list. How would you add a method to delete an edge from the graph?
// Exercise 4.1.3 (Solution published at
http://algs4.cs.princeton.edu/)
package algs41;
import stdlib.*;
import algs13.Bag;
/**
* The <code>Graph</code> class represents an undirected
graph of vertices
* named 0 through V-1.
* It supports the following operations: add an edge to the
graph,
* iterate over all of the neighbors adjacent to a vertex.
* Parallel edges and self-loops are permitted.
* <p>
* For additional documentation, see <a
href="http://algs4.cs.princeton.edu/51undirected">Section
5.1</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick
and Kevin Wayne.
*/
public class Graph {
private final int V;
private int E;
private final Bag<Integer>[] adj;
/**
* Create an empty graph with V vertices.
*/
@SuppressWarnings("unchecked")
public Graph(int V) {
if (V < 0) throw new
Error("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
this.adj = new Bag[V];
for (int v = 0; v < V; v++)
{
adj[v] = new
Bag<>();
}
}
/**
* Return the number of vertices in the graph.
*/
public int V() { return V; }
/**
* Return the number of edges in the graph.
*/
public int E() { return E; }
/**
* Add the undirected edge v-w to graph.
* @throws java.lang.IndexOutOfBoundsException unless
both 0 <= v < V and 0 <= w < V
*/
public void addEdge(int v, int w) {
if (v < 0 || v >= V) throw
new IndexOutOfBoundsException();
if (w < 0 || w >= V) throw
new IndexOutOfBoundsException();
E++;
adj[v].add(w);
adj[w].add(v);
}
/**
* Return the list of neighbors of vertex v as in
Iterable.
* @throws java.lang.IndexOutOfBoundsException unless 0
<= v < V
*/
public Iterable<Integer> adj(int v) {
if (v < 0 || v >= V) throw
new IndexOutOfBoundsException();
return adj[v];
}
/**
* Returns the degree of vertex {@code
v}.
*
* @param v the vertex
* @return the degree of vertex {@code
v}
* @throws IllegalArgumentException unless
{@code 0 <= v < V}
*/
public int degree(int v) {
if (v < 0 || v >= V) throw
new IndexOutOfBoundsException();
return adj[v].size();
}
/**
* Return a string representation of the graph.
*/
public String toString() {
StringBuilder s = new
StringBuilder();
String NEWLINE =
System.getProperty("line.separator");
s.append(V + " vertices, " + E + "
edges " + NEWLINE);
for (int v = 0; v < V; v++)
{
s.append(v + ":
");
for (int w :
adj[v]) {
s.append(w + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
/**
* Save a graphviz representation of the graph.
* See <a
href="http://www.graphviz.org/">graphviz.org</a>.
*/
public void toGraphviz(String filename) {
GraphvizBuilder gb = new
GraphvizBuilder ();
for (int v = 0; v < V; v++)
{
gb.addNode
(v);
boolean
showSelfLoop = false;
for (int w :
adj[v]) {
if (v < w) // only once each edge
gb.addEdge (v, w);
if (v == w) {
showSelfLoop =
!showSelfLoop;
if (showSelfLoop)
gb.addEdge
(v, w);
}
}
}
gb.toFileUndirected
(filename);
}
/**
* Test client.
*/
public static void main(String[] args) {
//args = new String [] {
"data/tinyCG.txt" };
args = new String [] {
"data/tinyG.txt" };
//args = new String [] { "20", "40"
};
Graph G;
if (args.length == 1) {
In in = new
In(args[0]);
G =
GraphGenerator.fromIn (in);
} else {
int V =
Integer.parseInt (args[0]);
int E =
Integer.parseInt (args[1]);
G =
GraphGenerator.simple(V, E);
}
StdOut.println(G);
G.toGraphviz ("g.png");
}
}
Suppose we have to remove an edge u-v from the graph we can add the below function to the above code
public void delEdge(Vector <Integer>adj[],int u,int v)
{
for
(
int
i
=
0
; i < adj[u].size();
i++)
{
if
(adj[u].get(i) == v)
{
adj[u].remove(i);
break;
}
}
for
(
int
i
=
0; i < adj[v].size(); i++)
{
if
(adj[v].get(i) == u)
{
adj[v].remove(i);
break;
}
}
}
Consider the java Graph class below which represents an undirected graph in an adjacency list. How...
Java: Return an array of booleans in a directed graph. Please complete the TODO section in the mark(int s) function import algs13.Bag; import java.util.HashSet; // See instructions below public class MyDigraph { static class Node { private String key; private Bag<Node> adj; public Node (String key) { this.key = key; this.adj = new Bag<> (); } public String toString () { return key; } public void addEdgeTo (Node n) { adj.add (n); } public Bag<Node> adj () { return adj;...
Help !! I need help with Depth-First Search using an undirected graph. Write a program, IN JAVA, to implement the depth-first search algorithm using the pseudocode given. Write a driver program, which reads input file mediumG.txt as an undirected graph and runs the depth-first search algorithm to find paths to all the other vertices considering 0 as the source. This driver program should display the paths in the following manner: 0 to ‘v’: list of all the vertices traversed to...
How would I traverse through this graph? Provide example code, please! class Edge { int src, dest; Edge(int src, int dest) { this.src = src; this.dest = dest; } }; // class to represent a graph object class Graph { // A list of lists to represent adjacency list List<List<Integer>> adj = new ArrayList<>(); // Constructor to construct graph public Graph(List<Edge> edges) { // allocate memory for adjacency list for (int i = 0; i < edges.size(); i++) { adj.add(i,...
Below is the Graph file that needs to be modified(using Python3) : #!/usr/bin/python3 # Simple Vertex class class Vertex: """ Lightweight vertex structure for a graph. Vertices can have the following labels: UNEXPLORED VISITED Assuming the element of a vertex is string type """ __slots__ = '_element', '_label' def __init__(self, element, label="UNEXPLORED"): """ Constructor. """ self._element = element self._label = label def element(self): """ Return element associated with this vertex. """ return self._element def getLabel(self): """ Get label assigned to...
Please try your best to complete this 11 methods under. I have provided the UndirectedGraph class with the single instance data variable. Do not add any additional instance data variables. Do not modify any other classes provided. In addition to writing the 8 required methods of the interface and the constructor, you will also write methods for the two traversals and an isConnected method. import java.util.Queue; public class UndirectedGraph<T> implements BasicGraphInterface <T> { private DirectedGraph digraph; ...
3. Graph Connected Components (25 pts) You are given an undirected, unweighted graph that may be disconnected i.e. some vertices may not be reachable from other vertices. Every group of mutually reachable vertices forms an island, called a con- nected component. There is no path between vertices in different connected components. If a graph is not disconnected, then its vertices are in a single connected component, which is the entire graph itself. Implement a method using depth-first search that will...
Given the Interface Code write a java class that implements this interface and show the working functionality in the main method: public interface CustomList<T> { /** * This method should add a new item into the <code>CustomList</code> and should * return <code>true</code> if it was successfully able to insert an item. * @param item the item to be added to the <code>CustomList</code> * @return <code>true</code> if item was successfully added, <code>false</code> if the item was not successfully added (note: it...
6) Below is an adjacency matrix for an undirected graph, size n- 8. Vertices are labeled 1 to 8 Rows are labeled 1 through 8, top to bottom. Columns are labeled 1 through 8, left to right. Column labels to the right: 1 2 345 6 78 Row labels are below this: 1 0 0 1 000 0 0 2 0 0 101 1 00 (See a drippy heart?) 3 1 1 0 1 01 0 0 4 0 0...
from collections import defaultdict # This class represents a directed graph using # adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue...
Hello, i am working on java program which implements Graph as an adjacency list structure. code is the implementation of RailNetwork. i need help to change the code so it could hold String instead of integers. so, for example, Station "Station name" is connected to "Station name" and also i need to add class edge which basically will be a direction for those give stations. so the output will be like "Station name" is connected to "Station name" with "this...