'Parses a list of tokens in accordance to the MST parsing algorithm
for non-projective dependency parses.  Assumes that the tokens to
be parsed have already been tagged and those tags are provided.  Various
scoring methods can be used by implementing the ``DependencyScorerI``
interface and passing it to the training algorithm.
:type tokens: list(str)
:param tokens: A list of words or punctuation to be parsed.
:type tags: list(str)
:param tags: A list of tags corresponding by index to the words in the tokens list.
:return: An iterator of non-projective parses.
:rtype: iter(DependencyGraph)'

def parse(self, tokens, tags):

    self.inner_nodes = {}
    g_graph = DependencyGraph()
    for (index, token) in enumerate(tokens):
        g_graph.nodes[(index + 1)].update({'word': token, 'tag': tags[index], 'rel': 'NTOP', 'address': (index + 1)})
    g_graph.connect_graph()
    original_graph = DependencyGraph()
    for (index, token) in enumerate(tokens):
        original_graph.nodes[(index + 1)].update({'word': token, 'tag': tags[index], 'rel': 'NTOP', 'address': (index + 1)})
    b_graph = DependencyGraph()
    c_graph = DependencyGraph()
    for (index, token) in enumerate(tokens):
        c_graph.nodes[(index + 1)].update({'word': token, 'tag': tags[index], 'rel': 'NTOP', 'address': (index + 1)})
    self.initialize_edge_scores(g_graph)
    logger.debug(self.scores)
    unvisited_vertices = [vertex['address'] for vertex in c_graph.nodes.values()]
    nr_vertices = len(tokens)
    betas = {}
    while unvisited_vertices:
        current_vertex = unvisited_vertices.pop(0)
        logger.debug('current_vertex:    %s', current_vertex)
        current_node = g_graph.get_by_address(current_vertex)
        logger.debug('current_node:    %s', current_node)
        best_in_edge = self.best_incoming_arc(current_vertex)
        betas[current_vertex] = self.original_best_arc(current_vertex)
        logger.debug('best    in    arc:    %s    -->    %s', best_in_edge, current_vertex)
        for new_vertex in [current_vertex, best_in_edge]:
            b_graph.nodes[new_vertex].update({'word': 'TEMP', 'rel': 'NTOP', 'address': new_vertex})
        b_graph.add_arc(best_in_edge, current_vertex)
        cycle_path = b_graph.contains_cycle()
        if cycle_path:
            new_node = {'word': 'NONE', 'rel': 'NTOP', 'address': (nr_vertices + 1)}
            c_graph.add_node(new_node)
            self.update_edge_scores(new_node, cycle_path)
            self.collapse_nodes(new_node, cycle_path, g_graph, b_graph, c_graph)
            for cycle_index in cycle_path:
                c_graph.add_arc(new_node['address'], cycle_index)
            self.inner_nodes[new_node['address']] = cycle_path
            unvisited_vertices.insert(0, (nr_vertices + 1))
            nr_vertices += 1
            for cycle_node_address in cycle_path:
                b_graph.remove_by_address(cycle_node_address)
        logger.debug('g_graph:    %s', g_graph)
        logger.debug('b_graph:    %s', b_graph)
        logger.debug('c_graph:    %s', c_graph)
        logger.debug('Betas:    %s', betas)
        logger.debug('replaced    nodes    %s', self.inner_nodes)
    logger.debug('Final    scores:    %s', self.scores)
    logger.debug('Recovering    parse...')
    for i in range((len(tokens) + 1), (nr_vertices + 1)):
        betas[betas[i][1]] = betas[i]
    logger.debug('Betas:    %s', betas)
    for node in original_graph.nodes.values():
        node['deps'] = {}
    for i in range(1, (len(tokens) + 1)):
        original_graph.add_arc(betas[i][0], betas[i][1])
    logger.debug('Done.')
    (yield original_graph)
