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

#include <dg.h>

Inheritance diagram for libint2::DirectedGraph:

Collaboration diagram for libint2::DirectedGraph:

Public Types
typedef DGVertex	vertex

typedef DGArc	arc

typedef std::shared_ptr< DGVertex >	ver_ptr

typedef std::shared_ptr< 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.

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 std::shared_ptr< DGVertex > &	find (const std::shared_ptr< DGVertex > &v) const
	Find vertex v or it's equivalent on the graph.

std::shared_ptr< DGVertex >	append_vertex (const std::shared_ptr< DGVertex > &v)
	appends v to the graph.

void	append_target (const std::shared_ptr< DGVertex > &)
	non-template append_target appends the vertex to the graph as a target

template<class I , class RR >
void	append_target (const std::shared_ptr< I > &target)
	append_target appends I to the graph as a target vertex and applies RR to it.

template<class RR >
void	apply_to_all ()
	apply_to_all applies RR to all vertices already on the graph.

void	apply (const std::shared_ptr< Strategy > &strategy, const std::shared_ptr< Tactic > &tactic)
	after all append_target's have been called, apply(strategy,tactic) constructs a graph.

template<DGVertexMethodPtr method>
void	apply_at (const std::shared_ptr< 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 std::shared_ptr< CodeContext > &context)
	after Strategy has been applied, simple recurrence relations need to be optimized away.

void	traverse ()
	after all apply's have been called, traverse() construct a heuristic order of traversal for the graph.

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".

void	generate_code (const std::shared_ptr< CodeContext > &context, const std::shared_ptr< MemoryManager > &memman, const std::shared_ptr< ImplicitDimensions > &dims, const std::shared_ptr< CodeSymbols > &args, const std::string &label, std::ostream &decl, std::ostream &code)
	Generates code for the current computation using context.

void	reset ()
	Resets the graph and all vertices.

template<class RR >
unsigned int	num_children_on (const std::shared_ptr< RR > &rr) const
	num_children_on(rr) returns the number of children of rr which are already on this graph.

std::shared_ptr< GraphRegistry > &	registry ()
	Returns the registry.

const std::shared_ptr< 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 std::shared_ptr< 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()

std::shared_ptr< DGVertex > DirectedGraph::append_vertex ( const std::shared_ptr< 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 std::shared_ptr< Strategy > &	strategy,
		const std::shared_ptr< 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.

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.

which do not have exit arcs)

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 std::shared_ptr< DGVertex > & libint2::DirectedGraph::find ( const std::shared_ptr< 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 std::shared_ptr< CodeContext > &	context,
		const std::shared_ptr< MemoryManager > &	memman,
		const std::shared_ptr< ImplicitDimensions > &	dims,
		const std::shared_ptr< 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::Entity::id(), 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 std::shared_ptr< 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:

dg.h
dg.cc

Public Types

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ DirectedGraph()

Member Function Documentation

◆ append_target()

◆ append_vertex()

◆ apply()

◆ apply_to_all()

◆ find()

◆ generate_code()

◆ optimize_rr_out()

◆ print_to_dot()

◆ reset()

◆ traverse()