Generating immutable cyclic data structrures

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

I don't think this is possible with a strictly immutable class of the type you proposed. The only thing I can think of is to add a property with a setter that check whether or not a field is null, and allows it to be set if it is. In this way you could leave the first field in the first object null, and once you've created the last object in the cycle set that field appropriately to close the loop. Once it's set, it is no longer null, and the setter would no longer allow it to be changed. It would still be possible for the field to be changed by code internal to the class, of course, but it would be essentially immutable from the outside.

Something like this (C#):

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

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

    public object First {
        get { return first; }
        set 
        {
            if (first == null)
            {
                first = value;
            }
        }
    }

    // and a similar property for second
}

Answer 2

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.