Algorithm for finding all closed walks in a graph from a given vertex

I have graph which is undirected, no multiple/parallel edges, and each edge is weighted with a distance. I am looking to find closed walks in the graph between a certain minimum and maximum total distance. I would also like to be able to set a limit on the amount of repeated distance in the walk, for example, if an edge with 10 is traversed twice, there is a repeated distance of 10. Setting the repeated distance to 0 should find closed paths in the graph (as opposed to walks). Lastly, although it would be nice to find all closed walks, I'm not sure if this is feasible for larger graphs where there are thousands/millions of potential routes, since I believe this would take exponential time. So, I am currently trying to find a few closed walks that are the best according to a heuristic function, in order for the algorithm to finish in a reasonable amount of time.

Edit: approximate performance requirements - the graph I am using to test currently has 17,070 nodes and 23,026 edges. Loops that are generated contain approximately 50 edges, taking on the order of 20 seconds to find, however I would like to find loops of longer distances (~100 edges) ideally also in the time frame of <1 minute.

Here is my current approach:

graph.go:

package graph

import (
	"fmt"

	"github.com/bgadrian/data-structures/priorityqueue"
)

// A Graph struct is a collection of nodes and edges represented as an adjacency list.
// Each edge has a weight (float64).

type Edge struct {
	HeuristicValue 	int // Lower heuristic = higher priority
	Distance float64
}

type Graph struct {
	Edges map[int]map[int]Edge // adjacency list, accessed like Edges[fromId][toId]
}

func (g *Graph) FindAllLoops(start int, minDistance float64, maxDistance float64, maxRepeated float64, routesCap int) []Route {
	// Find all loops that start and end at node start.
	// A loop is a closed walk through the graph.
	
	loops := []Route{}
	loopCount := 0

	queue, _ := priorityqueue.NewHierarchicalHeap(100, 0, 100, false)
	
	queue.Enqueue(*NewRoute(start), 0)
	size := 1

	
	distanceToStart := getDistanceToStart(g, start)
	
	for size > 0 {
		// Pop the last element from the stack
		temp, _ := queue.Dequeue()
		size--
		route := temp.(Route)

		// Get the last node from the route
		lastNode := route.LastNode()
	
		// If the route is too long or has too much repeated distance,
		// don't bother exploring it further
		if route.Distance + distanceToStart[route.LastNode()] > maxDistance || route.RepeatedDistance > maxRepeated {
			continue
		}
		
		// Now we need to efficiently check if the total repeated distance is too long

		// If the last node is the start node and the route is long enough, add it to the list of loops
		if lastNode == start && route.Distance >= minDistance && route.Distance <= maxDistance {
			loops = append(loops, route)
			
			loopCount++
			if loopCount >= routesCap {
				return loops
			}
		}

		// Add all the neighbours of the last node to the stack
		for neighbour := range g.Edges[lastNode] {
			// newRoute will be a copy of the current route, but with the new node added
			newRoute := route.WithAddedNode(neighbour, g.Edges[lastNode][neighbour])
			
			queue.Enqueue(newRoute, newRoute.Heuristic())
			size++
		}
	}
	return loops
}

route.go:

package graph

import (
	"fmt"
)

// A route is a lightweight struct describing a route
// It is stored as a sequence of nodes (ints, which are the node ids)
// and a distance (float64)
// It also counts the total distance that is repeated (going over the same
// edge twice)
// To do this, it stores a list of edges that have been traversed before
type Route struct {
	Nodes    []int
	Distance float64
	Repeated []IntPair // two ints corresponding to the nodes, orderedd by (smallest, largest)
	RepeatedDistance float64
	Heuristic int // A heuristic for the type of Routes we would like to generate
	LastWay int
}

type IntPair struct {
	A int
	B int
}

// WithAddedNode adds a node to the route
func (r *Route) WithAddedNode(node int, edge Edge) Route {

	newRoute := Route{Nodes: make([]int, len(r.Nodes) + 1), Distance: r.Distance, Repeated: make([]IntPair, len(r.Repeated), len(r.Repeated) + 1), RepeatedDistance: r.RepeatedDistance, Ways: r.Ways, LastWay: r.LastWay}
	copy(newRoute.Nodes, r.Nodes)
	copy(newRoute.Repeated, r.Repeated)
	
	newRoute.Nodes[len(r.Nodes)] = node
	newRoute.Distance += edge.Distance
	
	// Get an IntPair where A is the smaller node id and B is the larger
	var pair IntPair
	if newRoute.Nodes[len(newRoute.Nodes)-2] < node {
		pair = IntPair{newRoute.Nodes[len(newRoute.Nodes)-2], node}
	} else {
		pair = IntPair{node, newRoute.Nodes[len(newRoute.Nodes)-2]}
	}
	
	// Check if the edge has been traversed before
	found := false
	for _, p := range newRoute.Repeated {
		if p == pair {
			newRoute.RepeatedDistance += edge.Distance
			found = true
			break
		}
	}

	if !found {
		newRoute.Repeated = append(newRoute.Repeated, pair)
	}
	
        // Current heuristic sums heuristics of edges but this may change in the future
        newRoute.Heuristic += edge.HeuristicValue
	
	return newRoute
}

func (r *Route) Heuristic() int {
	return r.Heuristic
}

func (r *Route) LastNode() int {
	return r.Nodes[len(r.Nodes)-1]
}

Here are the things I have currently done to speed up the algorithm so far:

1. Rather than finding all loops, find the first few loops according to a given heuristic.
2. Trimmed the graph to remove almost all nodes of degree 2 where possible, replacing them with a single edge with weight = sum of the original two edges.
3. Used a slice to store repeated edges as opposed to a map.
4. Used Dijkstra's algorithm to find the shortest distance from the start node to every other node. If a route is unable to make it back in this amount of distance, discard it immediately. (Code for the algorithm implementation is not included in the post because it only accounts for ~4% of runtime)

According to the Go profiler, the WithAddedNode method in route.go is accounting for 68% of the runtime, with time in that method approximately evenly split between runtime.memmove and runtime.makeslice (calling runtime.mallocgc). Essentially, I believe most of the time is spent copying Routes. I would greatly appreciate any feedback on how to improve this algorithm's runtime or any possible alternative approaches. Let me know if there is any additional information I can provide. Thank you so much!

The standard algorithm to find all paths between two vertices is:

• Apply Dijkstra to find cheapest path
• Increment cost of links in path
• Repeat until no new path found

In your case you want the paths to return to the starting vertex. The algorithm can easily be modified to do this

• Split the starting vertex, S, into two, S1 and S2.
• LOOP V over vertices connected to S.
  • Add zero cost edge between S1 and V
  • Add zero cost edge between S2 and V
• Remove S and its edges.
• Run standard algorithm to find all paths between S1 and S2

You will need to modify the Dijkstra code to take account of your other constraints - maximum length and the "heuristic"

Performance

Although you say you are concerned about performance on large graphs, you give no indication of your required performance. I will try to provide an estimate.

I do not know anything about the performance of GO, so I will assume it is the same as C++ with which I am familiar.

Here are some performance measurements for C++:

Run time for running the Dijkstra algorithm to find the cheapest paths from one randomly selected vertex to every other vertex on large graphs downloaded from https://dyngraphlab.github.io/. Longest result from 3 runs using the graphex application.

Suppose that you wish to find 10 closed paths - multiply the above run times by 10.