Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

/* Additional info that might be needed */ interface Graph { // Add a vertex. No-op if vertex already exists. void addVertex(V v); // Return

image text in transcribed

image text in transcribed

/* Additional info that might be needed */

interface Graph {

// Add a vertex. No-op if vertex already exists. void addVertex(V v);

// Return all the vertices Iterable vertices();

// Return the number of vertices. int vertexCount();

// Answer whether a particular vertex is in the graph boolean hasVertex(V v);

// Add an edge between two vertices. // Raises IllegalArgumentException if either vertex is not in graph // No-op if edge already exists void addEdge(V v1,V v2);

// Return the neighbors of a vertex Iterable neighbors(V v);

// Return the degree (number of neighbors) of a vertex int degree(V v); }

class AdjSetGraph implements Graph { private Map> vertices;

public AdjSetGraph() { vertices = new HashMap>(); }

public void addVertex(V v) { if (!vertices.containsKey(v)) vertices.put(v,new HashSet()); }

public boolean hasVertex(V v) { return vertices.containsKey(v); }

public Iterable vertices() { return vertices.keySet(); }

public int vertexCount() { return vertices.size(); }

private Set getAdjs(V v) { Set adjs = vertices.get(v); if (adjs == null) throw new IllegalArgumentException("vertex " + v + " is not in graph"); return adjs; }

public void addEdge(V v1,V v2) { Set adjs1 = getAdjs(v1); Set adjs2 = getAdjs(v2); adjs1.add(v2); adjs2.add(v1); }

public Iterable neighbors(V v) { return getAdjs(v); }

public int degree(V v) { return getAdjs(v).size(); }

// useful for debugging, once methods are implemented public String toString() { return GraphUtils.dumpGraph(this); } }

Rewrite the Java program(first pic) to Python(second pic) Fill in the missing routines in the second picture.

import java.io. import java , util.* public abstract claas GraphUtils t static V> Graph emptyGraph) return new HiddenGraphv static String dumpGraph (GrapheV> g) ( StringBuilder s new StringBuilder ) a.append ("Vertex countgvertexCount ( for (V vg.verticest)) n) 3-append(vt) for (V w g.neighbors (v)) s append t H) .append("in*)r return .toString()?. static Graph readStringGraph (String name, String pep) throws Exception t Scanner in nek Scanner (new FileReader (name ag")) Graph g, string gnane) throws Exception f java.io. PrintStream out - new java.io.Printstream (gname + seta) set-new Hashsetv ), out-println("graph+ gname + ".dot") for (V v : g.vertices)) t for (V w : g.neighbors (v))f if(set.contains (w)false) "\" \"" t""); + W + out.printIn("\"" + + v -- set add(y) out printlatina out close ( /usr/bin/env python 3 2 3 import sys 4 import os.path 6 # Fill in the missing routines, using the Java versions 7 from lab3/08X and 10X as prototypes. # read-integer-graph ( ) 10 E 11 #read-string-graph ( ) 12 13 write dot graph) 14 15 16 17 Edef usage ): 18 print ('usage: /graph.py I file.ig I file.sg sep 1') 19 exit (0) 20 21 def main): 22 if len (sys.argv) Graph emptyGraph) return new HiddenGraphv static String dumpGraph (GrapheV> g) ( StringBuilder s new StringBuilder ) a.append ("Vertex countgvertexCount ( for (V vg.verticest)) n) 3-append(vt) for (V w g.neighbors (v)) s append t H) .append("in*)r return .toString()?. static Graph readStringGraph (String name, String pep) throws Exception t Scanner in nek Scanner (new FileReader (name ag")) Graph g, string gnane) throws Exception f java.io. PrintStream out - new java.io.Printstream (gname + seta) set-new Hashsetv ), out-println("graph+ gname + ".dot") for (V v : g.vertices)) t for (V w : g.neighbors (v))f if(set.contains (w)false) "\" \"" t""); + W + out.printIn("\"" + + v -- set add(y) out printlatina out close ( /usr/bin/env python 3 2 3 import sys 4 import os.path 6 # Fill in the missing routines, using the Java versions 7 from lab3/08X and 10X as prototypes. # read-integer-graph ( ) 10 E 11 #read-string-graph ( ) 12 13 write dot graph) 14 15 16 17 Edef usage ): 18 print ('usage: /graph.py I file.ig I file.sg sep 1') 19 exit (0) 20 21 def main): 22 if len (sys.argv)

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Data Management Databases And Organizations

Authors: Richard T. Watson

6th Edition

1943153035, 978-1943153039

More Books

Students also viewed these Databases questions