text: import itertools
  import random
  from joblib import Parallel, delayed
  from alias.alias import alias_sample, create_alias_table
  from .utils import partition_num
  
  
  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 deepwalk_walk(self, walk_length, start_node):
  
          walk = [start_node]
  
          while len(walk) < walk_length:
              cur = walk[-1]
              cur_nbrs = list(self.G.neighbors(cur))
              if len(cur_nbrs) > 0:
                  walk.append(random.choice(cur_nbrs))
              else:
                  break
          return walk
  
      def node2vec_walk(self, walk_length, start_node):
  
          G = self.G
          alias_nodes = self.alias_nodes
          alias_edges = self.alias_edges
  
          walk = [start_node]
  
  
          while len(walk) < walk_length:
              cur = walk[-1]
  
              cur_nbrs = list(G.neighbors(cur))
  
              if len(cur_nbrs) > 0:
                  if len(walk) == 1:
                      walk.append(
                          cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])]
                      )
  
                  else:
  
                      prev = walk[-2]
  
                      edge = (prev, cur)
  
                      next_node = cur_nbrs[
                          alias_sample(alias_edges[edge][0], alias_edges[edge][1])
                      ]
  
                      walk.append(next_node)
  
              else:
                  break
  
          return walk
  
      def simulate_walks(self, num_walks, walk_length, workers=1, verbose=0):
  
          G = self.G
  
          nodes = list(G.nodes())
  
          results = Parallel(n_jobs=workers, verbose=verbose)(
              delayed(self._simulate_walks)(nodes, num, walk_length)
              for num in partition_num(num_walks, workers)
          )
          walks = list(itertools.chain(*results))
  
          return walks
  
      def _simulate_walks(self, nodes, num_walks, walk_length):
          walks = []
          for _ in range(num_walks):
              random.shuffle(nodes)
              for v in nodes:
                  if self.p == 1 and self.q == 1:
                      walks.append(
                          self.deepwalk_walk(walk_length=walk_length, start_node=v)
                      )
                  else:
                      walks.append(
                          self.node2vec_walk(walk_length=walk_length, start_node=v)
                      )
          return walks
  
      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])
  
              reverse_edge = edge[::-1]
              alias_edges[reverse_edge] = self.get_alias_edge(reverse_edge[0], reverse_edge[1])
  
          self.alias_nodes = alias_nodes
          self.alias_edges = alias_edges
  
          return
  
  
  def chooseNeighbor(v, graphs, layers_alias, layers_accept, layer):
  
      v_list = graphs[layer][v]
  
      idx = alias_sample(layers_accept[layer][v], layers_alias[layer][v])
      v = v_list[idx]
  
      return v
  