How to get predecessor and successors from adjacency matrix
Hi I am trying to complete an assignment where it is good to consult the online community. I have to create a graph class that can ultimately do the first search and the depth of the first search. I was able to successfully implement these algorithms, however another requirement is to get successors and predecessors and determine if the two peaks are either predecessors or successors for each other. I'm having trouble thinking about how to do this. I'll post my code below, if anyone has any suggestions, we'd really appreciate it.
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+" ");
}
}
I believe this function is wrong:
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;
}
The second task effectively says that the edges are not directional. If I remove the second assignment then this test
import junit.framework.TestCase;
public class GraphTest extends TestCase {
public void testIsPredecessor() throws Exception {
Graph<Integer> graph = new Graph<Integer>();
Vertex<Integer> zero = new Vertex<Integer>(0, "zero");
Vertex<Integer> one = new Vertex<Integer>(1, "one");
Vertex<Integer> two = new Vertex<Integer>(2, "two");
graph.addVertex(zero);
graph.addVertex(one);
graph.addVertex(two);
graph.addEdge(zero, one);
graph.addEdge(one, two);
assertTrue(graph.isPredecessor(zero, one));
assertFalse(graph.isPredecessor(one, zero));
}
}
can be conveyed by the following implementation:
public boolean isPredecessor( Vertex<T> a, Vertex<T> b){
int startIndex=vertices.indexOf(a);
int endIndex=vertices.indexOf(b);
return adjMatrix[startIndex][endIndex]==1;
}
isSuccessor()
has an obvious implementation - just call isPredecessor(b, a)
. By the way, the method deleteEdge()
should probably be assigned 0, not 1 (and should only do this once, for example addEdge()
).
source to share
Take a look here .
If v is accessible from u, then u is the predecessor of v and v is the successor of u. If there is an arc from u to v, then u is the direct predecessor of v and v is the direct successor of u.
This should be trivial to implement as you already seem to have created an adjacency matrix as well as traversal functions. So just fire up BFS / DFS and find what interests you.
Note that if your graph is not directional, there is no point in talking about predecessors and successors, as the edges are bidirectional. Your graph seems to be non-directional, so are you sure that the job cannot be found if one node is accessible from another or not?
source to share