Longest path in adjacency matrix in R

Question

Hypothetical scenario to have a descriptive example: I've a model consisting of 10 parts (vertices) to be put together. Each part can be connected to others (edges) as defined by a connection table.

There's a shortest.paths function in igraph. However here the aim is to find a way to calculate the longest path in the adjacency matrix. Resulting in a path using as many parts as possible, ideally all, so no part of the model is left alone in the end. MWE as follows:

library(igraph)
connections <- read.table(text="A B 
1 2
1 7
1 9
1 10
2 7
2 9  
2 10 
3 1  
3 7  
3 9 
3 10 
4 1  
4 6  
4 7 
7 5  
7 9  
7 10  
8 9 
8 10 
9 10", header=TRUE)  

adj <- get.adjacency(graph.edgelist(as.matrix(connections), directed=FALSE))
g1 <- graph_from_adjacency_matrix(adj, weighted=TRUE, mode="undirected")
plot(g1)

Edit: The result should be something like: for instance if the first part of the model is 8 it could be combined with 9 or 10. Let's say 10 is selected next part can be either 1,2,7 or 9. If 9 is selected as next the follow up could be 1,2,3,7 or 8. If then 8 is selected the model would be finished as part 10 is already in use. The question then would be how to find a way/path to put together as many parts as possible, ideally all of them. The latter would be possible only by starting with 6 or 5.

Answer 1

Tell me if i get it right, you are trying to find a path, that touch the maximum number of nodes? If that so this is basically an instance of the Hamiltonian path problem, I would say an easier version of it if you can pass on a node more than 1 time. You can try to watch that algorithm. to respect you edit maybe, you can try to see the graphs search algorithms, you can find something here, however be advise that this type of algorithms are quite heavy on the memory complexity side.

Answer 2

There are cycles in your graphs, and I don't think you have stated that we cannot use the same vertex (part) more than once: and in this case the longest path might be infinitely long as you can traverse the cycle infinitely many times and then proceed to your destination.

As per your edit, I think this is not allowed. You can use dynamic programming for this I hope. You can start with DFS like algorithm and mark all the vertex except starting as unvisited. Then apply recursion to choose maximum between the longest paths from all the possible vertex we can reach (except which are already visited) from that given vertex.

It is an NP-hard problem, so you would have to check all the possible paths!

You can see: https://en.wikipedia.org/wiki/Longest_path_problem . You will have modify the algorithm to work in graphs with cycle by adding, as stated earlier, a flag to tell which vertices are already visited.