CODEWITHSUNDEEP
mathgraph
mr.nothing
mr.nothing

Reputation: 5399

Algorithm to generate interval graph

I wonder if there is any algorithm or some easy procedure to generate an interval graph?
I need to generate interval graphs with n nodes, where n is changing for 1 to, say, 10000.
If it is possible, I need an incidence matrix representation of the graph.
An additional restriction is not to have all these graphs complete.

Thanks everyone in advance!

==ADDITION==

Here is an implementation in Java:

public Object generate(int numberOfNodes) {
    int listCapacity = numberOfNodes * 2;
    List<Integer> arr = new ArrayList<Integer>();
    int[][] adjacencyMatrix = new int[numberOfNodes][numberOfNodes];
    Integer nodeNumber = 0;
    for (int i = 0; i < listCapacity; i = i + 2) {
        arr.add(nodeNumber);
        arr.add(nodeNumber);
        nodeNumber++;
    }

    Collections.shuffle(arr);

    for (int i = 0; i < numberOfNodes; i++) {
        for (int j = arr.indexOf(i); j < arr.lastIndexOf(i); j++) {
            adjacencyMatrix[i][arr.get(j)] = 1;
            adjacencyMatrix[arr.get(j)][i] = 1;
        }
        adjacencyMatrix[i][i] = 0;
    }

    return new Graph(adjacencyMatrix);
}

Though, in some cases it fails to produce interval graph.

Upvotes: 2

Views: 1275

Answers (1)

John Dvorak
John Dvorak

Reputation: 27317

One possible way to generate an interval graph with N nodes:

  • create an array [1, 1, 2, 2, ... n, n]
  • shuffle the array
  • create a graph:
    • each node v_i corresponds to the pair of occurences of i in the shuffled array
    • two nodes v_i and v_j are connected with an edge iff i and j are interleaved in the array. That is i j i j or i j j i, but not i i j j. In other words, the intervals i and j intersect.

This graph is guaranteed to be an interval graph (every node is an interval in the original array), and every graph is possible to create this way.

Upvotes: 4

Related Questions