adjacency matrix in java or c++ to find connected nodes

Question

Hi

I am given a problem where I have been given N nodes in a graph that are interconnected to each other then given a matrix which lists down a node being connected to another (1 if it is, 0 if not). I am wondering how to best approach this problem. I think these are adjacency matrix? But how would I implement that ...

Basically what I am trying to get out of these is find whether a particular node is connected to all other nodes in a given set 'S'. And whether selected items are clique or not...

I'd appreciate any hints.

Answer 1

Hint: So you have your adjacency matrix M which tells you if two nodes are directly connected. Then what does M^2 gives you? It tells you if there is a path of length 2 between two nodes.

I let you imagine what are M^3,... , M^inf (when you reach the fixpoint)

Answer 2

You can implement this using a 2-dimensional array of booleans. So, if node i is connected to node j, then myarray[i][j] would be true. If your edges are not directional, then myarray[j][i] would be true whenever myarray[i][j] is.

This can also be extended to weighted edges by using integers (or another numeric type) instead of booleans as the elements of the array.

Answer 3

The easiest way to do this would be to use a square matrix (2d array), either of booleans to show the presence or absence of a connection or integers to represent the cost of traversal. For a sparse graph, however, you may get better compression by using jagged arrays and then storing which nodes are adjacent to the first one. In Java, I'd probably do this by having a List<List<Integer>> where the outer list corresponds to the node in question and the inner list is all of the nodes adjacent to this one.

Assuming you decide to use a standard (uncompressed) matrix, you could find out whether a node i is adjacent to every node j in a list by iterating through the list, and then looking up A[i][j]. If any of them are false, then it is not adjacent to every item in the list, otherwise it is true. For a clique, you just have to do this for every item in the list (dropping the case where i=j and making some optimizations for an undirected graph).

An example (again in Java)

public boolean isClique(boolean[][] A, List<Integer> nodes){
  for(int i : nodes){
    for(int j : nodes){
      if(i != j){
        if(!A[i][j]) return false;
      }
    }
  }
  return true;
}

Optimizations and a solution to the Max-Clique problem are left as an exercise to the reader.

Answer 4

Using your adjacency matrix, applying the Floyd-Warshall algorithm will give you all your paths between nodes. Then you can check for particular sets.

Answer 5

You might want to use bitset or bit_vector instead of bool[][].

If you don't use a jagged array, and your connections are symmetric, consider wrapping with an accessor based on MIN() & MAX() [macros]. Storing the same data in two places is a recipe for pain. Eventually, array[i][j] != array[j][i].

E.g: getValue( int i, int j ) { return array [ MIN(i,j) ] [ MAX(i,j) ] }

Answer 6

Guys Thanks for all the answers. I am stuck at the very basic thing. I understand that we should have a 2 dim http://stackoverflow.com/Content/img/wmd/code.pngmatrix where if matrix(i,j) is 0 then i and j nodes in the graph are connected. However, how we do represent these 'nodes'

for example lets assume we are looking at this. Now we have 6 nodes and only 3 (1, 2 and 5) are clique of size 3. How do I represent that 1 is connected to 5...1 is connected to 2 ...2 is connected to 3 and such. Becaue the matrix (which is suppose to have 0's and 1s representting what is connected or not) wont have same values as nodes. so lets for exmaple say in this case we have a 3x3 matrix...how will it be represented in code that hey 2 and 5 are connected.
This is what I have so far..its not much :(

    public static void main (String [] args)
    {
        List<Integer> nodes = new LinkedList();

        //assuming there are 6 nodes
        for (int i = 0; i < 6; i ++) //is this a good way of creating 'nodes'?
            nodes.add(i);

        //matrix representing which are connected.
        //A(i,j) = 1 means i and j connected
        //A(i,j) = 0 means i and j are not connected
        int i = 3;
        int j = 3;

        int [][]A = new int [i][j];
        A[0][0] = 0; A[0][1] = 1; A[0][2] = 1;
        A[1][0] = 1; A[1][1] = 1; A[1][2] = 1;

    }
}

once I have the basic structure down ...I can begin to play with what I want from this ..like getting clique..edges and all. Thanks in advance..

Answer 7

public class AdjacencyMatrix {

private String [] nodes;

private int [][] matrix;

public AdjacencyMatrix(String [] nodes,int [][] matrix){
 this.nodes = nodes;
 this.matrix = matrix;
}

boolean isSymmetric(){
 boolean sym = true;
  for(int i=0;i<matrix.length;i++){
   for(int j=i+1; j < matrix[0].length ; j++){
    if (matrix[i][j] != matrix[j][i]){
     sym = false;
     break;
    }
   }
  }
  return sym;
}

public Graph createGraph(){
 Graph graph = new Graph();
  Node[] NODES = new Node[nodes.length];

 for (int i=0; i<nodes.length; i++){
  NODES[i] =  new Node(nodes[i]);
  graph.addNode(NODES[i]);
 }

 for(int i=0;i<matrix.length;i++){    
   for(int j=i;j<matrix[0].length;j++){
    int distance = matrix[i][j];
    if (distance != 0){      
     graph.addEdge(new Edge(NODES[i], NODES[j], distance));
    } 
   }
 }

 return graph;
}


public long pathLength(int[] path){
 long sum = 0;
 for (int i=0; i<path.length - 1; i++){
  if (matrix[path[i]][path[i+1]] != 0)
   sum += matrix[path[i]][path[i+1]];
  else {
   sum = 0;
   break;
  }
 }

 return sum;
}


public static void main(String[] args){
 String[] nodes = {"A", "B", "C", "D", "E"};
 int [][] matrix= { {0, 2, 2, 1, 0}, 
      {2, 0, 1, 0, 0}, 
      {2, 1, 0, 0, 1}, 
      {1, 0, 0, 0, 4}, 
      {0, 0, 1, 4, 7}};
 AdjacencyMatrix am = new AdjacencyMatrix(nodes, matrix);
 Graph graph  = am.createGraph();
 int[] a = {0, 2, 4, 4, 3, 0};
 int[] b = {0, 1, 2, 4, 4, 3, 0};
 graph.writeGraph(); 
 am.pathLength(a);
 am.pathLength(b);
}

}