Notes

//name: date:
//for use with EdgeList, DFS-BFS, and EdgeListCities

import java.io.*;
import java.util.*;

class Vertex implements VertexInterface
{
private final String name;
private ArrayList<Vertex> adjacencies;

public Vertex(String n)
{
name = n;
adjacencies = new ArrayList();
}

public String getName()
{
return name;
}

public ArrayList<Vertex> getAdjacencies()
{
return adjacencies;
}
/* enter your code here */
}

public class TJGraphAdjList_5G_Dhanasekar
{
private ArrayList<Vertex> vertices = new ArrayList<Vertex>();
private Map<String, Integer> nameToIndex = new HashMap<String, Integer>();

public void addVertex(String n)
{
boolean contains = false;
for(int x = 0; x < vertices.size(); x++)
{
if(vertices.get(x).getName().equals(n))
{
contains = true;
}
}
if(!contains)
{
vertices.add(new Vertex(n));
nameToIndex.put(n, vertices.size() - 1);
}

}

public void addEdge(String n, String n1)
{
int index = nameToIndex.get(n);
Vertex temp = vertices.get(index);
temp.getAdjacencies().add(new Vertex(n1));
}

public String toString()
{
String y = "";
for(int x = 0; x < vertices.size(); x++)
{
y += vertices.get(x).getName() + " [ ";
for(int z = 0; z < vertices.get(x).getAdjacencies().size(); z++)
{
y += vertices.get(x).getAdjacencies().get(z).getName() + " ";
}
y += "]n";
}
return y;
}

public Map<String, Integer> getVertexMap()
{
return nameToIndex;
}

public List<Vertex> depthFirstSearch(String name)
{
ArrayList<Vertex> tempL = new ArrayList<Vertex>();
Stack<Vertex> tempS = new Stack<Vertex>();


while(tempS.size() != 0)
{
tempS.push(new Vertex(name));
tempL.add(tempS.pop());
ArrayList<Vertex> temp = vertices.get(nameToIndex.get(name)).getAdjacencies();
for(int x = 0; x < temp.size(); x++)
{
Vertex n1 = temp.get(x);
boolean contains = false;
if(tempL.contains(n1))
{
contains = true;
}
if(!contains)
{
tempS.push(n1);
}
}
name = tempS.pop().getName();
}
return tempL;

}

public List<Vertex> breadthFirstSearch(String name)
{
ArrayList<Vertex> tempL = new ArrayList<Vertex>();
Queue<Vertex> tempS = new Queue<Vertex>();


while(tempS.size() != 0)
{
tempS.add(new Vertex(name));
tempL.add(tempS.remove());
ArrayList<Vertex> temp = vertices.get(nameToIndex.get(name)).getAdjacencies();
for(int x = 0; x < temp.size(); x++)
{
Vertex n1 = temp.get(x);
boolean contains = false;
if(tempL.contains(n1))
{
contains = true;
}
if(!contains)
{
tempS.push(n1);
}
}
name = tempS.pop().getName();
}
return tempL;
}

}
interface VertexInterface
{
public String toString(); //just return the name
public String getName();
public ArrayList<Vertex> getAdjacencies();
}

interface TJGraphAdjListInterface
{
/********************* Graphs 3: EdgeList *******************************/
public List<Vertex> getVertices();
public Vertex getVertex(int i) ;

public Vertex getVertex(String vertexName);
public Map<String, Integer> getVertexMap();
public void addVertex(String v);
public void addEdge(String source, String target);
public String toString();




/*********************Graphs 4: DFS and BFS ****************************/
//public List<Vertex> depthFirstSearch(String name);
// public List<Vertex> breadthFirstSearch(String name);
// public List<Vertex> depthFirstRecur(String name);



/****************Graphs 5: EdgeList with Cities *********/
// public void graphFromEdgeListData(String fileName) throws FileNotFoundException;
// public int edgeCount();
// public boolean isReachable(String source, String target);
// public boolean isConnected();
}