Random Graphs

randomDiGraph.py

import random

def randomDAG(minHeight, maxHeight, minFat, maxFat, p):
    '''
    create levels, and draw edges across levels
    from http://stackoverflow.com/questions/12790337/generating-a-random-dag
    '''
    height = random.randint(minHeight, maxHeight)

    nodes = 0
    outList = [[]]
    for rank in range(height):
        newNodes = random.randint(minFat, maxFat)

        for i in range(1, nodes + 1):
            for j in range(1, newNodes+1):
                if random.random() <= p:
                    outList[i].append(j+nodes)

        outList.extend([[] for iii in range(newNodes)])
        nodes += newNodes

    return outList

def randomSCC(nVertices):
    '''
    create a random SCC on n vertices
    Set u = 1
    keep exploring from u till you reach u back
    if all vertices have been visited, you have a cycle
    otherwise, from all the vertices that have been visited already, pick another and explore
    do this until you have touched all the vertices
    '''
    n = nVertices + 1
    outList = [set() for i in range(n)]
    visited = [False]*n

    def dfs(u, start):
        nonlocal visited, outList
        visited[u] = True
        v = u
        while v == u:
            v = random.randint(1, nVertices)
        if not v in outList[u]:
            outList[u].add(v)
        if v == start:
            return
        dfs(v, start)

    visited[1] = True
    while not all(visited[1:]):
        u = 0
        while not visited[u]:
            u = random.randint(1, nVertices)
        dfs(u, u)

    return [list(l) for l in outList]

def inflate(sccDAG, minFat, maxFat, p):
    '''given a DAG, populate the vertices of the dag with components'''
    dagSize = len(sccDAG)
    compWeight = [random.randint(minFat, maxFat) for i in range(dagSize)]
    graphSize = sum(compWeight[1:]) + 1
    graph = [[] for i in range(graphSize)]
    soFar = 0
    for i in range(1, dagSize):
        component = randomSCC(compWeight[i])
        for u in range(1, compWeight[i]+1):
            for v in component[u]:
                graph[u + soFar].append(v + soFar)
        soFar += compWeight[i]
    components = [(0,0)]
    r1, r2 = 0,0
    for i in range(1, dagSize):
        r1 = r2 + 1
        r2 = r1 + compWeight[i] - 1
        components.append((r1, r2))
    for u in range(1, dagSize):
        for v in sccDAG[u]:
            u1, u2 = components[u]
            v1, v2 = components[v]
            uX, vX = random.randint(u1, u2), random.randint(v1, v2)
            graph[uX].append(vX)
    for u in range(1, dagSize):
        for v in sccDAG[u]:
            u1, u2 = components[u]
            v1, v2 = components[v]
            for uX in range(u1, u2+1):
                for vX in range(v1, v2+1):
                    if random.random() <= p:
                        graph[uX].append(vX)
    return [list(set(neighbors)) for neighbors in graph]

def relabel(graph):
    '''randomize the labels of the vertices'''
    n = len(graph)
    labels = list(range(1, n))
    random.shuffle(labels)
    labels = [0] + labels
    newGraph = [[] for i in range(n)]
    for u in range(1, n):
        for v in graph[u]:
            newGraph[labels[u]].append(labels[v])
    return newGraph

def randomDiGraph():
    # create a random dag with random parameters
    minHeight = random.randint(1,50)
    maxHeight = random.randint(minHeight, 50)
    minFat = random.randint(1, 20)
    maxFat = random.randint(minFat, 20)
    p = random.random()
    # populate the dag with arbitrary parameters
    dag = randomDAG(minHeight, maxHeight, minFat, maxFat, p)
    minFat = random.randint(1, 20)
    maxFat = random.randint(minFat, 20)
    p = random.random()
    graph = inflate(dag, minFat, maxFat, p)
    # shuffle the labels
    graph = relabel(graph)
    return graph

def writeFile(fileHandle, graph):
    n = len(graph)
    fileHandle.write(str(n-1))
    for u in range(1, n):
        fileHandle.write("\n")
        fileHandle.write(str(len(graph[u])))
        fileHandle.write(' ' + (' '.join(map(str,graph[u]))))

def main():
    for i in range(500):
        graph = randomDiGraph()
        f = open("testcases/"+str(i)+".in", "w")
        writeFile(f, graph)
        print("File " + str(i) + " written.")
        f.close()

if __name__ == "__main__":
    main()