Get the longest route traveled in a graph

Question

I have an array of nodes that are connected to each other

I have below network of nodes. Here 0 is the starting point, I want to travel as many nodes as possible with a node traveled only once. Also during a trip from 0 to destination node, I want to have only a single odd numbered node (like 1, 3, 5, 7). Now I need to find out the longest route I can travel from my beginning position 0.

Example :

int[] array = { 0, 9, 0, 2, 6, 8, 0, 8, 3, 0 };

In above graph, below are possibilities:

0 -> 6 -> 4 (valid path, length = 3 nodes)
0 -> 9 -> 1 (Not valid path, length as we have 2 odd numbers here 1 & 9)
0 -> 2 -> 3 -> 8 (valid path, length = 4 nodes)
0 -> 2 -> 3 -> 8 -> 5 (Not valid path as we have 2 odd numbers here 3 & 5)
0 -> 2 -> 3 -> 8 -> 7 (Not valid path as we have 2 odd numbers here 3 & 7)

So the answer is 4 for this input.

Below is the program I am trying.

public int process(int[] array) {
    int count = array.length;
    ArrayList<Integer>[] branches = new ArrayList[count];
    for (int i = 0; i < count; i++) {
        branches[i] = new ArrayList<>();
    }
    int begin = 0;

    for (int i = 0; i < count; i++) {
        if (array[i] != i) {
            branches[i].add(array[i]);
            branches[array[i]].add(i);
        }
    }

    Arrays.stream(branches).forEach(System.out::println);

    Queue<Network> networkQueue = new LinkedList<Network>();
    ArrayList<Integer> networkList = branches[begin];
    networkList.forEach(value -> {
        Network net = new Network(0, value);
        networkQueue.add(net);
    });

    System.out.println("printing starting nodes.......");
    List<Network> nodes = new ArrayList<>();
    for (Network n : networkQueue) {
        nodes.add(n);
        System.out.println(n.value + " : " + n.road);
    }

    int result = 0;
    return result;
}

class Network {
    int road, value;

    public Network(int road, int value) {
        this.road = road;
        this.value= value;
    }

}

The program prints the branches and the nodes for the starting point i.e 0 :

[2, 6, 9]
[9]
[0, 3]
[2, 8]
[6]
[8]
[4, 0]
[8]
[5, 7, 3]
[1, 0]
printing starting nodes.......
2 : 0
6 : 0
9 : 0

I got stuck on finding the longest route, how to proceed next with this program, please help me here.

Answer 1

this is in c++, but i think it works the same:

#include <vector>

using namespace std;
void dfs(vector<vector<int>> &graphs, int nextidx, int& ticket, int& cities);

int solution(vector<int>& T)
{
    if (T.empty()) return 0;

    vector<vector<int>> graphs(T.size());

    int ticket = 1;
    int citiesmax = 0;
    for (int i = 1; i < T.size(); ++i) {
        graphs[T[i]].emplace_back(i);
    }

    //    0-> 2, 6, 9
    //    1-> _
    //    2-> 3
    //    3-> 8
    //    4-> _
    //    5-> _
    //    6-> 4
    //    7-> _
    //    8-> 5, 7
    //    9-> 1

    
    for (int i = 0; i < graphs[0].size(); ++i)
    {
        int nextidx = graphs[0][i];
        int cities = 1;
        dfs(graphs, nextidx, ticket, cities);
        if(cities > citiesmax)
        {
            citiesmax = cities;
        }
    }
    
    return citiesmax;

}

void dfs(vector<vector<int>> &graphs, int nextidx, int &ticket, int& cities)
{
    if (graphs[nextidx].empty()) return;


    for (int i = 0; i < graphs[nextidx].size(); ++i)
    {
        if (graphs[nextidx][i] % 2 > 0)
        {
            if (ticket == 0) return;
            ticket--;       
        }
        int idx = graphs[nextidx][i];
        cities++;
        dfs(graphs, idx, ticket, cities);
    }
    return;
}


int main()
{
    vector<int> test1 = {0,9,0,2,6,8,0,8,3,0};


    int res = solution(test1);
    
}

Answer 2

This is a classic Depth First Search with backtracking problem.

The gist of this algorithm is as follow. Starting from the start node, visit all its neighbors that have not been visited and do not break the max odd number node of 1 restriction. Add the current node to the current path and increment odd number node counter if the current node number is odd. Do this recursively until you've exhausted all valid paths for one neighbor, then backtrack for the remaining neighbors.

The following is the implementation with your provided input as the test case. I also added another list of list variable that is called res. This will give you all the valid longest path. I used a map to represent a graph, but you can modify this as you like.

import java.util.*;

public class LongestRoute {
    private static int maxLen = 0;
    private static List<List<Integer>> res = new ArrayList<>();

