write these method inside GraphAsList.java:

public int getinDegree(int v ) :

that return the in-dgree of the given vertex (i.e the count of edges coming to vertex )

hint: use getIncidentEdges()method.

public void printSourceVertices()

prints all source vertices in the graph . note:source vertices are those with zeroo in-dgree

this GraphAsList.java class :

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 < size; 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 < 0 || v0 > numberOfVertices - 1 || v1 < 0 || 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 < 0 || 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 < numberOfVertices; 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 < numberOfVertices; 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 < numberOfVertices; 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;

}

}

LLQueue :

import java.util.LinkedList;

public class LLQueue { private LinkedList list = new LinkedList(); public LLQueue() { } public void clear() { list.clear(); } public boolean isEmpty() { return list.isEmpty(); } public T firstEl() { return list.getFirst(); } public T dequeue() { return list.removeFirst(); } public void enqueue(T el) { list.add(el); } public String toString() { return list.toString(); } }

DLL:

//**************************** DLL.java *******************************

// generic doubly linked list class

import java.util.*;

public class DLL implements Iterable {

private DLLNode head, tail;

public DLL() {

head = tail = null;

}

public boolean isEmpty() {

return head == null;

}

public void clear() {

head = tail = null;

}

public void addToHead(T el) {

if (head != null) {

head = new DLLNode(el,head,null);

head.next.prev = head;

}

else head = tail = new DLLNode(el);

}

public void addToTail(T el) {

if (tail != null) {

tail = new DLLNode(el,null,tail);

tail.prev.next = tail;

}

else head = tail = new DLLNode(el);

}

public T deleteFromHead() {

if (isEmpty())

return null;

T el = head.info;

if (head == tail) // if only one node on the list;

head = tail = null;

else { // if more than one node in the list;

head = head.next;

head.prev = null;

}

return el;

}

public T deleteFromTail() {

if (isEmpty())

return null;

T el = tail.info;

if (head == tail) // if only one node on the list;

head = tail = null;

else { // if more than one node in the list;

tail = tail.prev;

tail.next = null;

}

return el;

}

public void delete(T el) { // delete the node with an element el;

DLLNode tmp;

for (tmp = head; tmp != null && !el.equals(tmp.info); tmp = tmp.next); //locate the item

if (tmp != null) { // item found

if (head == tail) //the found item was the only one

head = tail = null;

else if (head == tmp) { //the found item is the first

head = head.next;

head.prev = null;

}

else if (tail == tmp) { // the found item is the last

tail = tail.prev;

tail.next = null;

}

else { // the found item is in the middle

tmp.prev.next = tmp.next;

tmp.next.prev = tmp.prev;

}

}

}

public void printAll() {

for (DLLNode tmp = head; tmp != null; tmp = tmp.next)

System.out.print(tmp.info + " ");

}

public T find(T el) {

DLLNode tmp;

for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next);

if (tmp == null)

return null;

else return tmp.info;

}

public T getFirst() {

if (head != null)

return head.info;

else return null;

}

public T getLast() {

if (tail != null)

return tail.info;

else return null;

}

public String toString() {

String s = "[";

for (DLLNode tmp = head; tmp != null; tmp = tmp.next)

s += tmp.info + " ";

return s+"]";

}

public int length() {

int count = 0;

for (DLLNode tmp = head; tmp != null; tmp = tmp.next)

count++;

return count;

}

public Object[] toArray() {

Object[] ar = new Object[length()];

int i=0;

for (DLLNode tmp = head; tmp != null; tmp = tmp.next, i++)

ar[i] = tmp.info;

return ar;

}

public T[] toArray(T[] a) {

//create a generic array

T[] ar = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),length());

int i = 0;

for (DLLNode tmp = head; tmp != null; tmp = tmp.next, i++)

ar[i] = tmp.info;

return ar;

}

//another version

public T[] toArray(Class elemType) {

//create a generic array

T[] ar = (T[])java.lang.reflect.Array.newInstance(elemType, length());

int i = 0;

for (DLLNode tmp = head; tmp != null; tmp = tmp.next, i++)

ar[i] = tmp.info;

return ar;

}

public Iterator iterator() {

return new DLLIterator();

}

private class DLLIterator implements Iterator {

DLLNode tmp = head;

public boolean hasNext() {

return tmp != null;

}

public T next() {

T info = tmp.info;

tmp = tmp.next;

return info;

}

public void remove() {

// not implemented

}

}

// node of generic doubly linked list class

class DLLNode {

public T info;

public DLLNode next, prev;

public DLLNode() {

next = null; prev = null;

}

public DLLNode(T el) {

info = el; next = null; prev = null;

}

public DLLNode(T el, DLLNode n, DLLNode p) {

info = el; next = n; prev = p;

}

}

}