LIBINT  2.6.0
Public Types | Public Member Functions | List of all members
libint2::DirectedGraph Class Reference

DirectedGraph is an implementation of a directed graph composed of vertices represented by DGVertex objects. More...

#include <dg.h>

Inheritance diagram for libint2::DirectedGraph:
Inheritance graph
[legend]
Collaboration diagram for libint2::DirectedGraph:
Collaboration graph
[legend]

Public Types

typedef DGVertex vertex
 
typedef DGArc arc
 
typedef SafePtr< DGVertexver_ptr
 
typedef SafePtr< DGArcarc_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< DGVertexappend_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
 

Detailed Description

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.

Note
The objects are allocated on free store and the graph is implemented as an object of type 'vertices'.

Constructor & Destructor Documentation

◆ DirectedGraph()

DirectedGraph::DirectedGraph ( )

Creates an empty DAG.

Actual initialization of the graph must be done using append_target

Member Function Documentation

◆ append_target()

template<class I , class RR >
void libint2::DirectedGraph::append_target ( const SafePtr< I > &  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.

◆ append_vertex()

SafePtr< DGVertex > DirectedGraph::append_vertex ( const SafePtr< DGVertex > &  v)

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().

◆ 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().

◆ apply_to_all()

template<class RR >
void libint2::DirectedGraph::apply_to_all ( )
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()

const SafePtr<DGVertex>& libint2::DirectedGraph::find ( const SafePtr< DGVertex > &  v) const
inline

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

◆ generate_code()

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().

◆ optimize_rr_out()

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.

◆ print_to_dot()

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.

◆ reset()

void DirectedGraph::reset ( )

Resets the graph and all vertices.

The stack of unresolved recurrence relations is preserved.

◆ traverse()

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.


The documentation for this class was generated from the following files: