import java.util.ArrayList;

public class GraphAsLists {

private int numberOfVertices;

private int numberOfEdges;

private Vertex vertex[];

private DLL adjacencyList[];

private boolean isDirected;

public GraphAsLists(int size, boolean directed) {

isDirected = directed;

vertex = new Vertex[size];

adjacencyList = new DLL[size];

for(int v = 0; v

adjacencyList[v] = new DLL();

}

public GraphAsLists(int size) {

this(size, false);

}

//Begining of Vertex class as inner class

protected class Vertex {

protected int ID;

protected Object weight;

public Vertex(int v, Object wt) {

ID = v;

weight = wt;

}

public Vertex(int v) {

this(v, null);

}

public int getID() {

return ID;

}

public Object getWeight() {

return weight;

}

public boolean equals (Object obj) {

Vertex other = (Vertex) obj;

return ID == other.ID;

}

public Edge[] getIncidentEdges() {

return GraphAsLists.this.getIncidentEdges(ID);

}

public Edge[] getEmanatingEdges() {

return GraphAsLists.this.getEmanatingEdges(ID);

}

public Vertex[] getPredecessors() {

Edge[] incidents = getIncidentEdges();

if (incidents != null) {

int countOfIncidents = incidents.length;

Vertex[] preds = new Vertex[countOfIncidents];

for (int i=0; i

preds[i] = incidents[i].getMate(this);

return preds;

} else

return null;

}

public Vertex[] getSuccessors() {

Edge[] emanatings = getEmanatingEdges();

if (emanatings != null) {

int countOfEmanatings = emanatings.length;

Vertex[] succs = new Vertex[countOfEmanatings];

for (int i=0; i

succs[i] = emanatings[i].getMate(this);

return succs;

}

else

return null;

}

public String toString() {

String s = "V{" + ID;

if(weight != null)

s+=", " + weight;

s+="}";

return s;

}

} //End of Vertex class

//Begining of Edge class as an inner class

protected class Edge {

protected int v0;

protected int v1;

protected Object weight;

public Edge(int v, int w, Object obj) {

v0 = v;

v1 = w;

weight = obj;

}

public Edge(int v, int w) {

this(v, w, null);

}

public Vertex getV0() {

return vertex[v0];

}

public Vertex getV1() {

return vertex[v1];

}

public Object getWeight() {

return weight;

}

public Vertex getMate(Vertex v) {

if(v.getID() == v0)

return vertex[v1];

if(v.getID() == v1)

return vertex[v0];

else

return null; //invalid argument; better to throw exception here

}

public boolean isDirected() { //edge is directed if its graph is directed

return GraphAsLists.this.isDirected();

}

public boolean equals (Object obj) {

Edge other = (Edge) obj;

return v0 == other.v0 && v1 == other.v1;

}

public String toString() {

String s = "E{" + v0;

if(isDirected())

s+="->" + v1;

else

s+="--" + v1;

if(weight != null)

s+=", " + weight;

s+="}";

return s;

}

} //end of the Edge class

//Begining of Graph methods

public int getNumberOfVertices() {

return numberOfVertices;

}

public int getNumberOfEdges() {

return numberOfEdges;

}

public boolean isDirected() {

return isDirected;

}

public void visit(Vertex v) {

System.out.print(v+ " ");

}

public void addEdge(int v0, int v1, Object wt) {

adjacencyList[v0].addToTail(new Edge(v0, v1, wt));

numberOfEdges++;

}

public void addEdge(int v0, int v1) {

addEdge(v0, v1, null);

}

public Edge getEdge(int v0, int v1) {

if(v0 numberOfVertices - 1 || v1 numberOfVertices - 1)

return null; //invalid edge;

Object element = adjacencyList[v0].find(new Edge(v0, v1));

if (element != null)

return (Edge) element;

else

return null;

}

public void addVertex(Object wt) { //Note: ID of vertex is auto generated: 0, 1, 2, ...

vertex[numberOfVertices] = new Vertex(numberOfVertices, wt);

numberOfVertices++;

}

public void addVertex() {

addVertex(null);

}

public Vertex getVertex(int v) {

if(v numberOfVertices - 1)

return null;

else

return vertex[v];

}

public Vertex[] getVertices() {

return vertex;

}

public Edge[] getEmanatingEdges(int v0) {

return adjacencyList[v0].toArray(new Edge[0]);

}

public Edge[] getIncidentEdges(int v1) {

DLL list = new DLL();

for (int v0 = 0; v0

Edge edge = adjacencyList[v0].find(new Edge(v0, v1));

if (edge != null)

list.addToTail(edge);

}

return list.toArray(new Edge[0]);

}

public void depthFirstTraversal(int start) {

boolean visited[] = new boolean[numberOfVertices];

for(int v = 0; v

visited[v] = false;

depthFirstTraversal(start, visited);

}

private void depthFirstTraversal(int start, boolean[] visited){

if (visited[start])

return;

visit(vertex[start]);

visited[start] = true;

Vertex succ;

int id;

Vertex[] succs = vertex[start].getSuccessors();

if (succs != null) {

for (int i=0; i

succ = succs[i];

id = succ.getID();

if(!visited[id])

depthFirstTraversal(id, visited);

}

}

}

public void breadthFirstTraversal(int start) {

boolean enqueued[] = new boolean[numberOfVertices];

for(int v = 0; v

enqueued[v] = false;

LLQueue queue = new LLQueue();

enqueued[start] = true;

queue.enqueue(vertex[start]);

while(!queue.isEmpty()) {

Vertex v = (Vertex) queue.dequeue();

visit(v);

Vertex[] succs = v.getSuccessors();

if (succs != null) {

Vertex succ;

int id;

for (int i=0; i

succ = succs[i];

id = succ.getID();

if(!enqueued[id]) {

queue.enqueue(succ);

enqueued[id] = true;

}

}

}

}

}

public String toString() {

String s = "";

for (int i=0; i

s += vertex[i]+ ":";

s+= "\t"+adjacencyList[i]+ " ";

}

return s;

}

}

#########################################################

import java.io.*;

import java.util.Scanner;

public class TestGraph

{

public static void main(String[] args)

{

GraphAsLists graph = initGraph("GraphData2.txt");

int option, id;

GraphAsLists.Vertex[] vertices;

GraphAsLists.Edge[] edges;

Scanner reader = new Scanner(System.in);

do {

System.out.println(" ***************************");

System.out.println("* Testing Graph *");

System.out.println("*************************** ");

System.out.println("1. Print Graph");

System.out.println("2. Print Graph Traversals");

System.out.println("3. Print Predecessors and Successors of a vertex");

System.out.println("4. Print Incident and Emanating Edges of a vertex");

System.out.println("5. Quit");

System.out.print(" Select an Option [1...5] : ");

option = reader.nextInt();

switch (option) {

case 1 : System.out.println(graph);

break;

case 2 : System.out.println("Depth First Traversal:");

graph.depthFirstTraversal(0);

System.out.println();

System.out.println("Breadth First Traversal:");

graph.breadthFirstTraversal(0);

System.out.println();

break;

case 3 : System.out.print("Enter the ID of a vertex to print its Successors and Predecessors: ");

id = reader.nextInt();

vertices = graph.getVertex(id).getSuccessors();

System.out.print("Successors of Vertex "+id+" are: ");

for(int i=0; i

System.out.print(vertices[i]+ " ");

vertices = graph.getVertex(id).getPredecessors();

System.out.print(" Predecessors of Vertex "+id+" are: ");

for(int i=0; i

System.out.print(vertices[i]+" ");

break;

case 4 : System.out.print("Enter the ID of a vertex to print its Incident and Emanating edges: ");

id = reader.nextInt();

edges = graph.getIncidentEdges(id);

System.out.print("Incident edges for Vertex "+id+" are: ");

for(int i=0; i

System.out.print(edges[i]+" ");

edges = graph.getEmanatingEdges(id);

System.out.print(" Emanating edges for Vertex "+id+" are: ");

for(int i=0; i

System.out.print(edges[i]+ " ");

break;

} //end of switch

} while (option != 5);

}

//assumes first line contains size followed by D for directed graph or U for undirected graph

//followed by possible comments.

//remaining lines contains two digits each, representing the the edges.

public static GraphAsLists initGraph(String dataFile) {

try {

Scanner reader = new Scanner(new File(dataFile));

GraphAsLists graph;

int v0, v1, weight, size;

String line; String[] tokens;

line = reader.nextLine();

tokens = line.split("\\s+");

size = Integer.parseInt(tokens[0]);

if (tokens[1].equals("D"))

graph = new GraphAsLists(size, true);

else

graph = new GraphAsLists(size, false);

//add verices

for (int i=0; i

graph.addVertex();

//add edges

while (reader.hasNextLine())

{

line = reader.nextLine();

tokens = line.split("\\s+");

v0 = Integer.parseInt(tokens[0]);

v1 = Integer.parseInt(tokens[1]);

if (tokens.length > 2) {

weight = Integer.parseInt(tokens[2]);

graph.addEdge(v0, v1, weight);

}

else

graph.addEdge(v0, v1);

}

reader.close();

return graph;

} catch(IOException ex) {

System.out.println("File Error");

return null;

}

}

}

#########################################################

/GraphData.txt

7 D //size 7, directed graph

0 1

0 3

1 3

1 4

1 6

2 0

2 5

3 2

3 4

4 2

4 5

6 4

#########################################################

Write these two methods:

First, public int getInDegree (int v) - Hint you may use getIncidentEdges() method.

Second, public int getOutDegree (int v) - Hint you may use getEmanatingEdges() method.

Degree of a vertex o Number of edges incident on a vertex Indegree o Number of directed edges to vertex - - Outdegree o Number of directed edges from vertex degree(v4) 6 indegree(V4) -3 outdegree(v4) 3 V1 V2 indegree(V1) 0 outdegree(V1) - 3 y3 indegree(v6) 3 outdegree(v6) 0