This computes various pebbling numbers for directed acyclic graphs.
C Python C++ Makefile Shell
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.gitignore
BUGS.org
Makefile
README.org
bfs.c
bfs.h
common.c
common.h
config.c
config.h
dag.c
dag.h
dot2pdf
dsbasic.c
dsbasic.h
example.dot
example.kth
example.pdf
example.png
exposetypes.c
hashtable.c
hashtable.h
kthparser.c
linegraph.py
pebble.c
pebbling.c
pebbling.h
rev-line-estimates.py
rev-pyr-estimates.py
rev-pyr-persistent.py
revpebble2qdimacs.c
statistics.c
statistics.h
timedflags.c
timedflags.h

README.org

Pebbling software

  • pebble
  • bwpebble
  • revpebble

Compilation

The code is in C99 standard. So you need a C99 compiler to compile the code. If you have it just type

make 

Usage

We provide three command line tools: pebble, bwpebble, revpebble. They output respectively a black, black/white, reversible pebbling of a directed acyclic graph given in input, within the upper bound to the number of pebbles given at command line.

If there is no such a pebbling, then the program fails and report it, otherwise it outputs the pebbling as a sequence of graphs written in dot [2] format, showing the pebbling.

It is required to choose an upper bound on the number of pebbles allowed, in order to limit the search space. The canonical command lines

pebble/bwpebble/revpebble -b 5 -i <inputfile>

which compute pebbling (if they exist) using the smallest amount of pebbles needed, provided it is at most 5.

For further info on the usage launch

pebble/bwpebble/revpebble -h

How to compute the shortest pebbling

If you just care about the shortest pebbling within a bound (in this example is 5) you can use the -t option

pebble/bwpebble/revpebble -b 5 -t -i <inputfile>

This will find the shortest pebbling with at most five pebbles. If there is a longer pebbling with at most 4 pebbles, the latter will be ignored.

How to compute a persistent pebbling

If you want to compute persistent pebbling add the -Z option to the command line. This option is available on bwpebble and revpebble.

Input format

Input graph must be given in the following format: the file can start with some comments line, each of them starting with character c. The next non black line must contain the number n of vertices in the graph. Then there must be $n$ non black lines, one for each vertex 1 ≤ i ≤ n. The lines have the format:

i : <pred 1> <pred 2> <pred 3> ... <pred k>

where <pred 1> <pred 2> <pred 3> ... <pred k> is the ordered list of all vertices which have an outgoing edge to vertex i. Here’s an example

c
c This is a DAG of 5 vertices
c
5
1  :
2  : 
3  : 1  
4  : 3  
5  : 2  4

which represents the graph

example.png

Canonical graphs

For some graph there is not need to provide an input file. Adding the option -p <h> or -2 <h> instead of the input graph, the pebbling is computed for the pyramid graph or tree graph, respectively, of height <h>. For example

pebble -b 7 -p 5 

computes a pebbling of cost 7 for the pyramid of height 5 (there is no pebbling of cost 6). Instead

revpebble -b 8 -2 4 

computes a reversible black pebbling for the tree of height 5.

On pebbling games

Here is a brief introduction to the notion of pebbling games and pebbling numbers, in order to understand better the purpose of the code.

We deal we directed acyclic graphs, which are directed graph with no directed cycles. In particular our program computes various complexity measures called pebbling numbers for graphs with a single sink (i.e. there is only one vertex which has no outgoing arcs).

Literature studies several types of pebbling games [1]: the directed acyclic graph starts empty; at each step the player may put a pebble on an empty vertex or remove it from a pebbled one, according to some rules which depend on the specific game.

Each game models a different kind of computations. The number of pebbles simultaneously on the graph at each step models the space (i.e. memory) used in that particular moment of the computation.

The (black, black/white, reversible) pebbling number of a directed acyclic single sink graph G is the smallest number n of pebbles such that there is a (black, black/white, reversible) pebbling of G which uses at most n pebbles at any moment of the game.

Black pebbling (or just “pebbling”)

The goal is to put a black pebble on the sink of the graph, and the rules are the following:

  • you can always remove a pebble from a vertex;
  • you can put a pebble on a vertex only if all predecessors are pebbled.

A vertex u is a predecessor of another vertex v if (u,v) is an arc in the directed graph. Therefore you can always put a pebble on a source vertex (i.e. a vertex with no incoming edges).

Black/White pebbling

This is a generalization of black pebbling. Now we have two types of pebbles, black and white, with opposite and dual behavior.

The goal is to place a pebble (either black or white) on the sink and then to remove all pebbles from the graph. Here’s the rules:

  • you can always remove a black pebble;
  • you can always place a white pebble;
  • a black pebble can be placed only if the predecessors of the vertex are pebbled;
  • a white pebble can be removed only if the predecessors of the vertex are pebbled.

Reversible pebbling

This is a variant of black pebbling in which the condition for a placement and a removal are the same. Indeed if a move is legal, the backward move is legal too.

The goal is to place a pebble on the sink. Here’s the rules:

  • a black pebble can be placed only if the predecessors of the vertex are pebbled;
  • a black pebble can be removed only if the predecessors of the vertex are pebbled.

Persistent pebbling

All three pebbling games (black, black/white, reversible) have a variant in which in the final position of the game the graph has a black pebble on the sink and no other pebbles on the graph.

Such a pebble is called a persistent (black, black/white, reversible) pebbling. It is easy to see that the persistent pebbling number is at most one more than the corresponding pebbling number. It is also easy to see that for black pebbling this condition does not make any difference (it does for the other games).

[1] For more information about pebbling of graph you can read the comprehensive survey by Jakob Nordstrӧm (link) soon to be published in Foundations and Trends in Theoretical Computer Science.

[2] dot tool is part of Graphviz (http://www.graphviz.org)