Classes | |
class | Node |
class | Marking |
class | PowerCircuit |
class | PowerCircuitCompMatrix |
class | PowerCircuitGraph |
struct | Row |
struct | Col |
class | SignMatrix |
Typedefs | |
typedef char | Sign |
Functions | |
void | addSigns (const Sign &op1, const Sign &op2, Sign &result, Sign &carry) |
int | compareSigns (const Sign &op1, const Sign &op2) |
int | signToInt (const Sign &s) |
Sign | negateSign (const Sign &s) |
std::string | signToString (const Sign &s) |
Variables | |
const Sign | ZERO = 0 |
const Sign | PLUS = 1 |
const Sign | MINUS = 2 |
const Row | UNDEFINED_ROW |
const Col | UNDEFINED_COL |
This package implements power circuits in two different ways. The first one uses compact representation of markings as defined in [1]. The tree containing all markings is stored not as a graph but as a matrix to improve access time. This implementation is asymptotically optimal.
The other implementation (PowerCircuitGraph) stores the graph by adjacency lists and resembles the less technical approach chosen in [2]. Markings, too, are stored as lists. This implementation does not make use of compact representations. Thus, it is not theoretically optimal, but usually faster for typical inputs as it uses a lot of overhead.
Both power-circuit-classes are derived from the abstract class PowerCircuit and can be used interchangably.
To perform calculations with power circuits, create an instance of one of the above classes. The PowerCircuit class provides methods to create markings, perform reduction, insert edges into the graph (connect), and other tasks.
Markings work like references to the respective internal representations. Thus the assignment operator does not create a deep copy of a marking. However all arithmetic operations create new markings, so you can keep the old ones. It is also not necessary (and not possible) to delete markings (in the PowerCircuitGraph class once there is no marking pointing onto an internal marking, its memory is automatically deallocated). Just make sure that you create markings only for the time you really need them.
To get an idea of how to use power circuits, you might want to take a look at the examples included in this package, where power circuits are used to solve the word problem in certain groups.
In order to use the draw method you need graphviz installed on your computer (download from http://www.graphviz.org/). This method creates a postscript file with a graphical depiction of the graph.
The documentation is created with doxygen (see http://www.stack.nl/~dimitri/doxygen/index.html). To create the documentation in html and latex format use "doxygen". You can change the settings for the documentation in the file "Doxyfile". If "Doxyfile" does not exist, use "doxygen -g" to create it.
A lot of the theoretical background of power circuits is due to Sasha Ushakov. We thank him for his helpful advice, and also for the invitation to th Stevens Institute where parts of this implementation were developed.
[1] V. Diekert, J. Laun, A. Ushakov. Efficient algorithms for highly compressed data: The Word Problem in Higman's Group is in P. Preprint, 2011. http://arxiv.org/abs/1103.1232
[2] V. Diekert, J. Laun, A. Ushakov. Efficient algorithms for highly compressed data: The Word Problem in Higman's Group is in P. Conference version, to appear, 2011.
typedef char PC::Sign |
void PC::addSigns | ( | const Sign & | op1, | |
const Sign & | op2, | |||
Sign & | result, | |||
Sign & | carry | |||
) |
int PC::compareSigns | ( | const Sign & | op1, | |
const Sign & | op2 | |||
) |
Sign PC::negateSign | ( | const Sign & | s | ) |
int PC::signToInt | ( | const Sign & | s | ) |
std::string PC::signToString | ( | const Sign & | s | ) |
Definition at line 22 of file Sign.h.
Referenced by PC::SignMatrix< RowHdr, ColHdr, INTERNAL_TYPE >::printMatrix().
Definition at line 21 of file Sign.h.
Referenced by PC::SignMatrix< RowHdr, ColHdr, INTERNAL_TYPE >::printMatrix().
const Col PC::UNDEFINED_COL |
Definition at line 27 of file SignMatrix.h.
const Row PC::UNDEFINED_ROW |
Definition at line 26 of file SignMatrix.h.