text: import random
  import numpy as np
  
  
  def create_alias_table(area_ratio):
      """
  
      :param area_ratio: sum(area_ratio)=1
      :return: accept,alias
      """
      l = len(area_ratio)
      accept, alias = [0] * l, [0] * l
      small, large = [], []
      area_ratio_ = np.array(area_ratio) * l
      for i, prob in enumerate(area_ratio_):
          if prob < 1.0:
              small.append(i)
          else:
              large.append(i)
  
      while small and large:
          small_idx, large_idx = small.pop(), large.pop()
          accept[small_idx] = area_ratio_[small_idx]
          alias[small_idx] = large_idx
          area_ratio_[large_idx] = area_ratio_[large_idx] - (1 - area_ratio_[small_idx])
          if area_ratio_[large_idx] < 1.0:
              small.append(large_idx)
          else:
              large.append(large_idx)
  
      while large:
          large_idx = large.pop()
          accept[large_idx] = 1
      while small:
          small_idx = small.pop()
          accept[small_idx] = 1
  
      return accept, alias
  
  
  def alias_sample(accept, alias):
      """
  
      :param accept:
      :param alias:
      :return: sample index
      """
      N = len(accept)
      i = int(random.random() * N)
      r = random.random()
      if r < accept[i]:
          return i
      else:
          return alias[i]
  
  
  class RandomWalker:
      def __init__(self, G, p=1, q=1):
          """
          :param G:
          :param p: Return parameter,controls the likelihood of immediately revisiting a node in the walk.
          :param q: In-out parameter,allows the search to differentiate between “inward” and “outward” nodes
          """
          self.G = G
          self.p = p
          self.q = q
  
      def get_alias_edge(self, t, v):
          """
          compute unnormalized transition probability between nodes v and its neighbors give the previous visited node t.
          :param t:
          :param v:
          :return:
          """
          G = self.G
          p = self.p
          q = self.q
  
          unnormalized_probs = []
          for x in G.neighbors(v):
              weight = G[v][x].get('weight', 1.0)  # w_vx
  
              if x == t:  # d_tx == 0
                  unnormalized_probs.append(weight / p)
              elif G.has_edge(x, t):  # d_tx == 1
                  unnormalized_probs.append(weight)
              else:  # d_tx > 1
                  unnormalized_probs.append(weight / q)
  
          norm_const = sum(unnormalized_probs)
          normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]
  
          return create_alias_table(normalized_probs)
  
      def preprocess_transition_probs(self):
          """
          Preprocessing of transition probabilities for guiding the random walks.
          """
          G = self.G
  
          alias_nodes = {}
          for node in G.nodes():
              unnormalized_probs = [G[node][nbr].get('weight', 1.0)
                                    for nbr in G.neighbors(node)]
              norm_const = sum(unnormalized_probs)
              normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]
              alias_nodes[node] = create_alias_table(normalized_probs)
  
          alias_edges = {}
  
          for edge in G.edges():
              alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])
  
          self.alias_nodes = alias_nodes
          self.alias_edges = alias_edges
  