Data Structures Project 13 Note that adjacency matrix graph implementation in yo

Question

Data Structures Project 13

Note that adjacency matrix graph implementation in your book (section 11.2, fig. 11.6) does not provide means to actually create the graph. Implement 11.6 algorithm and extend it so that a user can read graph description from a file. This data can then be used by setEdge function to build the graph. Provide a main program that 'demos' different graph functions.

_____________________

THIS IS FIGURE 11.6!!!

_____________________

/** Graph: Adjacency matrix */
class Graphm implements Graph {
private int[][] matrix; // The edge matrix
private int numEdge; // Number of edges
public int[] Mark; // The mark array
public Graphm() {} // Constructors
public Graphm(int n) {
Init(n);
}
public void Init(int n) {
Mark = new int[n];
matrix = new int[n][n];
numEdge = 0;
}
public int n() { return Mark.length; } // # of vertices
public int e() { return numEdge; } // # of edges
/** @return v’s first neighbor */
public int first(int v) {
for (int i=0; i if (matrix[v][i] != 0) return i;
return Mark.length; // No edge for this vertex
}
/** @return v’s next neighbor after w */
public int next(int v, int w) {
for (int i=w+1; i if (matrix[v][i] != 0)
return i;
return Mark.length; // No next edge;
}
/** Set the weight for an edge */
public void setEdge(int i, int j, int wt) {
assert wt!=0 : "Cannot set weight to 0";
if (matrix[i][j] == 0) numEdge++;
matrix[i][j] = wt;
}
/** Delete an edge */
public void delEdge(int i, int j) { // Delete edge (i, j)
if (matrix[i][j] != 0) numEdge--;
matrix[i][j] = 0;
}
/** Determine if an edge is in the graph */
public boolean isEdge(int i, int j)
{ return matrix[i][j] != 0; }

}

PLEASE PROVIDE A ANSWER I CAN JUST COPY AND PASTE NO Abbreviations Please

Thank You

Explanation / Answer

import java.util.Iterator;
import java.util.NoSuchElementException;

public class AMGraph {
private static final String NEWLINE = System.getProperty("line.separator");
private int V;
private int E;
private boolean[][] adj;
  
// empty graph with V vertices
public AMGraph(int V) {
if (V < 0) throw new RuntimeException("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
this.adj = new boolean[V][V];
}

// random graph with V vertices and E edges
public AMGraph(int V, int E) {
this(V);
if (E < 0) throw new RuntimeException("Number of edges must be nonnegative");
if (E > V*(V-1) + V) throw new RuntimeException("Too many edges");

// can be inefficient
while (this.E != E) {
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
addEdge(v, w);
}
}

// number of vertices and edges
public int V() { return V; }
public int E() { return E; }

// add undirected edge v-w
public void addEdge(int v, int w) {
if (!adj[v][w]) E++;
adj[v][w] = true;
adj[w][v] = true;
}

// does the graph contain the edge v-w?
public boolean contains(int v, int w) {
return adj[v][w];
}

// return list of neighbors of v
public Iterable<Integer> adj(int v) {
return new AdjIterator(v);
}

// support iteration over graph vertices
private class AdjIterator implements Iterator<Integer>, Iterable<Integer> {
private int v;
private int w = 0;

AdjIterator(int v) {
this.v = v;
}

public Iterator<Integer> iterator() {
return this;
}

public boolean hasNext() {
while (w < V) {
if (adj[v][w]) return true;
w++;
}
return false;
}

public Integer next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return w++;
}

public void remove() {
throw new UnsupportedOperationException();
}
}

// string representation of Graph - takes quadratic time
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + 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();
}

// test client
public static void main(String[] args) {
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
AMGraph G = new AMGraph(V, E);
StdOut.println(G);
}

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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