text: ### This file: line-by-line translation from Algorithm 2
  ### in the paper "Representing higher-order dependencies in networks"
  ### Code written by Jian Xu, Jan 2017
  
  ### Technical questions? Please contact i[at]jianxu[dot]net
  ### Demo of HON: please visit http://www.HigherOrderNetwork.com
  ### Latest code: please visit https://github.com/xyjprc/hon
  
  ### Call BuildNetwork()
  ### Input: Higher-order dependency rules
  ### Output: HON network
  ### See details in README
  
  
  from collections import defaultdict, Counter
  
  Graph = defaultdict(dict)
  Verbose = True
  
  def Initialize():
      Graph = defaultdict(dict)
  
  
  def BuildNetwork(Rules):
      VPrint('Building network')
      Initialize()
      SortedSource = sorted(Rules, key=lambda x: len(x))
      for source in SortedSource:
          for target in Rules[source]:
              Graph[source][(target,)] = Rules[source][target]
              # following operations are destructive to Rules
              if len(source) > 1:
                  Rewire(source, (target,))
      RewireTails()
      return Graph
  
  def Rewire(source, target):
      PrevSource = source[:-1]
      PrevTarget = (source[-1],)
      if not PrevSource in Graph or not source in Graph[PrevSource]:
          Graph[PrevSource][source] = Graph[source][target]
          del(Graph[PrevSource][PrevTarget])
  
  def RewireTails():
      ToAdd = []
      ToRemove = []
      for source in Graph:
          for target in Graph[source]:
              if len(target) == 1:
                  NewTarget = source + target
                  while len(NewTarget) > 1:
                      if NewTarget in Graph:
                          ToAdd.append((source, NewTarget, Graph[source][target]))
                          ToRemove.append((source, target))
                          break
                      else:
                          NewTarget = NewTarget[1:]
      for (source, target, weight) in ToAdd:
          Graph[source][target] = weight
      for (source, target) in ToRemove:
          del(Graph[source][target])
  
  
  ###########################################
  # Auxiliary functions
  ###########################################
  
  def VPrint(string):
      if Verbose:
          print(string)