data-structures - 生成不可变的循环数据结构

Question

假设我有这个简单的类:

public class Pair {
    public readonly object first;
    public readonly object second;

    public Pair(object first, object second) {
        this.first = first;
        this.second = second;
    }
}

生成对的循环图是不可能的。

你将如何创建一个类似的类，它仍然是不可变的，但可以以某种方式用于生成循环图？

Answer 1

有无数种方法来表示图结构。一种这样的方法是使用矩阵。每行和每列都由顶点索引，矩阵中的每个单元格代表一个有向(可能是加权的)边。一个简单的循环图，0 表示没有连接边，1 表示连接边，就像这样:

| 0 1 |
| 1 0 |

与许多不可变结构一样，构造它们的方式是根据给定矩阵的所需关系返回新结构。例如，如果我们想采用上面的图形并将第一个顶点上的一条边添加回自身，则表示它的矩阵就是这样。

| 1 0 |
| 0 0 |

并将其与另一个矩阵相结合，我们只需将它们加在一起。

| 0 1 |  +  | 1 0 |  ==  | 1 1 |
| 1 0 |     | 0 0 |      | 1 0 |

当然，有很多方法可以表示矩阵，在速度、空间和某些其他操作方面有不同的权衡，但这是一个不同的问题。