text: """
      Author: Lasse Regin Nielsen
  """
  
  from __future__ import print_function
  import os, csv
  import numpy as np
  filepath = os.path.dirname(os.path.abspath(__file__))
  
  def read_data(filename, has_header=True):
      """
          Read data from file.
          Will also return header if header=True
      """
      data, header = [], None
      with open(filename, 'rt') as csvfile:
          spamreader = csv.reader(csvfile, delimiter=' ')
          if has_header:
              header = spamreader.next()
          for row in spamreader:
              data.append(row)
      return (np.array(data), np.array(header))
  
  def load_graphs(filename):
      """
          Loads graphs from file
      """
      data, _ = read_data(filename, has_header=False)
      graphs = []
      for line in data:
          if line[0] == 't':
              G = Graph(id=int(line[2]))
              graphs.append(G)
          else:
              if line[0] == 'v':
                  v = Vertex(id=int(line[1]), label=line[2])
                  graphs[len(graphs)-1].add_vertex(vertex=v)
              elif line[0] == 'e':
                  e = Edge(label=line[3],
                           from_vertex=graphs[len(graphs)-1].get_vertex(id=int(line[1])),
                           to_vertex=graphs[len(graphs)-1].get_vertex(id=int(line[2])))
                  graphs[len(graphs)-1].add_edge(edge=e)
      return graphs
  
  #################################################
  #                    Classes                    #
  #################################################
  class Queue(object):
      """
          Implementation of a simple queue data structure
      """
      def __init__(self, queue=None):
          if queue is None:
              self.queue = []
          else:
              self.queue = list(queue)
      def dequeue(self):
          return self.queue.pop(0)
      def enqueue(self, element):
          self.queue.append(element)
      def is_empty(self):
          return len(self.queue) == 0
      def empty(self):
          self.queue = []
  
  class Vertex():
      """
          Implementation of an Vertex in a graph
      """
      visited = False
      dfs_id = 0
      def __init__(self, id, label):
          self.id = id
          self.label = label
  
  class Edge():
      """
          Implementation of an Edge in a graph
      """
      def __init__(self, label, from_vertex, to_vertex):
          self.label = label
          self.from_vertex = from_vertex
          self.to_vertex = to_vertex
  
      def connected_to(self, vertex):
          return vertex.id == self.from_vertex.id or \
                 vertex.id == self.to_vertex.id
  
  class Graph():
      """
          Implementation of a Graph
      """
      edges, vertices = [], []
      def __init__(self, id):
          self.id = id
          self.edges = []
          self.vertices = []
      def add_vertex(self, vertex):
          self.vertices.append(vertex)
      def add_edge(self, edge):
          self.edges.append(edge)
      def get_vertex(self, id):
          for v in self.vertices:
              if v.id == id:
                  return v
          raise KeyError('No vertex with the id was found in graph')
      def adjacent_edges(self, vertex):
          adj_edges = []
          for e in self.edges:
              if e.connected_to(vertex):
                  adj_edges.append(e)
          return adj_edges
      def adjacent_vertices(self, vertex):
          adj_edges = self.adjacent_edges(vertex)
          adj_vertices = []
          for e in adj_edges:
              if e.from_vertex.id == vertex.id:
                  adj_vertices.append(e.to_vertex)
              else:
                  adj_vertices.append(e.from_vertex)
          return adj_vertices
      def adjacent_connections(self, vertex):
          adj_edges = self.adjacent_edges(vertex)
          adj_connections = []
          for e in adj_edges:
              if e.from_vertex.id == vertex.id:
                  adj_connections.append((e, e.to_vertex))
              else:
                  adj_connections.append((e, e.from_vertex))
          # Sort according to node index
          ids = [w.id for e,w in adj_connections]
          idx = np.argsort(ids)
          adj_connections = [adj_connections[i] for i in idx]
          return adj_connections
      def generate_vertices(self):
          for e in self.edges:
              for v in [e.from_vertex, e.to_vertex]:
                  v.id = v.dfs_id
                  if not v in self.vertices:
                      self.add_vertex(vertex=v)
      def get_max_vertex(self):
          ids = [v.id for v in self.vertices]
          idx = np.argsort(ids)[::-1]
          return self.vertices[idx[0]]
      def get_max_dfs_id_vertex(self):
          vertices_id = []
          for i, v in enumerate(self.vertices):
              if not v.dfs_id is None:
                  vertices_id.append(i)
          if len(vertices_id) > 0:
              ids = [self.vertices[i].id for i in vertices_id]
              idx = np.argsort(ids)[::-1]
              return self.vertices[idx[0]]
          else:
              return []
      def get_min_vertex(self):
          ids = [v.id for v in self.vertices]
          idx = np.argsort(ids)
          return self.vertices[idx[0]]
      def contains_vertex_id(self, id):
          for v in self.vertices:
              if v.id == id:
                  return True
          return False
      def contains_edge(self, from_id, to_id):
          for e in self.edges:
              if (e.from_vertex.id == from_id and e.to_vertex.id == to_id) or \
                 (e.to_vertex.id == from_id and e.from_vertex.id == to_id):
                 return True
          return False
      def reverse_graph(self):
          for e in self.edges:
              tmp_from = e.from_vertex
              e.from_vertex = e.to_vertex
              e.to_vertex = tmp_from
          self.edges = self.edges[::-1]
          self.vertices = self.vertices[::-1]
      def print_graph(self):
          DFScode = G2DFS(self)
          for line in DFScode:
              print(line)
      def get_edge(self, from_id, to_id):
          for e in self.edges:
              if (e.from_vertex.id == from_id and e.to_vertex.id == to_id) or \
                 (e.to_vertex.id == from_id and e.from_vertex.id == to_id):
                 return e
          return None
      def reset(self):
          for v in self.vertices:
              v.visited = False
              v.dfs_id = None
  
  #################################################
  #                   Functions                   #
  #################################################
  def DFS(G, v):
      """
          Depth-first search recursive algorithm:
          Input:
              G   Graph object containing vertices and edges
              v   Root vertex of the graph G (Vertex object)
          Output:
              p   Graph making a DFS spanning tree
      """
      G.reset() # Reset search parameters
      edges = []
      recursive_call_DFS(G, v, edges)
      p = Graph(-1)
      for e in edges:
          p.add_edge(e)
      p.generate_vertices()
      return p
  
  def recursive_call_DFS(G, v, edges):
      """
          Helper function for recursive DFS
      """
      v.visited = True
      v.dfs_id = len(edges)
      neighbors = G.adjacent_connections(vertex=v)
      for e, w in G.adjacent_connections(vertex=v):
          if not w.visited:
              edges.append(e)
              recursive_call_DFS(G, w, edges)
  
  def rightmost_path_BFS(G, v, v_target):
      """
          Get rightmost path using Breadth-First search algorithm on DFS path:
          Input:
              G           Graph object containing vertices and edges
              v           Root vertex of the graph G (Vertex object)
              v_target    Target vertex
          Output:
              p           Graph of shortest path from v to v_target
      """
      G.reset() # Reset search parameters
      for _v in G.vertices:
          _v.dfs_id = float('inf')
          _v.parent = None
      Q = Queue()
      v.dfs_id = 0
      Q.enqueue(v)
      while not Q.is_empty():
          current = Q.dequeue()
          for e, w in G.adjacent_connections(vertex=current):
              if w.dfs_id == float('inf'):
                  w.dfs_id = current.dfs_id + 1
                  w.parent = current
                  Q.enqueue(w)
                  if(w == v_target):
                      Q.empty()
                      break
      tmp = v_target
      p = Graph(id=-1)
      while tmp.parent is not None:
          e = Edge(label='_', from_vertex=tmp, to_vertex=tmp.parent)
          p.add_edge(edge=e)
          p.add_vertex(vertex=tmp)
          tmp = tmp.parent
      p.add_vertex(vertex=tmp)
      return p
  
  def get_rightmost_path(G):
      """
          Returns the rightmost-path of the graph G
      """
      v_root = G.get_min_vertex()
      v_target = G.get_max_vertex()
      T_G = DFS(G=G, v=v_root)
      v_target = G.get_max_dfs_id_vertex()
      R = rightmost_path_BFS(T_G, v_root, v_target)
      for v in R.vertices:
          v.id = v.dfs_id
      R.reverse_graph()
      return R
  
  def G2DFS(G):
      """
          Converts a graph object into a DFScode tuple sequence
      """
      DFScode = []
      for e in G.edges:
          DFScode.append((e.from_vertex.id, e.to_vertex.id,
              e.from_vertex.label, e.to_vertex.label, e.label))
      return DFScode
  
  def DFS2G(C):
      """
          Converts a DFScode tuple sequence C into a graph G
      """
      G = Graph(id=-1)
      vertices = []
      for u,v,L_u,L_v,L_uv in C:
          for vertex, label in [(u, L_u), (v, L_v)]:
              if not (vertex, label) in vertices:
                  vertices.append((vertex, label))
      for v_id, v_label in vertices:
          # Create and add vertex
          v = Vertex(id=v_id, label=v_label)
          G.add_vertex(vertex=v)
      # Add edges
      for t in C:
          # Expand tuple
          u, v, L_u, L_v, L_uv = t
          # Get vertices
          _u, _v = G.get_vertex(id=u), G.get_vertex(id=v)
          # Add edge
          e = Edge(label=L_uv, from_vertex=_u, to_vertex=_v)
          G.add_edge(edge=e)
      return G
  
  def tuple_is_smaller(t1,t2):
      """
          Checks whether the tuple t1 is smaller than t2
      """
      t1_forward = t1[1] > t1[0]
      t2_forward = t2[1] > t2[0]
      i,j,x,y = t1[0], t1[1], t2[0], t2[1]
      # Edge comparison
      if t1_forward and t2_forward:
          if j < y or (j == y and i > x):
              return True
          elif j > y or (j == y and i < x):
              return False
      elif (not t1_forward) and (not t2_forward):
          if i < x or (i == x and j < y):
              return True
          elif i > x or (i == x and j > y):
              return False
      elif t1_forward and (not t2_forward):
          if j <= x:
              return True
          else:
              return False
      elif (not t1_forward) and t2_forward:
          if i < y:
              return True
          elif i > y: # Maybe something missing here
              return False
      # Lexicographic order comparison
      a1,b1,c1 = t1[2], t1[3], t1[4]
      a2,b2,c2 = t2[2], t2[3], t2[4]
  
      if not a1.isdigit():
          a1,b1,c1 = ord(a1),ord(b1),ord(c1)
          a2,b2,c2 = ord(a2),ord(b2),ord(c2)
      else:
          a1,b1,c1 = int(a1),int(b1),int(c1)
          a2,b2,c2 = int(a2),int(b2),int(c2)
  
      if a1 < a2:
          return True
      elif a1 == a2:
          if b1 < b2:
              return True
          elif b1 == b2:
              if c1 < c2:
                  return True
  
      #if ord(t1[2]) < ord(t2[2]):
      #    return True
      #elif ord(t1[2]) == ord(t2[2]):
      #    if ord(t1[3]) < ord(t2[3]):
      #        return True
      #    elif ord(t1[3]) == ord(t2[3]):
      #        if ord(t1[4]) < ord(t2[4]):
      #            return True
      return False
          #raise KeyError('Wrong key type in tuple')
  
  #def compare_DFScodes
  def tuples_are_smaller(G1, G2):
      """
          Checks if tuples in G1 are less than tuples in G2
      """
      DFScodes_1, DFScodes_2 = G1, G2
      if len(DFScodes_1) != len(DFScodes_2):
          raise Exception('Size of the two graphs are not equal')
      for i in range(0, len(DFScodes_1)):
          t1, t2 = DFScodes_1[i], DFScodes_2[i]
          is_smaller = tuple_is_smaller(t1,t2)
          if is_smaller:
              return True
      return False
  
  def get_minimum_DFS(G_list):
      """
          Finds the graph with smallest DFS code i.e. the canonical graph
      """
      # Initialize first one as minimum
      min_G = G_list[0]
      min_idx = 0
      counts = np.zeros(len(G_list))
      for i in range(0, len(G_list)):
          for j in range(0, len(G_list)):
              if i == j:
                  continue
              is_smaller = tuples_are_smaller(G_list[i], G_list[j])
              if not is_smaller:
                  counts[i] += 1
      min_idx = np.argmin(counts)
      min_G = G_list[min_idx]
      return min_G, min_idx
  
  def subgraph_isomorphisms(C, G):
      """
          Returns the set of all isomorphisms between C and G
      """
      # Initialize set of isomorphisms by mapping vertex 0 in C
      # to each vertex x in G that shares the same label as 0s
      #G.print_graph()
      phi_c = []
      G_C = DFS2G(C)
      v0 = G_C.get_min_vertex()
      for v in G.vertices:
          if v.label == v0.label:
              phi_c.append([(v0.id, v.id)])
      for i, t in enumerate(C):
          u, v, L_u, L_v, L_uv = t    # Expand extended edge
          phi_c_prime = []            # partial isomorphisms
          for phi in phi_c:
              # phi is a list of transformations
              if v > u:
                  # Forward edge
                  try:
                      phi_u = transform_vertex(u, phi)
                  except Exception as e:
                      continue
                  # Find neighbors of transformed vertex
                  vertex = G.get_vertex(phi_u)
                  neighbors = G.adjacent_connections(vertex)
                  for e, x in neighbors:
                      # Check if an inverse transformation exists
                      inv_trans_exists = check_inv_exists(x.id, phi)
                      if (not inv_trans_exists) and \
                          (x.label == L_v) and \
                          (e.label == L_uv):
                          phi_prime = list(phi)
                          phi_prime.append((v, x.id))
                          phi_c_prime.append(list(phi_prime))
              else:
                  # Backward edge
                  try:
                      phi_u = transform_vertex(u, phi)
                      phi_v = transform_vertex(v, phi)
                  except Exception as e:
                      #print('abe2')
                      continue
                  # Find neighbors of transformed vertex
                  vertex = G.get_vertex(phi_u)
                  neighbors = G.adjacent_connections(vertex)
                  for e, x in neighbors:
                      if phi_v == x.id:
                          phi_c_prime.append(list(phi))
                          break
          phi_c = list(phi_c_prime)
      return phi_c
  
  def check_inv_exists(v, phi):
      """
          Given a vertex id u and a set of partial isomorphisms phi.
          Returns True if an inverse transformation exists for v
      """
      for _phi in phi:
          if _phi[1] == v:
              return True
      return False
  
  def inv_transform_vertex(x, phi):
      """
          Given a vertex id x and a set of partial isomorphisms phi.
          Returns the inverse transformed vertex id
      """
      for _phi in phi:
          if _phi[1] == x:
              return _phi[0]
      raise Exception('Could not find inverse transformation')
  
  def transform_vertex(u, phi):
      """
          Given a vertex id u and a set of partial isomorphisms phi.
          Returns the transformed vertex id
      """
      for _phi in phi:
          if _phi[0] == u:
              return _phi[1]
      raise Exception('u couldn\' be found in the isomorphisms')
  
  def RMPE(C, D):
      """
          Implements the RightMostPath-Extensions algorithm.
          Given a frequent canonical DFS code C and a list of graphs D, a
          set of possible rightmost path extensions from C, along with
          their support values are computed.
      """
      # Create graph of C -> G(C)
      G_C = DFS2G(C=C)
      # Only if C is not empty
      if len(C) > 0:
          # Compute rightmost path
          R = get_rightmost_path(G_C)
          u_r = R.vertices[len(R.vertices)-1].dfs_id
          L_u_r = R.vertices[len(R.vertices)-1].label
      E = [] # set of extensions from C
      for i, G in enumerate(D):
          if len(C) == 0: # If C is empty
              # add distinct label tuples in G_i as forward extensions
              for e in G.edges:
                  L_x, L_y, L_xy = e.from_vertex.label, e.to_vertex.label, e.label
                  f = (0, 1, L_x, L_y, L_xy)
                  E.append((i, f))
                  f = (0, 1, L_y, L_x, L_xy)
                  E.append((i, f))
          else:
              # Get subgraph isomorphisms
              phi_c_i = subgraph_isomorphisms(C, G)
              for phi in phi_c_i:
                  ############################################
                  # Backward extensions from rightmost child #
                  ############################################
                  phi_u_r = transform_vertex(u_r, phi)
                  # Find neighbors of transformed vertex
                  vertex = G.get_vertex(phi_u_r)
                  neighbors = G.adjacent_connections(vertex)
                  for e, x in neighbors:
                      if check_inv_exists(x.id, phi):
                          v = inv_transform_vertex(x.id, phi)
                          if R.contains_vertex_id(id=v) and \
                             not G_C.contains_edge(from_id=u_r, to_id=v):
                              _e = G.get_edge(transform_vertex(v, phi), phi_u_r)
                              if _e is None:
                                  raise Exception('Couldn\'t find edge')
                              L_v = G_C.get_vertex(id=v).label
                              b = (u_r, v, L_u_r, L_v, _e.label) # What label?
                              E.append((i, b))
                  ###################################################
                  # Forward extensions from nodes on rightmost path #
                  ###################################################
                  for u in R.vertices:
                      phi_u = transform_vertex(u.id, phi)
                      # Find neighbors of transformed vertex
                      vertex = G.get_vertex(phi_u)
                      neighbors = G.adjacent_connections(vertex)
                      for e, x in neighbors:
                          if not check_inv_exists(x.id, phi):
                              f = (u.id, u_r + 1, vertex.label, x.label, e.label)
                              E.append((i, f))
      # Only use distinct tuples
      E = list(set(E))
      extensions = list(set([e for i,e in E]))
      extensions = sort_tuples(extensions)
      pairs = []
      for ext in extensions:
          sup = 0
          for s in E:
              _, tup = s
              if tup == ext:
                  sup += 1
          pairs.append((ext, sup))
      return pairs
  
  def sort_tuples(E):
      """
          Sort a list of tuples using the get_minimum_DFS function.
      """
      sorted_tuples = []
      tuples = [[t] for t in E]
      for i in range(0, len(tuples)):
          min_G, min_idx = get_minimum_DFS(tuples)
          sorted_tuples.append(tuples[min_idx][0])
          del tuples[min_idx]
      return sorted_tuples
  
  def compute_support(C, D):
      """
          Computes the support of subgraph C in set of graphs D
      """
      sup = 0
      for i, G in enumerate(D):
          phi_c_i = subgraph_isomorphisms(C, D[i])
          if len(phi_c_i) > 0:
              sup += 1
      return sup
  
  def is_canonical(C):
      """
          Checks if C is canonical
      """
      D_C = [DFS2G(C)]    # graph corresponding to code C
      C_star = []         # initialize canonical DFScode
      k = len(C)
      for i in range(0, k):
          E = RMPE(C_star, D_C)
          if len(E) == 0:
              break
          G_list = [[_e[0]] for _e in E]
          min_G, min_idx = get_minimum_DFS(G_list)
          s_i = E[min_idx][0]
          sup_s_i = E[min_idx][1]
          if tuple_is_smaller(s_i, C[i]):
              return False
          C_star.extend([s_i])
      return True # no smaller code exists -> C is canonical
  
  def g_span(C, D, min_sup, extensions):
      """
          Finds possible frequent and canonical extensions of C in D, using
          min_sup as lowest allowed support value.
          Results are stored in extensions
      """
      #extensions.append(C)
      E = RMPE(C, D)
      for t, sup_t in E:
          # extend the code with extended edge tuple t
          C_prime = list(C)
          C_prime.extend([t])
          # record the support of new extension
          sup_C_prime = sup_t
          # recursively call gSpan if code is frequent and canonical
          if (sup_C_prime >= min_sup) and is_canonical(C_prime):
              extensions.append(C_prime)
              g_span(C_prime, D, min_sup, extensions)
  