1
$\begingroup$

Suppose i have a graph $G$ of $n$ nodes. For each node someone has given us a recipe $R$ how to replace the node with a graph. So for node $i$, i have $m_i$ choices of graphs to replace it with. Thus, it is simple to see that given $G$, i can obtain $\prod\limits_{i=1}^n m_i$ graphs because of the recipe $R$ already given. For huge possibilities of graphs that can be obtained from $G$ using $R$, exhaustive enumeration is a poor choice due to computational infeasibility.

To avoid doing exhaustive enumeration because computers cannot run for days, we need to do selective enumeration of those graphs. One idea i could think was that we define biases based on user/operator input. Thus some graphs are more relevant/important than others. Using this as a guiding heuristic we can do some kind of pruning to avoid enumerating all possible graphs.

I have done a lot of hand-waving without any concrete stuff. That is why i posed this question. My question is could someone show some work where this is actually done in a concrete computational way rather than hand-waving, or suggest concrete computational steps to take in this direction?

EDIT:

Suppose we have a directed acyclic graphs with weighted edges. And cost of the graph is a non-linear function of the edge weights. We want to see if changing the graph using $R$ leads to graphs with costs less than some threshold range. We want to avoid doing exhaustive enumeration and do some smart algo method. What previous work has been done in this direction? What keywords to search in google scholar to find such algo methods?

$\endgroup$
  • 1
    $\begingroup$ Handwaving is OK in moderation but you need to give some idea of what you are evaluating - it seems like you want to choose the best set of transforms for the nodes of $G$? For some method of deciding "best". Are these perhaps directed acyclic graphs with weighted edges/nodes? $\endgroup$ – Joffan Aug 11 '17 at 0:39
  • $\begingroup$ Yes i had directed acyclic graphs with weighted edges in mind. I agree with your statement wholly. To make discussion concrete based on your comment i have made an addendum in my original question. $\endgroup$ – user_1_1_1 Aug 11 '17 at 18:44
  • $\begingroup$ For a computational example of pruning nodes from a graph with Python ya might want to check the Point toy class I wrote as an answer for a somewhat related question; specifically the cheapest of routes method demonstrates one way of returning a sub-set of nodes/Points who are the lowest or tied for lowest in cost to a calling process for further evaluation. As for smart algorithms it might be worth looking into sorting algos for bubbling up the most important points for preferential pre-filtering. $\endgroup$ – S0AndS0 Apr 1 at 6:40
1
$\begingroup$

Note from the future; I've condensed this answer and added this answer's source code to a GitHub repo, and more content on the pages site related to graphs, because it was getting rather verbose.


I'll attempt to assist with the following bits...

One idea I could think was that we define biases based on user/operator input. Thus some graphs are more relevant/important than others. Using this as a guiding heuristic we can do some kind of pruning to avoid enumerating all possible graphs.

... but first it's probably a good idea to get comfortable (snack and/or drink in other-words), it's going to be one of those posts ;-D

Your idea sounds smart for prioritizing computation of unordered (and possibly mutating) structured data sets, keeping humans in the loop allows for the illusion of control and given the strides being made in machine learning... enough hand-waving though time to focus on a portion of this problem; a prioritizing iterator.

The best way that I know how to express this is in Python, I'll try to keep it to a minimum as far as script size while also only using/inheriting built-ins so that the technical-debt (a measure of having to understand sets of $library_{dependency}$ before even beginning to code), for readers is kept to a minimum too. A balancing act but at least what I share is very generalizable.

Link to hybrid_iterator/__init__.py

a dependency of the following class that'll be used soon, it's mainly to keep code clean and mostly reliable between Python versions.

Bellow's a sketch of Hybrid_Iterator's super relationships with dict and Iterator classes

