# importing os ( = "Operating System") module
# allows to run any executable or operating system command or batch file
# from inside a python program
import os

import random


# To specify a graph completely, one list E is enough.
# List E supposes that the nodes are labeled by integers 0,1,2...
# An entry in E at position k is the list of all neighbours of node labeled k.
# Length of E is equal to the number of nodes in the graph

# No programming language is optimally suited for graph manipulation
# We often have to survive with code which may feel (partially) clumsy
# and less elegant than it may be desired.

# ----------------------------------------------------------------------------
#            G R A P H
# ----------------------------------------------------------------------------

# ----------------------------------------------------------------------------
#          Basic representation

edges = []

def newGraph( Nnodes ):
    global edges
    edges =  [ [] for _ in range(Nnodes) ]

def addEdge( node1, node2 ):
    global edges
    edges[node1].append(node2)
    edges[node2].append(node1)

def isEdge( node1, node2 ):
    # extremely slow implementation, but simple, at least
    if len(edges[node1]) < len(edges[node2]):
        return node2 in edges[node1]
    else:
        return node1 in edges[node2]
    # The complexity of function isEdge is equal
    # to the smaller of the degrees of node1 and node2.
    # Note that in extreme cases this complexity is proportional to
    # the number of all nodes in the graph (when the node degrees are high).
    # When it is called many times it can slow down the execution speed
    # in orders of magnitude, especially when the processed graph is big.
    # Therefore: A - use it with caution or B - or develop or use more effective
    # approach according to the problem specifics.

def degree( node ):
    return len(edges[node])
# ----------------------------------------------------------------------------
#     Service functions -- more interface comfort

# print graph in text mode for better debug etc.
def printg( ):
    N = len(edges) # no. of nodes
    for i in range( N ):
        print( i, edges[i] )
    print( "--------------")


def makePicture( edges, graphName ):
    dotfName = graphName+".dot"
    graphPicfName = graphName+".jpg"

    # Graphviz expects graph description
    # in plain text file with .dot extension
    dotFile = open( dotfName, "w" )

    dotFile.write( "graph {\n" )
    dotFile.write( "node [shape=oval fixedsize=true width=0.40 height=0.30" )
    dotFile.write( " fontname=\"Courier-Bold\" ]" )

    for i in range( len(edges) ):
        for neighi in edges[i]:
            if i < neighi:
                dotFile.write(str(i)+" -- "+str(neighi) + "\n" )
    dotFile.write( "}\n" )
    dotFile.close()

    GraphvizExe = "d:\G\graphviz\\bin\dot"
    # Graphviz Engines:  dot neato twopi circo fdp osage sfdp # prefer dot or fdp
    GraphvizEngine = "neato"
    GraphvizParams = " -Tjpg -K" +GraphvizEngine+ " " + dotfName + " -o " + graphPicfName
    GraphvizCommand = GraphvizExe + GraphvizParams
    os.system( GraphvizCommand )

    os.system("d:\\Util\\IrfanView\\i_view32.exe " + graphPicfName)


# ----------------------------------------------------------------------------
#     Construction area  -- create various kinds of graphs

# define graph manually by its list of edges
def manualGraph( spec ):
    # spec in a string of integers separated by space(s)
    # the first integer is the number of nodes
    # remaining integers are pairs of nodes specifying edges
    # Ex. "4  0 2  1 2  3 2" is a 4-nodes star with center in 2
    global edges
    vals = spec.split()
    newGraph( int(vals[0]))
    for i in range(1, len(vals), 2):
        addEdge( int(vals[i]), int(vals[i+1]) )

def randomGraph( Nnodes, Nedges ):
    global edges
    # create all possible edges
    ee = []
    for i in range(Nnodes-1):
        for j in range(i+1, Nnodes):
            ee.append( [i,j] )
    # select randomly only Nedges of all edges
    random.shuffle( ee )
    ee = ee[:Nedges]
    # add those edges to the graph
    newGraph( Nnodes )
    for e in ee:
        addEdge(e[0], e[1] )

def completeGraph( Nnodes ):
    global edges
    newGraph( Nnodes )
    for node1 in range(Nnodes-1):
        for node2 in range(node1+1, Nnodes ):
            addEdge( node1, node2 )

