How to get predecessor and successors from an adjacency matrix

Question

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+" ");
 }

}

Answer 1

Look here.

If v is reachable from u, then u is a predecessor of v and v is a successor of u. If there is an arc from u to v, then u is a direct predecessor of v, and v is a direct successor of u.

It should be trivial to implement this since you already seem to have the adjacency matrix built and also the traversal functions. So just run BFS / DFS and find what you're interested in.

Note that, unless your graph is directed, it makes no sense to talk about predecessors and successors, since the edges are bidirectional. Your graph seems to be undirected, so are you sure the assignment isn't to find if one node is reachable from another or not?

Answer 2

I believe this function is in error:

 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 assignment is saying, effectively, that the edges are directionless. 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 passed 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 deleteEdge() method should probably be assigning to 0, not 1 (and should only do so once, like addEdge()).