    public static int longestRouteWithRestrictions(Map<Integer, List<Integer>> graph, int startNode) {
        Set<Integer> visited = new HashSet<>();
        visited.add(startNode);
        List<Integer> path = new ArrayList<>();
        path.add(startNode);

        dfs(graph, startNode, visited, startNode % 2 == 1 ? 1 : 0, path);
        return maxLen;
    }

    private static void dfs(Map<Integer, List<Integer>> graph, int currentNode, Set<Integer> visited, int oddNumNodeCnt, List<Integer> path) {
        if(path.size() > maxLen) {
            maxLen = path.size();
            res.clear();
            res.add(new ArrayList<>(path));
        }
        else if(path.size() == maxLen) {
            res.add(new ArrayList<>(path));
        }
        for(int neighbor : graph.get(currentNode)) {
            if(visited.contains(neighbor) || oddNumNodeCnt == 1 && neighbor % 2 != 0) {
                continue;
            }
            path.add(neighbor);
            visited.add(neighbor);
            dfs(graph, neighbor, visited, oddNumNodeCnt + (neighbor % 2 != 0 ? 1 : 0), path);
            path.remove(path.size() - 1);
            visited.remove(neighbor);
        }
    }
    public static void main(String[] args) {
        //Init a test graph
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Integer[] neighbors_0 = {2,6,9};
        List<Integer> list0 = Arrays.asList(neighbors_0);
        graph.put(0, list0);

        Integer[] neighbors_1 = {9};
        List<Integer> list1 = Arrays.asList(neighbors_1);
        graph.put(1, list1);

        Integer[] neighbors_2 = {0,3};
        List<Integer> list2 = Arrays.asList(neighbors_2);
        graph.put(2, list2);

        Integer[] neighbors_3 = {2,8};
        List<Integer> list3 = Arrays.asList(neighbors_3);
        graph.put(3, list3);

        Integer[] neighbors_4 = {6};
        List<Integer> list4 = Arrays.asList(neighbors_4);
        graph.put(4, list4);

        Integer[] neighbors_5 = {8};
        List<Integer> list5 = Arrays.asList(neighbors_5);
        graph.put(5, list5);

        Integer[] neighbors_6 = {0,4};
        List<Integer> list6 = Arrays.asList(neighbors_6);
        graph.put(6, list6);

        Integer[] neighbors_7 = {8};
        List<Integer> list7 = Arrays.asList(neighbors_7);
        graph.put(7, list7);

        Integer[] neighbors_8 = {5,7};
        List<Integer> list8 = Arrays.asList(neighbors_8);
        graph.put(8, list8);

        Integer[] neighbors_9 = {0,1};
        List<Integer> list9 = Arrays.asList(neighbors_9);
        graph.put(9, list9);

        System.out.println(longestRouteWithRestrictions(graph, 0));
        for(List<Integer> route : res) {
            System.out.println(route.toString());
        }
    }
}

Answer 3

You can try below approach, which should be relatively simple to implement as well as track. Firstly, you need to form a Node class which would have information about 3 things:

1. Max length of the path traveled so far while visiting all the nodes until this node from node 0, visiting each node just once.
2. A variable called oddCounter that counts the number of odd nodes encountered so far in this path.
3. A boolean variable isVisited to know if this node is already visited or not.

Now just implement BFS with nodes being as instance of this type of class defined above and while doing BFS, you just need to update each node variables accordingly.

Please note that you need to do BFS to all nodes starting from node 0, each time resetting the values of above 3 variables so you can keep track of the further paths in that route through this node. You can terminate the loop beyond certain nodes if you have already found one odd node. This way it would be more flexible in future as well where you might want to include maybe 2 or 3 odd numbered nodes in your path as compared to just one node currently.

Also, you would need to create a resultList and currList where you create a new currList everytime you traverse to a new node and update resultList with currList if length of currList is greater than the length of resultList as per the constraints we have.

I am sure that this approach can be optimized further using Dynamic Programming. As you know the route length and number of odd nodes until a given node say i, you can just do a BFS now from ith node and using memoization to keep track of previous route length and odd numbered nodes, which we are already tracking using above class we created.

Answer 4

I'm sorry I don't have time to code it, but here is the logic i would apply.

1. starting from 0 the program generate linked lists of neighbors. In our case:

   [0->2]
   [0->9]
   [0->6]
   

2. checking neighbors (last elements in lists): if they are odd then increment a counter that refer to that path list. If the odd counter ==2 then erase that list from further analsys

3. for each list start again from 1. using last element as input. When no more VALID lists can be generated find the one with longest path, counting elements.

Just pay attention that a valid neighbor cannot be the same as the previous element in the list to avoid infinite loops: The only valid list generable by [0->2] it's [0->2->3], and not [0->2->0]