$$ \color{#CD8C00}{\fbox{ dict }{ \color{#2E8B57}{\xleftarrow[]{ \color{#000}{\text{super}_{\left(key\_word\_args\right)}} }} \over{\color{#CD8C00}{ \xrightarrow[\color{#000}{\text{returned value}}]{} }} }} \color{#2E8B57}{\fbox{ Hybrid~Iterator }{ \color{#2E8B57}{\xrightarrow[]{ \color{#000}{\text{super}_{\left(key\_word\_args\right)}} }} \over{\color{#00A}{ \xleftarrow[\color{#000}{\text{returned value}}]{} }} }} \color{#00A}{\fbox{ Iterator }} $$

Above is nothing overly special on it's own, in fact without modification it's in someways a worse dictionary than it was before. Hint, compare the lists of methods available for each via dir(), eg dir(Hybrid_Iterator) to see it's inner bits that can be called upon... But let's not get lost in the details, instead get past the prereqs, and on to the proof of concept code and it's usage.

Link to hybrid_iterator/priority_buffer.py

$$ \color{#2E8B57}{\fbox{ Hybrid~Iterator }{ \color{#8C0073}{\xleftarrow[]{ \color{#000}{\text{super}_{\left(key\_word\_args\right)}} }} \over{\color{#2E8B57}{ \xrightarrow[\color{#000}{\text{returned value}}]{} }} }} \color{#8C0073}{\fbox{ Priority~Buffer }} $$

Above is a sketch of the relationships being built between above and bellow code blocks.

Indeed that was some code so to cover the what's, hows, and whys I'll try to put it into some context with usage examples.


Usage Examples

Provided that the first script was saved to hybrid_iterator/__init__.py and the second to hybrid_iterator/priority_buffer.py (within what-ever sub-directory you've made and changed working directories to), it should be possible to run the following within a Python shell...

from priority_buffer import Priority_Buffer

... which should produce no output just a new line; thrilling for sure.

I'm going to ask Python to generate some toy data to play with, priorities will be randomly set within upper and lower bounds between 0 and 9 respectively...

from random import randint


graph = {}
for i in range(0, 21, 1):
    graph.update({
        "sub_graph_{0}".format(i): {
            'points': {},
            'first_to_compute': randint(0, 9),
        }
    })

Above should generate a graph dictionary that'll look sorta like the following...

for k, v in graph.items():
    print("{0} -> {1}".format(k, v))
# ...
# Graph_4 -> {'points': {}, 'first_to_compute': 0}
# Graph_7 -> {'points': {}, 'first_to_compute': 4}
# Graph_5 -> {'points': {}, 'first_to_compute': 8}
# ...

The first_to_compute keys are what are going to be used soon and I hope readers like it, doesn't really matter what you call this key so long as you're consistent between above and bellow code blocks. The sub_graphs key names are unimportant for these examples as dictionaries are unordered, only serving as a hash for look-ups. The points are just place-holders to show that more than one key value pair are allowed in a dictionary; well so long as the keys are unique. Note nesting dicts is often easer than getting data back out without forethought though so this should not be used in production without significant modifications.

Readers who really want something more substantial in complexity to substitute in for points empty dictionary can find a link within the comments of this OP's question to another class written for a different graph related question. However, for the following set of examples it'll not be important.

With all that set-up out of the way it is time to initialize the Priority_Buffer class!...

buffer = Priority_Buffer(
    graph = graph,
    priority = {'key_name': 'first_to_compute',
                'GE_bound': 7},
    step = {'amount': -2,
            'GE_min': -1},
    buffer_size = 5,
)

... then to loop it, safely...

counter = 0
c_max = int(len(graph.keys()) / buffer['buffer_size'] + 1)
# ... (21 / 5) + 1 -> int -> 5


for chunk in buffer:
    print("Chunk {count} of ~ {max}".format(
        count = counter, max = c_max - 1))

    for key, val in chunk['buffer'].items():
        print("\t{k} -> {v}".format(**{
            'k': key, 'v': val}))

    counter += 1

    if counter > c_max:
        raise Exception("Hunt for bugs!")

That business above with counter and c_max is to ensure an initialized Priority_Buffer with inputs that result in contemplating $\infty$ the wrong way are not disastrous.

... which should output something that looks like...

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}
# ... Trimmed for brevity...
Chunk 3 of ~ 4
         Graph_6 -> {'points': {}, 'first_to_compute': 0}
         Graph_4 -> {'points': {}, 'first_to_compute': 0}
         Graph_3 -> {'points': {}, 'first_to_compute': 0}
         Graph_16 -> {'points': {}, 'first_to_compute': 3}
         Graph_1 -> {'points': {}, 'first_to_compute': 2}
Chunk 4 of ~ 4
         Graph_0 -> {'points': {}, 'first_to_compute': 0}

The original graph dictionary should now be empty, destructive reads with pop() are a memory vs computation optimization feature as well as an attempt to mitigate looking over the same priorities ranges' worth of data too redundantly before expanding the search space.

If consuming the graph is not a desired behavior I believe Priority_Buffer(graph = dict(graph),...) copies the source data during initialization, this means you'd have two copies of the same data, however, Priority_Buffer's will on average always be decreasing... well that is unless you refill buffer['graph'] with an update({'sub_graph_<n>': ...}) before the main loop exits, which hint hint, allowing for such shenanigans on a loop is kinda why it's written the way it is ;-) though you'll want to refresh the buffer['GE_bound'] (or LE_bound) to ensure things are bubbling up again like they should.

Using the currently scripted methods you'll always get chunks size of buffer['buffer_size'] or less. The first found that are greater or equal to buffer['priority']['GE_bound'] (inverse for LE_bound) are returned as a chunk. If for example it didn't have enough on a given call of buffer.next() (implicitly called by loops), the search space would expand by buffer['step']['amount'] till either it reaches (or crosses) buffer['step']['GE_min'] or the buffer size is satisfied. There's a few other bits-n-bobs for exiting when graph is empty but that's the gist of it.

While it'll happily make mistakes on your behalf at the speed of "ohh sh..." I think it's a fair start (in that those within a range are prioritized, first-found $=$ first-poped), and close enough to what you're asking for that it hacking into something better is totally likely. This is probably a good point to pause and allow things to steep. When you're ready, the following are a few extra tips;

  • be careful with step['amount']'s direction; decrement (use negative numbers) when using GE_ related configurations, and increment when using LE_,

  • _bounds should be -+1 (less or more by 1) than the total target priority['key_name'] priority value max/min to avoid having a bad time.

  • the priority['GE_bound'], buffer_size, and other values should be played with because ideal settings will depend upon system resources available.

  • for applying $R$ at some level in the execution stack check the other answer I linked in your question's comments for hints on adding first class function calls, I used Python lambdas there (quick-n-dirty), but functions and methods work similarly.

  • try running the file as a script, eg. python priority_buffer.py, a few times to observe the behavior of the current sorting methods.

  • If new to Python try, adding print("something -> {0}".format('value')) (replacing 'value' with something), lines anywhere that you want to dump some info during execution, or use a fancy IDE such as Atom (with a few plugins) to enable setting break points and step through parts that don't quite make sense.

Hope this was somewhat helpful in getting ya up-to speed with how one can develop an approach for solving such problems.


For even more on this subject, heres some links to Q&A and Advanced Usage, content has been split out into posts hosted by GitHub Pages because of character limits.

$\endgroup$
  • 1
    $\begingroup$ You must write books and blogs. Your style is awesome!!! $\endgroup$ – user_1_1_1 Apr 3 at 19:36
  • $\begingroup$ The business with counter and c_max was not clear. could u explian more? $\endgroup$ – user_1_1_1 Apr 3 at 20:00
  • 1
    $\begingroup$ Thanks, I'm glad I come across as mostly coherent, I'm not currently cool enough to keep a regular blog; tried it once but it felt like the good ship lifestyle on repeat for a month solid, which regardless of initial opinion I'm pretty sure anyone would be up for verity even if it's Jingle Cats... I've updated the answer with a bit more on c_max and the whys of it's importance within the last section. $\endgroup$ – S0AndS0 Apr 4 at 6:48
  • $\begingroup$ thanks, lastly 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. $\endgroup$ – user_1_1_1 Apr 4 at 21:50
  • $\begingroup$ It's two nested dictionaries, one with methods for prioritizing the other. I chose to use dictionaries because it's possible to print(buffer) and dump it's state (easy inspection) at any point. They're what I consider to be one of the more friendly Python objects to organize the data structure it seemed like you where describing. Near the end of the recent update you'll find I get into what the code is doing a bit more within the Q&A links, and with the Advanced Usage link I think I'm very close to a complete (though non-optimal) answer... which future revisions might sort out. $\endgroup$ – S0AndS0 Apr 5 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.