LIBINT
2.6.0
|
DirectedGraph is an implementation of a directed graph composed of vertices represented by DGVertex objects. More...
#include <dg.h>
Public Types | |
typedef DGVertex | vertex |
typedef DGArc | arc |
typedef SafePtr< DGVertex > | ver_ptr |
typedef SafePtr< DGArc > | arc_ptr |
typedef DGVertexKey | key_type |
typedef std::multimap< key_type, ver_ptr > | VPtrAssociativeContainer |
typedef std::list< ver_ptr > | VPtrSequenceContainer |
typedef VPtrSequenceContainer | targets |
typedef VPtrAssociativeContainer | vertices |
typedef VPtrSequenceContainer | vertices |
typedef targets::iterator | target_iter |
typedef targets::const_iterator | target_citer |
typedef vertices::iterator | ver_iter |
typedef vertices::const_iterator | ver_citer |
typedef int | address |
typedef unsigned int | size |
typedef std::vector< address > | addresses |
typedef void(DGVertex::* | DGVertexMethodPtr) () |
Public Member Functions | |
DirectedGraph () | |
Creates an empty DAG. More... | |
unsigned int | num_vertices () const |
Returns the number of vertices. | |
const vertices & | all_vertices () const |
Returns all vertices. | |
const targets & | all_targets () const |
Returns all targets. | |
const SafePtr< DGVertex > & | find (const SafePtr< DGVertex > &v) const |
Find vertex v or it's equivalent on the graph. More... | |
SafePtr< DGVertex > | append_vertex (const SafePtr< DGVertex > &v) |
appends v to the graph. More... | |
void | append_target (const SafePtr< DGVertex > &) |
non-template append_target appends the vertex to the graph as a target | |
template<class I , class RR > | |
void | append_target (const SafePtr< I > &target) |
append_target appends I to the graph as a target vertex and applies RR to it. More... | |
template<class RR > | |
void | apply_to_all () |
apply_to_all applies RR to all vertices already on the graph. More... | |
void | apply (const SafePtr< Strategy > &strategy, const SafePtr< Tactic > &tactic) |
after all append_target's have been called, apply(strategy,tactic) constructs a graph. More... | |
template<DGVertexMethodPtr method> | |
void | apply_at (const SafePtr< DGVertex > &vertex) const |
apply_at<method>(vertex) calls method() on vertex and all of its descendants | |
template<class Method > | |
void | foreach (Method &m) |
calls Method(v) for each v, iterating in forward direction | |
template<class Method > | |
void | foreach (Method &m) const |
calls Method(v) for each v, iterating in forward direction | |
template<class Method > | |
void | rforeach (Method &m) |
calls Method(v) for each v, iterating in reverse direction | |
template<class Method > | |
void | rforeach (Method &m) const |
calls Method(v) for each v, iterating in reverse direction | |
void | optimize_rr_out (const SafePtr< CodeContext > &context) |
after Strategy has been applied, simple recurrence relations need to be optimized away. More... | |
void | traverse () |
after all apply's have been called, traverse() construct a heuristic order of traversal for the graph. More... | |
void | update_func_names () |
update func_names_ | |
void | debug_print_traversal (std::ostream &os) const |
Prints out call sequence. | |
void | print_to_dot (bool symbols, std::ostream &os=std::cout) const |
Prints out the graph in format understood by program "dot" of package "graphviz". More... | |
void | generate_code (const SafePtr< CodeContext > &context, const SafePtr< MemoryManager > &memman, const SafePtr< ImplicitDimensions > &dims, const SafePtr< CodeSymbols > &args, const std::string &label, std::ostream &decl, std::ostream &code) |
Generates code for the current computation using context. More... | |
void | reset () |
Resets the graph and all vertices. More... | |
template<class RR > | |
unsigned int | num_children_on (const SafePtr< RR > &rr) const |
num_children_on(rr) returns the number of children of rr which are already on this graph. | |
SafePtr< GraphRegistry > & | registry () |
Returns the registry. | |
const SafePtr< GraphRegistry > & | registry () const |
const std::string & | label () const |
return the graph label | |
void | set_label (const std::string &new_label) |
sets label to new_label | |
bool | missing_prerequisites () const |
return true if there are vertices with 0 children but not pre-computed | |
DirectedGraph is an implementation of a directed graph composed of vertices represented by DGVertex objects.
Most important operations will assume that this is a DAG, i.e. there are no directed cycles.
DirectedGraph::DirectedGraph | ( | ) |
Creates an empty DAG.
Actual initialization of the graph must be done using append_target
|
inline |
append_target appends I to the graph as a target vertex and applies RR to it.
append_target can be called multiple times on the same graph if more than one target vertex is needed.
I must derive from DGVertex. RR must derive from RecurrenceRelation. RR has a constructor which takes const I& as the only argument. RR must have a public member const I* child(unsigned int) .
NOTE TO SELF : need to implement these restrictions using standard Bjarne Stroustrup's approach.
appends v to the graph.
If v's copy is already on the graph, return the pointer to the copy. Else return pointer to *v.
References libint2::DGVertex::dg(), and libint2::DGVertex::label().
Referenced by append_target(), and apply().
void DirectedGraph::apply | ( | const SafePtr< Strategy > & | strategy, |
const SafePtr< Tactic > & | tactic | ||
) |
after all append_target's have been called, apply(strategy,tactic) constructs a graph.
Apply a strategy to all vertices not yet computed (i.e. which do not have exit arcs)
strategy specifies how to apply recurrence relations. The goal of strategies is to connect the target vertices to simpler, precomputable vertices. There usually are many ways to reduce a vertex. Tactic specifies which of these possibilities to choose.
References append_vertex().
|
inline |
apply_to_all applies RR to all vertices already on the graph.
RR must derive from RecurrenceRelation. RR must define TargetType as a typedef. RR must have a public member const DGVertex* child(unsigned int) .
NOTE TO SELF : need to implement these restrictions using standard Bjarne Stroustrup's approach.
Find vertex v or it's equivalent on the graph.
Return null pointer if not found. Computational cost for a graph based on a nonassociative container may be high
void DirectedGraph::generate_code | ( | const SafePtr< CodeContext > & | context, |
const SafePtr< MemoryManager > & | memman, | ||
const SafePtr< ImplicitDimensions > & | dims, | ||
const SafePtr< CodeSymbols > & | args, | ||
const std::string & | label, | ||
std::ostream & | decl, | ||
std::ostream & | code | ||
) |
Generates code for the current computation using context.
dims specifies the implicit dimensions, args specifies the code symbols for the arguments to the function, label specifies the tag for the computation, decl specifies the stream to receive declaration code, code specifies the stream to receive the definition code
References libint2::LibraryTaskManager::current(), libint2::LibraryTaskManager::Instance(), label(), libint2::label_to_funcname(), libint2::merge(), missing_prerequisites(), registry(), and update_func_names().
void DirectedGraph::optimize_rr_out | ( | const SafePtr< CodeContext > & | context | ) |
after Strategy has been applied, simple recurrence relations need to be optimized away.
optimize_rr_out() will replace all simple recurrence relations with code representing them.
void DirectedGraph::print_to_dot | ( | bool | symbols, |
std::ostream & | os = std::cout |
||
) | const |
Prints out the graph in format understood by program "dot" of package "graphviz".
If symbols is true then label vertices using their symbols rather than (descriptive) labels.
void DirectedGraph::reset | ( | ) |
Resets the graph and all vertices.
The stack of unresolved recurrence relations is preserved.
void DirectedGraph::traverse | ( | ) |
after all apply's have been called, traverse() construct a heuristic order of traversal for the graph.
Recursively traverse depth-first, once a node has been tagged by all of its parents schedule its computation.