标签: cycle

我是一些家庭树软件的开发者(用C ​​++和Qt编写).在我的一位客户向我邮寄错误报告之前,我没有遇到任何问题.问题是客户有两个孩子和自己的女儿,因此,他因错误而无法使用我的软件.

这些错误是我处理家族图的各种断言和不变量的结果(例如,在走一个循环之后,程序声明X不能同时是Y的父亲和祖父).

如何在不删除所有数据断言的情况下解决这些错误？

我知道Tortoise和Hare的会议总结了循环的存在,但是如何将兔子移动到链接列表的开头同时将野兔保持在会场,然后一步一步地移动两个步骤使它们在循环的起始点相遇？

我需要一个工作算法来查找无向图中的所有简单循环.我知道成本可能是指数级的并且问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少.

经过长时间的研究(主要是在这里),我仍然没有工作方法.以下是我的搜索摘要:

查找无向图中的所有循环

无向图中的循环 - >仅检测是否存在循环

在无向图中查找多边形 - >非常好的描述,但没有解决方案

在有向图中查找所有循环 - >仅在有向图中查找循环

使用增强图库检测无向图中的循环

我发现的唯一一个解决我问题的答案是:

查找图表中的所有周期,redux

似乎找到一组基本的循环并对它们进行异或可以解决问题.找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...

在Perl中,有能力打破这样的外部循环:

AAA: for my $stuff (@otherstuff) {
         for my $foo (@bar) {
             last AAA if (somethingbad());
         }
      }

(语法可能有误),它使用循环标签从内部循环内部中断外部循环.Ruby中有类似的东西吗？

我已经看过一个问题,讨论在链表中查找循环的算法.我已经阅读了Floyd的循环寻找算法解决方案,在许多地方提到我们必须采取两个指针.一个指针(慢/龟)增加一个,其他指针(更快/野兔)增加2.当它们相等时我们找到循环,如果更快的指针到达null,则链表中没有循环.

现在我的问题是为什么我们将指针增加更快2.为什么不是别的呢？增加2是必要的,或者我们可以将它增加X来得到结果.如果我们将指针增加2,或者可能存在需要增加3或5或x的情况,我们是否有必要找到一个循环.

我听说有英特尔在线书籍描述了特定汇编指令所需的CPU周期,但我无法找到它(经过努力).有人能告诉我如何找到CPU周期吗？

下面是一个例子,在下面的代码中,mov/lock是1个CPU周期,xchg是3个CPU周期.

// This part is Platform dependent!
#ifdef WIN32
inline int CPP_SpinLock::TestAndSet(int* pTargetAddress, 
                                              int nValue)
{
    __asm
    {
        mov edx, dword ptr [pTargetAddress]
        mov eax, nValue
        lock xchg eax, dword ptr [edx]
    }
    // mov = 1 CPU cycle
    // lock = 1 CPU cycle
    // xchg = 3 CPU cycles
}

#endif // WIN32

顺便说一句:这是我发布的代码的URL:http://www.codeproject.com/KB/threads/spinlocks.aspx

有没有人知道一个算法来查找链表是否只使用两个变量来遍历列表.假设您有一个链接的对象列表,它与哪种类型的对象无关.我在一个变量中有一个指向链表头部的指针,我只有一个其他变量来遍历列表.

所以我的计划是比较指针值以查看是否有任何指针相同.该列表的大小有限,但可能很大.我可以将两个变量都设置为头部,然后用另一个变量遍历列表,总是检查它是否等于另一个变量,但是,如果我确实打了一个循环,我将永远不会离开它.我认为它与遍历列表和比较指针值的不同速率有关.有什么想法吗？

我有两个实体:

Parent {
   Child[] children;
}

and 

Child {
   Parent parent;
}

我知道@JsonBackReference和@JsonManagedReference.如果我正在序列化实例,那么它们很好Parent.

但我还需要传输实例,Child并希望parent填充该字段.

换一种说法:

1. 在Parent它的序列化应该有,children但他们的父字段可能是空的(可以通过使用json引用注释来解决).
2. 在Child它的序列化应该parent与他们children(但children不必parent填充.

有没有办法使用标准的Jackson功能来解决它​​？

即跳过已经序列化的实体的序列化,而不是标记符合条件或不符合序列化条件的字段.

好吧,我使用itertools.cycle().next()Python 2.6.6的方法,但现在我更新到3.2我注意到itertools.cycle()对象没有方法next().

我用它在类的spin()方法中循环一个字符串Spinner.因此,如果我们循环元组('|', '/', '-', '\\', '|', '/', '-'),它会打印:|,/,-,\,|,/,-,|,/等...

我搜索了Python 3.0,3.1和3.2的发行说明,并没有发现任何变化.什么时候改变了？是否有任何简单的替代方案可以实现与以前相同的功能？

先感谢您.

请注意,图表表示为邻接列表.

我听说有两种方法可以在图表中找到一个循环:

1. 保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.

2. 来自Cormen的CLRS或Skiena的那个:对于无向图中的深度优先搜索,有两种类型的边,树和背.当且仅当存在后沿时,该图具有循环.

有人可以解释一下图的后边缘是什么,以及上述两种方法之间的差异是什么.

谢谢.

更新: 这是在两种情况下检测周期的代码.Graph是一个简单的类,为了简单起见,将所有图形节点表示为唯一编号,每个节点都有其相邻的相邻节点(g.getAdjacentNodes(int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

用于检测无向图中的循环的Java代码:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = …