'Computes the probability of a dependency graph based
on the parser\'s probability model (defined by the parser\'s
statistical dependency grammar).
:param dg: A dependency graph to score.
:type dg: DependencyGraph
:return: The probability of the dependency graph.
:rtype: int'

def compute_prob(self, dg):

    prob = 1.0
    for node_index in range(1, len(dg.nodes)):
        children = list(chain(*dg.nodes[node_index][u'deps'].values()))
        nr_left_children = dg.left_children(node_index)
        nr_right_children = dg.right_children(node_index)
        nr_children = (nr_left_children + nr_right_children)
        for child_index in range((0 - (nr_left_children + 1)), (nr_right_children + 2)):
            head_word = dg.nodes[node_index][u'word']
            head_tag = dg.nodes[node_index][u'tag']
            child = u'STOP'
            child_tag = u'STOP'
            prev_word = u'START'
            prev_tag = u'START'
            if (child_index < 0):
                array_index = (child_index + nr_left_children)
                if (array_index >= 0):
                    child = dg.nodes[children[array_index]][u'word']
                    child_tag = dg.nodes[children[array_index]][u'tag']
                if (child_index != (-1)):
                    prev_word = dg.nodes[children[(array_index + 1)]][u'word']
                    prev_tag = dg.nodes[children[(array_index + 1)]][u'tag']
                head_event = (u'(head    (%s    %s)    (mods    (%s,    %s,    %s)    left))' % (child, child_tag, prev_tag, head_word, head_tag))
                mod_event = (u'(mods    (%s,    %s,    %s)    left))' % (prev_tag, head_word, head_tag))
                h_count = self._grammar._events[head_event]
                m_count = self._grammar._events[mod_event]
                if (m_count != 0):
                    prob *= (h_count / m_count)
                else:
                    prob = 1e-08
            elif (child_index > 0):
                array_index = ((child_index + nr_left_children) - 1)
                if (array_index < nr_children):
                    child = dg.nodes[children[array_index]][u'word']
                    child_tag = dg.nodes[children[array_index]][u'tag']
                if (child_index != 1):
                    prev_word = dg.nodes[children[(array_index - 1)]][u'word']
                    prev_tag = dg.nodes[children[(array_index - 1)]][u'tag']
                head_event = (u'(head    (%s    %s)    (mods    (%s,    %s,    %s)    right))' % (child, child_tag, prev_tag, head_word, head_tag))
                mod_event = (u'(mods    (%s,    %s,    %s)    right))' % (prev_tag, head_word, head_tag))
                h_count = self._grammar._events[head_event]
                m_count = self._grammar._events[mod_event]
                if (m_count != 0):
                    prob *= (h_count / m_count)
                else:
                    prob = 1e-08
    return prob
