找到图中所有封闭游走的算法，适用于给定的顶点

今日不肯埋头，明日何以抬头！每日一句努力自己的话哈哈~哈喽，今天我将给大家带来一篇《找到图中所有封闭游走的算法，适用于给定的顶点》，主要内容是讲解等等，感兴趣的朋友可以收藏或者有更好的建议在评论提出，我都会认真看的！大家一起进步，一起学习！

我有一个无向图，没有多个/平行边，并且每个边都用距离加权。我希望在图表中找到某个最小和最大总距离之间的封闭行走。我还希望能够对步行中重复距离的数量设置限制，例如，如果将 10 的边遍历两次，则重复距离为 10。将重复距离设置为 0 应该会发现闭合图中的路径（与行走相对）。最后，虽然找到所有封闭步道会很好，但我不确定这对于存在数千/数百万条潜在路线的较大图表是否可行，因为我相信这将花费指数时间。因此，我目前正在尝试根据启发式函数找到一些最佳的封闭行走，以便算法在合理的时间内完成。

编辑：大致性能要求 - 我用来测试的图当前有 17,070 个节点和 23,026 个边。生成的循环包含大约 50 个边，查找时间约为 20 秒，但是我希望找到更长距离的循环（~100 个边），理想情况下也在 <1 分钟的时间范围内。

这是我当前的方法：

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
}

路线.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]
}

以下是我目前为加速算法所做的事情：

1. 不是查找所有循环，而是根据给定的启发式查找前几个循环。
2. 修剪图表，尽可能删除几乎所有 2 阶节点，并用权重 = 原始两条边之和的单条边替换它们。
3. 使用切片来存储重复的边，而不是使用地图。
4. 使用 dijkstra 算法找到从起始节点到每个其他节点的最短距离。如果一条路线无法在这段距离内返回，请立即丢弃它。 （算法实现的代码未包含在帖子中，因为它只占运行时间的约 4%）

根据 go 分析器，route.go 中的 withaddednode 方法占运行时的 68%，该方法的时间大致均匀地分布在 runtime.memmove 和 runtime.makeslice （调用 runtime.mallocgc）之间。本质上，我相信大部分时间都花在复制路由上。我将非常感谢任何有关如何改进该算法的运行时间或任何可能的替代方法的反馈。如果我可以提供任何其他信息，请告诉我。非常感谢！

正确答案

查找两个顶点之间的所有路径的标准算法是：

• 应用 dijkstra 寻找最便宜的路径
• 增加路径中链接的成本
• 重复直到找不到新路径

在您的情况下，您希望路径返回到起始顶点。可以轻松修改算法来做到这一点

• 将起始顶点 s 分成两部分：s1 和 s2。
• 在连接到 s 的顶点上循环 v。
  • 在 s1 和 v 之间添加零成本边
  • 在 s2 和 v 之间添加零成本边
• 删除 s 及其边缘。
• 运行标准算法来查找 s1 和 s2 之间的所有路径

您需要修改 dijkstra 代码以考虑其他限制 - 最大长度和“启发式”

性能

尽管您说您担心大型图表的性能，但您没有给出所需的性能。我会尝试提供一个估计。

我对 go 的性能一无所知，所以我假设它与我熟悉的 c++ 相同。

以下是 c++ 的一些性能测量：

运行 dijkstra 算法的运行时间，以在从 https://dyngraphlab.github.io/。使用 graphex 应用程序运行 3 次的最长结果。