# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013
from copy import *     # import copy and deepcopy functions

# relink digraph into a graph
def relink(g) :
    for i in range(0, len(g)) :
        for j in g[i] :
            if i!=j : g[j].add(i)   # prevent the add from changing g[i]
    return g                  # note that g was changed and really doesn't have to be returned


# simple utility 1D array function
def array(size, value) : 
    a = []
    for i in range(0, size) : 
        a.append(deepcopy(value))
    return a


# as list/sets in a digraph
digraph = [{1, 2, 3}, # 0
          set(),       # 1
          {4, 5},      # 2
          {5},         # 3
          set(),       # 4
          {8},         # 5
          {7},         # 6
          set(),       # 7
          set()        # 8
          ]
          

# create a separate graph version of the digraph using copy and relink
graph = deepcopy(digraph)
relink(graph)


# as list/sets in a digraph
notTree = [{1, 2, 3}, # 0
          set(),       # 1
          {4, 5},      # 2
          {5},         # 3
          set(),       # 4
          {6},         # 5
          set()        # 6
          ]
          
# create a separate graph version of the digraph using copy and relink
notTreeGraph = deepcopy(notTree)
relink(notTreeGraph)

tree   = [{1, 2, 3},   # 0
          set(),       # 1
          {4, 5},      # 2
          set(),       # 3
          set(),       # 4
          {6},         # 5
          set()        # 6
          ]
          
# relink(tree)