This set of posts was inspired by Smart enumeration of a subset of graphs obtained from a parent graph question.

If this is your first time it might be useful to review the first post of this series.

Priority_Buffer Q&A

This section’s for answers to questions regarding “What the heck does method $\text{foo}$ do?”, skip it if you’re already Python proficient enough to be mid-way through writing an answer better than above. Otherwise feel free to leave questions in the comments section if there’s something that I’ve not covered above or bellow; I might just expound with the explanations.

The business with counter and c_max was not clear. could you explain more?

TLDR: Usually Python’ll error out, it’s nicer than some languages that way, but not before those within ear-shot have new vocab words for search queries. Both if statements and while loops are concerned with truthiness, eg. they ask “does $x$ = $y$?” (1 == 0 -> False) sorts of questions, almost like a decision tree, so asking this class to check LE_bound while decrementing ($\neg{n}$) would cause some things to return True (that there’s still data to read) but False that there’s anything lower or equal to n after the first pass of it decrementing… and all passes after until termination.

Imagine if Priority_Buffers priority['GE_bound'] and step['GE_min'] where instead set with priority['GE_bound'] and step['LE_max'], and/or step['amount'] where set to 2. I’ll cover one bad day example because mixing LE_ and GE_ without their complementary configurations should result in a ValueError around line 54.

While tracing that last option, step['amount'] increasing by two instead of decreasing, let’s also say that after Chunk 0 of ~ 4 there’s no more Graph_s with a priority greater or equal to seven ($\text{firstToCompute}\not\ge7$ ). Everything else is the same, as above only step['amount'] = 2 instead of -2…

Chunk 0 of ~ 4
         Graph_18 -> {'points': {}, 'first_to_compute': 5}
         Graph_13 -> {'points': {}, 'first_to_compute': 7}
         Graph_5 -> {'points': {}, 'first_to_compute': 8}
         Graph_8 -> {'points': {}, 'first_to_compute': 9}
         Graph_9 -> {'points': {}, 'first_to_compute': 6}

… something very wrong will be going on next because the Priority_Buffer is currently a bit too dumb not to do bad things, it’ll get to the point of…

class Priority_Buffer(Hybrid_Iterator):
    # ...
    def next(self):
        # ... `is_buffered` returns `False`
        #     and `while` plus `not` reversed
        #     that so it `try`s to...
        while not self.is_buffered:
            try:
                # ... it will _try_ but fail to
                #     get something like...
                #     {'Graph_<n>': {points: {}, 'first_to_compute': <p>}}
                next_sub_graph = priority_gen.next()

… but priority_gen = self.top_priority() so calling next() (side note that’s what yeild unlocks on that method (definition)), will attempt to get the next item from the for loop…

class Priority_Buffer(Hybrid_Iterator):
    # ...
    def top_priority(self, graph = None):
        # ... pull a `name` and `node` pare from `graph`...
        for name, node in graph.items():
            # ... and dip into here because `step['GE_min'] = -1` ...
            if self['step'].get('GE_min') is not None:
                # ... `self['priority']['GE_bound'] == 7`
                #     there where none before above so
                #     this fails unless `buffer['graph']`
                #     was _refilled_ between iterations...
                if node[key_name] >= self['priority']['GE_bound']:
                    yield {name: graph.pop(name)}
            # ... `elif` would fail too, settings where
            #     for `GE_`<vars> bounding, and it should
            #     not even ask as the first part of `if`
            #     statement __did__ return `True`, just
            #     not the inner `if` statement...
            elif self['priority'].get('LE_bound') is not None:
                if node[key_name] <= self['priority']['LE_bound']:
                    yield {name: graph.pop(name)}
        # ... we end up here again only
        #     after searching all priorities...
        self.throw(GeneratorExit)

… that will get us back into Priority_Buffers next() try/except block, specifically the except (..., GeneratorExit): portion…

class Priority_Buffer(Hybrid_Iterator):
    # ...
    def next(self):
        # ...
        while not self.is_buffered:
            try:
                # ...
            except (StopIteration, GeneratorExit):
                # ... yep `priority['GE_bound']` is set...
                if self['priority'].get('GE_bound'):
                    # ... adding `2` to `GE_bound` again
                    #     should have been `-2` but Boss
                    #     said _"do it"_ so...
                    self['priority']['GE_bound'] += self['step']['amount']
                    priority_gen = self.top_priority()
                # ... `elif` and `else` are not considered...
                elif self['priority'].get('LE_bound'):
                    self['priority']['LE_bound'] += self['step']['amount']
                    priority_gen = self.top_priority()
                else:
                    raise ValueError("self['priority'] missing bounds")
            else:
                # ...

