I'm building a Markov text poetry generator. The main method, which is attached below, performs a depth-first search through the Markov chain, which is implemented as a NetworkX digraph of Word objects, which have methods for determining whether e.g. a Word rhymes with another Word instance. At each level of the search, I filter the successor nodes to those that match user-supplied constraints - for example, first word in sequence must rhyme with last word in sequence, so lines of poetry with different poetic devices can be built from the Markov chain.The code I have works, but with large amounts of text (27412 unique words, 160892 edges between words) for certain combinations of constraints, especially rhyming ones, it takes a very long time to come up with a sequence that satisfies the constraints, if there is a possible sequence in the chain. Here's an example:  >>> vg = VerseGenerator(some_very_long_text)>>> cs = [Constraint(Word.rhymeswith, [0, 3])]>>> vg.build_sequence(4, [], cs)[Word(among), Word(the), Word(white), Word(young)] - 204ms via IPython %timeit>>> cs = [Constraint(Word.rhymeswith, [0, 9])]>>> vg.build_sequence(10, [], cs) - Doesn't terminate for at least 10 minutes Can anyone see a way I could speed this up, if any? I'm experimenting with Cython, but it will be a while before I get up to speed on it. Perhaps there is some clever graph theory property or algorithm I could use to preprocess it, or something?The code in its entirety is available at my Github. I'm using Python 3. I hope I have explained it clearly enough, but if not please point out what other information I should include.def build_sequence(self, length, predicates, constraints, order='roulette'):    ''' Traverse the graph in depth first order to build a sequence    of the given length which fits the supplied predicates. If a    matching sequence is not found, return partially constructed    sequence. Begins with a randomly selected word from the graph    '''    # If there are any multiple-word constraints that begin at    # this level, we need to create predicates so they can be    # applied at future search levels    def apply_constraints(cands, path, level, preds, cons):        cs = [c for c in cons if c.indices[0] == level]        search_nodes = []        for can in cands:            new_preds = []            for con in cs:                curried = partial(con.method, can)                sub = con.indices[1:]                new_preds.extend([Predicate(curried, i) for i in sub])            rec = {'word': can, 'parent': path, 'level': level,                   'preds': preds + new_preds}            search_nodes.append(rec)        return search_nodes    stack = []    level = 0    # Get candidate starting nodes    apply = [p.partial for p in predicates if p.index == level]    cands = self.filter_words(self.chain.nodes(), apply)    random.shuffle(cands)    branches = apply_constraints(cands, None, level, predicates, constraints)    stack.extend(branches)    while stack and level < length:        path = stack.pop()        prev = path['word']        level = path['level'] + 1        preds = path['preds']        # Filter nodes following previous word to get candidates for        # the next word in the sequence.        apply = [p.partial for p in preds if p.index == level]        succ = self.shuffled_successors(prev, order=order)        cands = self.filter_words(succ, apply)        branches = apply_constraints(cands, path, level, preds, constraints)        stack.extend(branches)    # Walk backward through final recursive record to build the    # resulting sentence    result = []    for i in range(level):        result.append(path['word'])        path = path['parent']    return reverse(result)
Speeding up Python depth-first search in large graph
python;performance;graph;natural language processing;markov chain