Generating immutable cyclic data structures

Question

Suppose I have this simple class:

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

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

It would be impossible to generate a cyclic graph of pairs.

How would you create a similar class, that is still immutable, but can be used somehow to generate cyclic graphs?

Answer 1

There are zillions of ways to represent graph structures. One such way is with a matrix. each row and column is indexed by the vertex, and each cell in the matrix represents a directed (possibly weighted) edge. A simple, cyclic graph, with 0's as no connecting edge and 1 with a connecting edge would just be like so:

| 0 1 |
| 1 0 |

As with many immutable structures, the way you construct them is by returning new structures based on the desired relationship of given matrices. for instance, if we wanted to take the above graph and add an edge on the first vertex back onto itself, the matrix representing that is just.

| 1 0 |
| 0 0 |

and to combine that with the other matrix, we just add them together.

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

Of course, there are many ways to represent matrices, with different tradeoffs for speed, space, and certain other operations, but that's a different question.