#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013
from lib import *

# 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
          ]
          

# relink digraph into a graph: for every x to y edge there is a y to x edge
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


# reverse link the digraph:  every x to y edge is converted to a y to x edge
def reverselink(g) :
    ans = array(len(g), set())
    for i in range(0, len(g)) :
        for j in g[i] :
            ans[j].add(i)
    return ans


# test relinking
print(digraph)
print(reverselink(digraph))
relink(digraph)
print("Linked into a graph")
print(digraph)