How to cover maximum number of nodes via given path in a graph?

Question

I am trying to find out the maximum number of covered nodes via a path in a given graph. I have made a program using recursion but it is giving answer only for some simple graph not on complicated graph.

Input is given in a string array like 1#2: means node 1 is connected to node 2 or vice-versa.

I have made a matrix of total nodes size and if node is connected set 1 else -1 in matrix. This matrix is used to calculate maximum covered node in path.

Code:

import java.io.*;
import java.util.*; 

public class Medium 
{ 
 public static int node_covered;
 public static int big=0;
 public static boolean[] visited;
 public static int matrix_length;
 public static String[][] matrix;

 public static String[] input=new String[]
 //answer is 7.
{"1#2", "2#3","3#4","3#5","5#6","5#7","6#7","7#8"};

public static void main(String[] args){
      int total_nodes=maxno_city(input);
      System.out.println(total_nodes);
  }

public static int maxno_city(String[] input1)
{
int ln=input1.length;
HashSet hs = new HashSet();

for(int i=0; i<ln;i++)
{
    String[] temp=input1[i].split("#");     
    hs.add(temp[0]);        
    hs.add(temp[1]);    
}

matrix_length=hs.size();
hs.clear();
matrix=new String[matrix_length][matrix_length];
//initialize matrix
for (String[] row : matrix)
     Arrays.fill(row, "-1");

//System.out.println(Arrays.deepToString(matrix));

for(int i=0;i<matrix_length;i++)
{
    for(int j=0; j<matrix_length;j++)
    {
        String[] temp=input1[i].split("#");
        int first=Integer.parseInt(temp[0])-1;
        int second=Integer.parseInt(temp[1])-1;
        matrix[first][second]="1";
        matrix[second][first]="1";
    }
}
//System.out.println(Arrays.deepToString(matrix));
//initialized
//now start work on matrix
for(int i=0;i<matrix_length;i++)
{
    for(int j=0; j<matrix_length;j++)
    {
        visited=new boolean[matrix_length];
        if(matrix[i][j].equals("1"))
        {
            node_covered=0;
            getNextPath(j,i);
            //visited[i]=true;
        }   
    }
}
    return big;
}

//recursive method
public static void getNextPath(int path,int visited_node)
{
    boolean flag=false;
    visited[visited_node]=true;
    node_covered++;
    for(int i=0;i<matrix_length;i++)
    {
        if(matrix[path][i].equals("1") && visited[i]==false)
        {
            //visited[i]=true;
            flag=true;
            getNextPath(i,path);
            //visited[i]=false;
        }
    }
    if(flag==false)
    {
        if(big<node_covered)
        {
            big=node_covered;
            //System.out.println(big);
        }
    }
    else
    {
        node_covered--;
    }
    //visited[path]=false;
 }
}

Where I am doing mistake in above code?

Answer 1

Your main issue is that you do not store the complete matrix. This loop:

for(int i=0;i<matrix_length;i++)
{
    for(int j=0; j<matrix_length;j++)
    {
        String[] temp=input1[i].split("#");
        int first=Integer.parseInt(temp[0])-1;
        int second=Integer.parseInt(temp[1])-1;
        matrix[first][second]="1";
        matrix[second][first]="1";
    }
}

does not correctly iterate over input1 to populate matrix. By consequent, the last inputs are ignored (you can also see that j is not used at all within the inner loop). You should thus change it to a correct iteration:

for (int i = 0; i < input1.length; i++)
{
    String[] temp = input1[i].split("#");
    int first = Integer.parseInt(temp[0]) - 1;
    int second = Integer.parseInt(temp[1]) - 1;
    matrix[first][second] = "1";
    matrix[second][first] = "1";
}

(You may also want to improve it further to a foreach loop since you don't need the value of i)

I discovered this by debugging your code and figuring out that it does not recurse into some nodes, and then I figured that matrix was incomplete. You should print matrix to check whether it is correct.

Some other issues:

• You must reset your visited array when backtracking, otherwise you will not evaluate 2 different paths that go through the same node (uncomment visited[path]=false;)
• You do not need the flag: in both cases, you should check if you have a new "high score" and decrease node_covered before leaving the loop
• Your code will fail if there is a city that is not connected to the rest of the graph, because your Set hs will be too small. Try to look for the node with the highest number instead.

Some possible improvements:

• Convert matrix to a boolean matrix. This will also remove the need to initialize it.
• You do not need 2 parameters for getNextPath(). Try to do everything you need with visited_node at the calling place. You should then be able to simplify it further.
• If you manage to reduce it to 1 parameter, you will not need 2 nested for loops to initiate the recursion.