Rewrite from Java to Python.It would be possible, and even plausibly Pythonic, to reproduce the class structure of the Java Graph in Python, minus an interface le, of course. But to emphasize the point that you can get a lot done in Python without using OO techniques, you should not do that here . Instead ,just directly construct and use a Python dict with vertex keys and (set of vertex) values, where vertices can be type of values (even heterogenous ones!)

In Java

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); } }

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); }

public abstract class GraphUtils {

static Graph emptyGraph() { return new HiddenGraph(); }

static String dumpGraph(Graph g) { String s = "Vertex count = " + g.vertexCount() + " "; for (V v : g.vertices()) { s += v + ":"; for (V w : g.neighbors(v)) s += " " + w; s += " "; } return s; }

static Graph readIntegerGraph(String name) throws Exception { Scanner in = new Scanner(new FileReader(name + ".ig")); Graph g = emptyGraph(); in.nextLine(); // read and ignore V in.nextLine(); // read and ignore E while (in.hasNext()) { Integer v1 = in.nextInt(); Integer v2 = in.nextInt(); g.addVertex(v1); //might or might not already exist g.addVertex(v2); g.addEdge(v1,v2); } in.close(); return g; }

static Graph readStringGraph(String name, String sep) throws Exception { Scanner in = new Scanner(new FileReader(name + ".sg")); Graph g = emptyGraph(); while (in.hasNext()) { String[] a = in.nextLine().split(sep); g.addVertex(a[0]); //might or might not already exist for (int i = 1; i < a.length; i++) { g.addVertex(a[i]); g.addEdge(a[0],a[i]); } } in.close(); return g; }

public static void toDot(Graph g, String gname) throws Exception { java.io.PrintStream out = new java.io.PrintStream(gname + ".dot"); out.println("graph " + gname + " {"); // challenge is to avoid drawing every edge twice Set visited = new HashSet(); for (V v : g.vertices()) { for (V w : g.neighbors(v)) if (!visited.contains(w)) out.println("\"" + v + "\" -- \"" + w + "\""); visited.add(v); } out.println("}"); out.close(); }

# Fill in the missing functions in Python based on the functions given above in Java def read_integer_graph():

# Write your code here

def read_string_graph(): # Write your code here

def write_dot_graph(): #Write your code here

def usage(): print('usage: ./graph.py [ file.ig | file.sg sep ]') exit(0)

def main(): if len(sys.argv) < 2: usage() f = sys.argv[1] gname,kind = os.path.splitext(f) if kind == '.ig': if len(sys.argv) != 2: usage() g = read_integer_graph(gname) elif kind == '.sg': if len(sys.argv) != 3: usage() g = read_string_graph(gname,sys.argv[2]) else: usage() write_dot_graph(gname,g) if __name__ == '__main__': main()