Graph stitching

This tool is a little framework to determine possible merges between two graphs based on a set of required additional relationships (aka stitches / edges). Based on a set of possible resulting candidate graphs we validate which of the candidates graphs is the “best”.

An example use case is a packaging problem: e.g. set of entities need to be placed in an container which already contains a set of different entities.

Let’s assume the entities to be placed can be described using a request graph (as in entities having a relationship) and the existing container can be described as a graph as well (entities having relationships and are already ranked). Nodes & edges in the existing container should be ranked to indicate how loaded/busy they are.

Adding a new set of entities (e.g. a lamp described by the lamp bulb & fitting) to the existing container (e.g. a house) automatically requires certain relationships to be added (e.g. the power cable which is plugged into the socket). But not all possible relationship setups might be good as e.g. adding another consumer (the lamp) to a certain power socket might impact other consumers (the microwave) of the same socket as the fuse might give up. How loaded the power socket is can be expressed through the previously mentioned rank.

Hence stitching two graphs together is done by adding relationships (edges) between certain types of nodes from the container and the request. As multiple stitches are possible we need to know determine and validate (adhering conditions like compositions and attribute requirements) the possible candidates and determine the best. Defining the best one can be done using a very simple principle. A good stitch is defined by:

Through the pluggable architecture of this tool we can now implement different algorithms on how to determine if a resulting graph is good & stable:

This tool obviously can also be used to enhance the placement of workload after a temporal scheduling decision has been made (based on round-robin, preemptive, priority, fair share, fifo, … algorithms) within clusters.

graph stitcher’s internals

As mentioned above graph stitcher is pluggable, to test different algorithms of graph stitching & validation of the same. Hence it has a pluggable interface for the stitch() and validate() routine (see BaseStitcher class).

To stitch two graphs the tool needs to know which relationships are needed:

Type of source node | Type of target node
-----------------------------------------
type_a              | type_x
...                 | ...

These are stored in the file (stitch.json). Sample graphs & tests can be found in the tests directory as well.

There is a conditional_filter() function implemented which can do some basic filtering. Implementing your own is possible by passing conditions and the conditional_filter() routine you want to use as parameters to the stich() call.

The basic filter support the following operations:

The following dictionary can be passed in as a composition condition:

{
 'attributes': [('eq', ('a', ('foo', 'y'))),
                ('neq', ('a', ('foo', 5))),
                ('lt', ('a', ('foo', 4))),
                ('lg', ('a', ('foo', 7))),
                ('regex', ('a', ('foo', '^a')))],
 'compositions': [('same', ('1', '2')),
                  ('diff', ('3', '4')),
                  ('share', ('group', ['x', 'y'])),
                  ('nshare', ('group', ['a', 'b']))]
}

This graph stitcher is mostly developed to test & play around. Also to check if evolutionary algorithms can be developed to determine the best resulting graph. More details on the algorithms in place can be found in the /docs directory.

Running it

Just do a:

$ ./run_me.py

You will hopefully see something similar to the following diagram. The k, l, m nodes form the request. All other nodes represent the container (node colors indicate the rank, node forms the different types). The stitches are dotted lines. Each graph is a candidate solution, the results of the validation are shown as titles of the graphs.

output

To test the evolutionary algorithm run:

$ ./run_me.py -a evolutionary

Please note that it might not always find a set of good solutions, as the container and the request are pretty small. Also note that currently the fitness function expresses a fitness for the given conditions; and does not include a fitness value for the validation phase.

To test the bidding algorithm in which the container nodes try to find the optimal solution run:

$ ./run_me.py -a bidding