2

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.

0

6 Answers 6

7

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.

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.

3

Try this:

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

}
1
  • Hey solution is giving error for Graph class/interface. So do you have any different file for it?. Thanks in advance
    – Sagar007
    Feb 23, 2015 at 9:40
2

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)

0
1

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

0

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) ] }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.