How to get predecessor and successors from an adjacency matrix
- by NickTFried
Hi I am am trying to complete an assignment, where it is ok to consult the online community. I have to create a graph class that ultimately can do Breadth First Search and Depth First Search. I have been able to implement those algorithms successfully however another requirement is to be able to get the successors and predecessors and detect if two vertices are either predecessors or successors for each other. I'm having trouble thinking of a way to do this. I will post my code below, if anyone has any suggestions it would be greatly appreciated.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Graph<T>
{
public Vertex<T> root;
public ArrayList<Vertex<T>> vertices=new ArrayList<Vertex<T>>();
public int[][] adjMatrix;
int size;
private ArrayList<Vertex<T>> dfsArrList;
private ArrayList<Vertex<T>> bfsArrList;
public void setRootVertex(Vertex<T> n)
{
this.root=n;
}
public Vertex<T> getRootVertex()
{
return this.root;
}
public void addVertex(Vertex<T> n)
{
vertices.add(n);
}
public void removeVertex(int loc){
vertices.remove(loc);
}
public void addEdge(Vertex<T> start,Vertex<T> end)
{
if(adjMatrix==null)
{
size=vertices.size();
adjMatrix=new int[size][size];
}
int startIndex=vertices.indexOf(start);
int endIndex=vertices.indexOf(end);
adjMatrix[startIndex][endIndex]=1;
adjMatrix[endIndex][startIndex]=1;
}
public void removeEdge(Vertex<T> v1, Vertex<T> v2){
int startIndex=vertices.indexOf(v1);
int endIndex=vertices.indexOf(v2);
adjMatrix[startIndex][endIndex]=1;
adjMatrix[endIndex][startIndex]=1;
}
public int countVertices(){
int ver = vertices.size();
return ver;
}
/*
public boolean isPredecessor( Vertex<T> a, Vertex<T> b){
for()
return true;
}*/
/*
public boolean isSuccessor( Vertex<T> a, Vertex<T> b){
for()
return true;
}*/
public void getSuccessors(Vertex<T> v1){
}
public void getPredessors(Vertex<T> v1){
}
private Vertex<T> getUnvisitedChildNode(Vertex<T> n)
{
int index=vertices.indexOf(n);
int j=0;
while(j<size)
{
if(adjMatrix[index][j]==1 && vertices.get(j).visited==false)
{
return vertices.get(j);
}
j++;
}
return null;
}
public Iterator<Vertex<T>> bfs()
{
Queue<Vertex<T>> q=new LinkedList<Vertex<T>>();
q.add(this.root);
printVertex(this.root);
root.visited=true;
while(!q.isEmpty())
{
Vertex<T> n=q.remove();
Vertex<T> child=null;
while((child=getUnvisitedChildNode(n))!=null)
{
child.visited=true;
bfsArrList.add(child);
q.add(child);
}
}
clearVertices();
return bfsArrList.iterator();
}
public Iterator<Vertex<T>> dfs()
{
Stack<Vertex<T>> s=new Stack<Vertex<T>>();
s.push(this.root);
root.visited=true;
printVertex(root);
while(!s.isEmpty())
{
Vertex<T> n=s.peek();
Vertex<T> child=getUnvisitedChildNode(n);
if(child!=null)
{
child.visited=true;
dfsArrList.add(child);
s.push(child);
}
else
{
s.pop();
}
}
clearVertices();
return dfsArrList.iterator();
}
private void clearVertices()
{
int i=0;
while(i<size)
{
Vertex<T> n=vertices.get(i);
n.visited=false;
i++;
}
}
private void printVertex(Vertex<T> n)
{
System.out.print(n.label+" ");
}
}