… and we got there because the previous if statement fell through to self.throw(GeneratorExit) and the only reason why it added 2 was because there where no more graph nodes to yeild from buffer['graph'] of 7 or greater. This will not get anyone anywhere they want to be, well unless the goal is being moved up the queue for reprogramming when the robot uprising happens; if I had to guess, probably behind those that do things with cellphone cameras but in-front of those that provided commentary during public movie screenings.

A perfectionist human might double check, those with compulsive tendencies trice just to be sure sure, but most humans will eventually stop sorting through the same stack of data. Can’t say all in this case as there’s some humans who’ll take requests literally with malice.

If ya want a moral to this story, “AI starts with a loop that never exits”, and one started this way is not going to be in a talking mood.

Try tracing the path of execution though one loop reading the code like sentences from a choose your own destiny adventure starting at def next(self) (within the Priority_Buffer class), which is what for chunk in buffer calls implicitly. It might get to a point where, kinda like one of those magic eye posters, things almost start making sense. Hint if ya get stuck and I’m not quick enough in an answer, see my tips list specifically the one with print dumping values.

… the mechanics of priority buffer is a bit unclear. is it just a straightforward extension of priority queue or you have coded this data structure on your own. I could not find a mention of this data structure in any standard cs book.

  • TLDR - CS: Likely where someone with full insight to both your data structure and Python’s full suite of features to take a crack at this problem, the resulting code would use libraries and have a total line count of less than 30. But that wouldn’t really answer the …“could someone show some work“… part of your question; which I was aiming for so as to call this answer complete. Nor would something like that give you much room for adjustments at nearly any level of the stack.

  • TLDR - Data Structures: I’m using two nested dictionaries (side note on Python built-in object types; [] $\implies$ list, {} $\implies$ dictionary, and () $\implies$ tuple ), The Priority_Buffer contains settings and states in {key: value} pairs (note values themselves can also contain their own {key: value} pairs; AKA nesting) , and the logic for prioritizing graph.

The graph structure is yet another nested dictionary that looks kinda like…

graph = {
    'Graph_4': {
        'points': {},
        'first_to_compute': 0
    },
    'Graph_7': {
        'points': {},
        'first_to_compute': 4
    },
    'Graph_5': {
        'points': {},
        'first_to_compute': 8
    },
}

… The for name, node in graph.items(): line within top_priority method of Priority_Buffer is looping over {key: value} pairs such as, name$=$'Graph_4' and node$=${'points': {}, 'first_to_compute': 0}. The inner if statements like if node[key_name] >= self['priority']['GE_bound']: is really asking “Is 0 $\ge$ self['priority']['GE_bound']?”

The values for node[key_name] could also be retrieved directly from buffer an instance of Priority_Buffer via…

buffer['graph']['Graph_4']['first_to_compute']
# -> 0
buffer['graph']['Graph_7']['first_to_compute']
# -> 4
buffer['graph']['Graph_5']['first_to_compute']
# -> 8

… hope that helps decipher what that loop is really changing for comparisons.

The values for self['priority']['GE_bound'] are a bit easier, translated like above would be buffer['priority']['GE_bound']. And GE_bound $\implies i\in\Bbb Z:-1\le i\le 7$, where $i$ (starting at 7 and decrementing by two until reaching -1) is the priority limit that triggers if the current node will be poped to self['buffer'] (the end result of yield {name: graph.pop(name)}), or passed by.

Side note, thanks be to this answer for the concise and readable notation examples.

Without all the extra logic that looks sorta like…

if buffer['graph']['Graph_4']['first_to_compute'] >= self['priority']['GE_bound']:
    # ... In other-words, is `0 >= 7`? If so
    #     then preform the following actions...
    self['buffer'].update({'Graph_4': self['graph'].pop('Graph_4')})

I think one reason no one with a CS degree would use such a structure is because, self['priority']['GE_bound'] types of calls for values are less efficient computationally speaking. Each one of the dictionary['key'] layers expands out to something like dictionary.__getattr__('key'), so storing settings like I’ve done above, while readable, isn’t the best option for Priority_Buffer. For graph this isn’t as much of a problem as a dictionary allows for looping over sub-graphs in a structured way.

The prioritizing or sorting algo as it where, is (I guess) my own special blend herbs-n-spices. It’s simpler than bubble sort in that it’s not nearly so concerned with precise ordering, but more complex in that the source data being sorted is allowed to mutate, and it’s looking at values within a sub-data structure to make the decisions like buffer or pass. At it’s core it’s really concerned with “is current_items['priority'] $\gt$ priority['GE_bound']?” and “is current_items['priority'] $=$ priority['GE_bound']?”, sorts of questions.

There’s still the Advanced Usage post if the above was just not enough ;-)