class_docstr: Model specification given adjacency matrix and labeling.
class_docstr_tok: ["Model","specification","given","adjacency","matrix","and","labeling","."]
docstr: Prune the extraneous parts of the graph.
  
  General procedure:
    1) Remove parts of graph not connected to input.
    2) Remove parts of graph not connected to output.
    3) Reorder the vertices so that they are consecutive after steps 1 and 2.
  
  These 3 steps can be combined by deleting the rows and columns of the
  vertices that are not reachable from both the input and output (in reverse).
docstr_tok: ["Prune","the","extraneous","parts","of","the","graph",".","General","procedure",":","1",")","Remove","parts","of","graph","not","connected","to","input",".","2",")","Remove","parts","of","graph","not","connected","to","output",".","3",")","Reorder","the","vertices","so","that","they","are","consecutive","after","steps","1","and","2",".","These","3","steps","can","be","combined","by","deleting","the","rows","and","columns","of","the","vertices","that","are","not","reachable","from","both","the","input","and","output","(","in","reverse",")","."]
code: def _prune(self):
      """Prune the extraneous parts of the graph.
  
      General procedure:
        1) Remove parts of graph not connected to input.
        2) Remove parts of graph not connected to output.
        3) Reorder the vertices so that they are consecutive after steps 1 and 2.
  
      These 3 steps can be combined by deleting the rows and columns of the
      vertices that are not reachable from both the input and output (in reverse).
      """
      num_vertices = np.shape(self.original_matrix)[0]
  
      # DFS forward from input
      visited_from_input = set([0])
      frontier = [0]
      while frontier:
          top = frontier.pop()
          for v in range(top + 1, num_vertices):
              if (
                  self.original_matrix[top, v]
                  and v not in visited_from_input
              ):
                  visited_from_input.add(v)
                  frontier.append(v)
  
      # DFS backward from output
      visited_from_output = set([num_vertices - 1])
      frontier = [num_vertices - 1]
      while frontier:
          top = frontier.pop()
          for v in range(0, top):
              if (
                  self.original_matrix[v, top]
                  and v not in visited_from_output
              ):
                  visited_from_output.add(v)
                  frontier.append(v)
  
      # Any vertex that isn't connected to both input and output is extraneous to
      # the computation graph.
      extraneous = set(range(num_vertices)).difference(
          visited_from_input.intersection(visited_from_output)
      )
  
      # If the non-extraneous graph is less than 2 vertices, the input is not
      # connected to the output and the spec is invalid.
      if len(extraneous) > num_vertices - 2:
          self.matrix = None
          self.ops = None
          self.valid_spec = False
          return
  
      self.matrix = np.delete(self.matrix, list(extraneous), axis=0)
      self.matrix = np.delete(self.matrix, list(extraneous), axis=1)
      for index in sorted(extraneous, reverse=True):
          del self.ops[index]
  
file_path: singa/examples/model_selection/TRAILS-Database-Native-Model-Selection/internal/ml/model_selection/src/third_pkg/sp101_lib/model_spec.py
imports: import copy
  import hashlib
  import itertools
  import numpy
label_desc: Use image node_id 2 for calling the NASBench101ModelSpec obj's underlying member method code with example usage: obj._prune() without return types