"""GraphExamples.py

Various examples of small standard named graphs.

D. Eppstein, September 2005.
"""

def GeneralizedPetersenGraph(n,k):
    G = {}
    for i in range(n):
        G[i,True] = (i,False),((i-1)%n,True),((i+1)%n,True)
        G[i,False] = (i,True),((i-k)%n,False),((i+k)%n,False)
    return G

PetersenGraph = GeneralizedPetersenGraph(5,2)
DesarguesGraph = GeneralizedPetersenGraph(10,3)

def GeneralizedCoxeterGraph(n,a,b):
    G = {}
    for i in range(n):
        G[i,0] = (i,1),(i,2),(i,3)
        G[i,1] = (i,0),((i+1)%n,1),((i-1)%n,1)
        G[i,2] = (i,0),((i+a)%n,2),((i-a)%n,2)
        G[i,3] = (i,0),((i+b)%n,1),((i-b)%n,1)
    return G

CoxeterGraph = GeneralizedCoxeterGraph(7,2,3)

def CubeConnectedCycles(n):
    return {(x,y):[(x,(y+1)%n),(x,(y-1)%n),(x^(1<<y),y)]
            for x in range(1<<n) for y in range(n)}

def LCFNotation(L,n):
    """
    Construct the cubic Hamiltonian graph with LCF Notation L^n.
    See http://mathworld.wolfram.com/LCFNotation.html
    for a description of this notation.
    """
    n *= len(L)
    return {i:((i-1)%n,(i+1)%n,(i+L[i%len(L)])%n) for i in range(n)}

McGeeGraph = LCFNotation([-12,7,-7],8)
DyckGraph = LCFNotation([-13,5,-5,13],8)
PappusGraph = LCFNotation([5,7,-7,7,-7,-5],3)
TutteCoxeterGraph = LCFNotation([-13,-9,7,-7,9,13],5)
GrayGraph = LCFNotation([-25,7,-7,13,-13,25],9)