Finding cycles in a graph (not necessarily Hamiltonian or visiting all the nodes)

Question

I have graph like one in Figure 1 (the first image) and want to connect the red nodes to have cycle, but cycles do not have to be Hamiltonian like Figure 2 and Figure 3 (the last two images). The problem has much bigger search space than TSP since we can visit a node twice. Like the TSP, it is impossible to evaluate all the combinations in a large graph and I should try heuristic, but the problem is that, unlike the TSP, the length of cycles or tours is not fixed here. Because, visiting all the blue nodes is not mandatory and this cause having variable length including some of the blue nodes. How can I generate a possible "valid" combination every time for evaluation? I mean, a cycle can be {A, e, B, l, k, j, D, j, k, C, g, f, e} or {A, e, B, l, k, j, D, j, i, h , g, C, g, f, e}, but not {A, e, B, l, k, C, g, f, e} or {A, B, k, C, i, D}.

Update: The final goal is to evaluate which cycle is optimal/near optimal considering length and risk (see below). So I am not only going to minimize the length but minimizing the risk as well. This cause not being able to evaluate risk of cycle unless you know all its nodes sequence. Hope this clarifies why I can not evaluate new cycle at the middle of its generating process. We can:

• generate and evaluate possible cycles one by one;
• or generate all possible cycles and then do their evaluation.

Definition of the risk: Assume cycle is a ring which connects primary node (one of the red nodes) to all other red nodes. In case of failure in any part (edge) of the ring, no red nodes should be disconnected form the primary node (this is desired). However there are some edges we have to pass twice (due to not having Hamiltonian cycle which connects all the red nodes) and in case of failure in those edges, some of red nodes may be totally disconnected. So risk of cycle is summation of the length of risky edges (we have twice in our ring/tour) multiplied by number of red nodes we lose in case of cutting each risky edge.

A real example of 3D graph I am working on including 5 red nodes and 95 blue nodes is in below:

And here is link to Excel sheet containing adjacency matrix of the above graph (the first five nodes are red and the rests are blue).

Answer 1

Upon a bit more reflection, I decided it's probably better to just rewrite my solution, as the fact that you can use red nodes twice, makes my original idea of mapping out the paths between red nodes inefficient. However, it isn't completely wasted, as the blue nodes between red nodes is important.

You can actually solve this using a modified version of BFS, as more-less a backtracking algorithm. For each unique branch the following information is stored, most of which simply allows for faster rejection at the cost of more space, only the first two items are actually required:

• The full current path. (list with just the starting red node)
• The remaining red nodes. (initially all red nodes)
• The last red node. (initially the start red node)
• The set of blue nodes since last red node. (initially empty)
• The set of nodes with a count of 1. (initially empty)
• The set of nodes with a count of 2. (initially empty)

The algorithm starts with a single node then expands adjacent nodes using BFS or DFS, this repeats until the result is a valid tour or is the node to be expanded is rejected. So the basic psudoish code (current path and remaining red points) looks something like below. Where rn is the set of red nodes, t is the list of valid tours, p/p2 is a path of nodes, r/r2 is a set of red nodes, v is the node to be expanded, and a is a possible node to expand to.

function PATHS2HOME(G,rn)
    create a queue Q
    create a list t
    p = empty list
    v ← rn.pop()
    r ← rn
    add v to p
    Q.enqueue((p,r))
    while Q is not empty
        p, r ← Q.dequeue()
        if r is empty and the first and last elements of p are the same:
            add p to t
        else
            v ← last element of p
            for all vertices a in G.adjacentVertices(v) do 
                if canExpand(p,a)
                    p2 ← copy(p)
                    r2 ← copy(r)
                    add a to the end of p2
                    if isRedNode(a) and a in r2
                        remove a from r2
                    Q.enqueue( (p2,r2) )
    return t

The following conditions prevent expansion of a node. May not be a complete list.

• Red nodes:
  • If it is in the set of nodes that have a count of 2. This is because the red node would have been used more than twice.
  • If it is equal to the last red node. This prevents "odd" tours when a red node is adjacent to three other blue nodes. Thus say the red node A, was adjacent to blue nodes b, c and d. Then you would end a tour where part of the tour looks like b-A-c-A-d.
• Blue nodes:
  • If it is in the set of nodes that have a count of 2. This is because the red node would have been used more than twice.
  • If it is in the set of blue nodes since last red node. This is because it would cause a cycle of blue nodes between red nodes.

Possible optimizations:

• You could map out the paths between red nodes, use that to build something of a suffix tree, that shows red nodes that can be reached given the following path Like. The benefit here is that you avoid expanding a node if the path that expansion leads to red nodes that have already been visited twice. Thus this is only a useful check once at least 1 red node has been visited twice.
• Use a parallel version of the algorithm. A single thread could be accessing the queue, and there is no interaction between elements in the queue. Though I suspect there are probably better ways. It may be possible to cut the runtime down to seconds instead of hundreds of seconds. Although that depends on the level of parallelization, and efficiency. You could also apply this to the previous algorithm. Actually the reasons for which I switched to using this algorithm are pretty much negated by
• You could use a stack instead of a queue. The main benefit here is by using a depth-first approach, the size of the queue should remain fairly small.