def cycle( Nnodes ):
    global edges
    newGraph( Nnodes )
    for node in range(Nnodes):
        addEdge( node, (node+1) % Nnodes )

def path( Nnodes ):
    global edges
    newGraph( Nnodes )
    for node in range(Nnodes-1):
        addEdge( node, node+1 )

def star( Nnodes ):
    global edges
    newGraph( Nnodes )
    for node in range(1, Nnodes):
        addEdge( 0, node )

def wheel( Nnodes ):
    # wheel is a cycle with star inside creating the spikes
    global edges
    newGraph( Nnodes )
    for node in range(Nnodes-1):
        addEdge( 1+ node, 1+ ((node+1) % (Nnodes-1)) )
    for node in range(1, Nnodes):
        addEdge( 0, node )


def longStar( Nspikes, length ):
    global edges
    Nnodes = Nspikes*(length) + 1
    newGraph( Nnodes )
    # the center is at level 0
    for spike in range(1, Nspikes+1):
        addEdge(0, spike)
    for node in range( Nspikes +1, Nnodes ):
        addEdge( node, node - Nspikes)

def grid( height, width ):
    global edges
    Nnodes = height*width
    newGraph( Nnodes )
    for row in range(height):
        for col in range(width-1):
            addEdge(row*width + col , row*width + col+1)
    for col in range(width):
        for row in range(height-1):
            addEdge(row*width + col , row*width + col+ width)

# ----------------------------------------------------------------------------
#     Exploration area  -- Examine various graph properties

def maxDegree():
    return max( [degree(i) for i in range(len(edges)) ] )


def nodesWithDegree( deg ):
    return [node for node in range(len(edges)) if degree(node) == deg ]

def minDegree():
    return min( [degree(i) for i in range(len(edges)) ] )

def nodesByDegrees():
    N = len(edges)
    byDg = [[] for _  in range( N ) ]
    for i in range( N ):
        byDg[ len(edges[i]) ].append( i )
    print("degrees _ [corresponding nodes]")
    for i in range(N-1):
        print(i,"_", byDg[i] )

def isTriangle( node1, node2, node3 ):
    return isEdge(node1, node2) and isEdge(node1, node3) and isEdge(node2, node3)

def detectTriangles():
    N = len(edges)
    ntri = 0
    for node1 in range( 0, N-2):
        for node2 in range( node1+1, N-1):
            for node3 in range( node2+1, N):
                if isTriangle( node1, node2, node3 ):
                    ntri += 1
                    print( "triangle", ntri, "--", node1, node2, node3 )

def adjacentTriangles():
    # for each edge detect all triangles adjacent to that edge
    # then just list all pairs of those triangles
    Nnodes = len(edges)
    for node1 in range(Nnodes):
        for node2 in edges[node1]:
            if node2 < node1: continue
            triangles = []
            for node3 in range(Nnodes):
                if node3 == node1 or node3 == node2: continue
                if isEdge(node1, node3) and isEdge(node2, node3):
                    triangles.append([node1, node2, node3])
            for itri in range(len(triangles)-1):
                for jtri in range( itri+1, len(triangles)):
                    print( triangles[itri], triangles[jtri] )





# ----------------------------------------------------------------------------
#       M A I N   -- T E S T    G R A P H   P R O C E D U R E S
# ----------------------------------------------------------------------------

random.seed(2332332)
#randomGraph( 10, 18 )
#randomGraph( 20, 36 )
completeGraph( 4 )
printg()
maxdeg = maxDegree()
print( "max degree ", maxdeg )
selectedNodes = nodesWithDegree( maxdeg )
print("nodes: ", selectedNodes )
nodesByDegrees()
detectTriangles()
adjacentTriangles()

makePicture( edges, "anypic3")


'''
printg()

manualGraph( "4  0 2  1 2  2 3")
printg()
makePicture( edges, "anypic3")

cycle( 8 )
printg()
makePicture( edges, "anypic3")

grid( 3, 5 )
printg()
makePicture( edges, "anypic3")


longStar( 7, 3 )
printg()
makePicture( edges, "anypic3")

wheel( 6 )
printg()
makePicture( edges, "anypic3")

'''