A simple graph structure for graph-based operations. More...

#include <GraphUtils.h>

Collaboration diagram for souffle::Graph< Vertex, Compare >:

Public Member Functions
const std::set< Vertex, Compare >	clique (const Vertex &vertex) const
	Obtains the set of all vertices in the same clique than the given vertex. More...

bool	contains (const Vertex &from, const Vertex &to) const
	Determines whether the given edge is present. More...

bool	contains (const Vertex &vertex) const
	Determines whether the given vertex is present. More...

void	insert (const Vertex &from, const Vertex &to)
	Adds a new edge from the given vertex to the target vertex. More...

void	insert (const Vertex &vertex)
	Adds a vertex. More...

const std::set< Vertex, Compare > &	predecessors (const Vertex &to) const
	Returns the set of vertices the given vertex has edges from. More...

void	print (std::ostream &out) const
	Enables graphs to be printed (e.g. More...

bool	reaches (const Vertex &from, const Vertex &to) const
	Determines whether there is a directed path between the two vertices. More...

const std::set< Vertex, Compare > &	successors (const Vertex &from) const
	Returns the set of vertices the given vertex has edges to. More...

const std::set< Vertex, Compare > &	vertices () const
	Obtains a reference to the set of all vertices. More...

template<typename Lambda >
void	visitDepthFirst (const Vertex &vertex, const Lambda &lambda) const
	A generic utility for depth-first visits. More...

Private Member Functions
template<typename Lambda >
void	visitDepthFirst (const Vertex &vertex, const Lambda &lambda, std::set< Vertex, Compare > &visited) const
	The internal implementation of depth-first visits. More...

Private Attributes
std::map< Vertex, std::set< Vertex, Compare > >	_predecessors

std::map< Vertex, std::set< Vertex, Compare > >	_successors

std::set< Vertex, Compare >	_vertices

Friends
std::ostream &	operator<< (std::ostream &out, const Graph &g)

Detailed Description

template<typename Vertex, typename Compare = std::less<Vertex>>
class souffle::Graph< Vertex, Compare >

A simple graph structure for graph-based operations.

Definition at line 40 of file GraphUtils.h.

Member Function Documentation

◆ clique()

template<typename Vertex , typename Compare = std::less<Vertex>>

const std::set<Vertex, Compare> souffle::Graph< Vertex, Compare >::clique ( const Vertex & vertex ) const

inline

Obtains the set of all vertices in the same clique than the given vertex.

Definition at line 117 of file GraphUtils.h.

                                                                            {
         std::set<Vertex, Compare> visited;
         visitDepthFirst(vertex, lambda, visited);
     }
  
     /** Enables graphs to be printed (e.g. for debugging) */
     void print(std::ostream& out) const {
         bool first = true;
         out << "{";

◆ contains() [1/2]

template<typename Vertex , typename Compare = std::less<Vertex>>

bool souffle::Graph< Vertex, Compare >::contains	(	const Vertex &	from,
		const Vertex &	to
	)		const

inline

Determines whether the given edge is present.

Definition at line 90 of file GraphUtils.h.

                                               {
             return false;
         }
  
         // conduct a depth-first search starting at from
         bool found = false;
         bool first = true;
         visitDepthFirst(from, [&](const Vertex& cur) {

◆ contains() [2/2]

template<typename Vertex , typename Compare = std::less<Vertex>>

bool souffle::Graph< Vertex, Compare >::contains ( const Vertex & vertex ) const

inline

Determines whether the given vertex is present.

Definition at line 85 of file GraphUtils.h.

88 {

◆ insert() [1/2]

template<typename Vertex , typename Compare = std::less<Vertex>>

void souffle::Graph< Vertex, Compare >::insert	(	const Vertex &	from,
		const Vertex &	to
	)

inline

Adds a new edge from the given vertex to the target vertex.

Definition at line 51 of file GraphUtils.h.

                          {
             _successors.insert(std::make_pair(vertex, std::set<Vertex, Compare>()));
             _predecessors.insert(std::make_pair(vertex, std::set<Vertex, Compare>()));
         }
     }
  

◆ insert() [2/2]

template<typename Vertex , typename Compare = std::less<Vertex>>

void souffle::Graph< Vertex, Compare >::insert ( const Vertex & vertex )

inline

Adds a vertex.

Definition at line 61 of file GraphUtils.h.

                                                                         {
         return _successors.at(from);
     }
  
     /** Returns the set of vertices the given vertex has edges from */

◆ predecessors()

template<typename Vertex , typename Compare = std::less<Vertex>>

const std::set<Vertex, Compare>& souffle::Graph< Vertex, Compare >::predecessors ( const Vertex & to ) const

inline

Returns the set of vertices the given vertex has edges from.

Definition at line 80 of file GraphUtils.h.

                                       {
             return false;
         }

◆ print()

template<typename Vertex , typename Compare = std::less<Vertex>>

void souffle::Graph< Vertex, Compare >::print ( std::ostream & out ) const

inline

Enables graphs to be printed (e.g.

for debugging)

Definition at line 136 of file GraphUtils.h.

                                                                    {
         g.print(out);
         return out;
     }
  
 private:
     // not a very efficient but simple graph representation
     std::set<Vertex, Compare> _vertices;                        // all the vertices in the graph
     std::map<Vertex, std::set<Vertex, Compare>> _successors;    // all edges forward directed
     std::map<Vertex, std::set<Vertex, Compare>> _predecessors;  // all edges backward
  

◆ reaches()

template<typename Vertex , typename Compare = std::less<Vertex>>

bool souffle::Graph< Vertex, Compare >::reaches	(	const Vertex &	from,
		const Vertex &	to
	)		const

inline

Determines whether there is a directed path between the two vertices.

Definition at line 100 of file GraphUtils.h.

                                                                      {
         std::set<Vertex, Compare> res;
         res.insert(vertex);
         for (const auto& cur : vertices()) {
             if (reaches(vertex, cur) && reaches(cur, vertex)) {
                 res.insert(cur);
             }
         }
         return res;
     }

◆ successors()

template<typename Vertex , typename Compare = std::less<Vertex>>

const std::set<Vertex, Compare>& souffle::Graph< Vertex, Compare >::successors ( const Vertex & from ) const

inline

Returns the set of vertices the given vertex has edges to.

Definition at line 75 of file GraphUtils.h.

78 {

◆ vertices()

template<typename Vertex , typename Compare = std::less<Vertex>>

const std::set<Vertex, Compare>& souffle::Graph< Vertex, Compare >::vertices ( ) const

inline

Obtains a reference to the set of all vertices.

Definition at line 70 of file GraphUtils.h.

73 {

◆ visitDepthFirst() [1/2]

template<typename Vertex , typename Compare = std::less<Vertex>>

template<typename Lambda >

void souffle::Graph< Vertex, Compare >::visitDepthFirst	(	const Vertex &	vertex,
		const Lambda &	lambda
	)		const

inline

A generic utility for depth-first visits.

Definition at line 130 of file GraphUtils.h.

Referenced by souffle::Graph< const souffle::ast::Relation *, souffle::ast::NameComparison >::clique().

◆ visitDepthFirst() [2/2]

template<typename Vertex , typename Compare = std::less<Vertex>>

template<typename Lambda >

void souffle::Graph< Vertex, Compare >::visitDepthFirst	(	const Vertex &	vertex,
		const Lambda &	lambda,
		std::set< Vertex, Compare > &	visited
	)		const

inlineprivate

The internal implementation of depth-first visits.

Definition at line 164 of file GraphUtils.h.

                                                  {
     static const std::vector<char> table = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
             'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
             'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
             'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/'};
     std::string result;
     std::string tmp = data;
     unsigned int padding = 0;
     if (data.size() % 3 == 2) {
         padding = 1;

Friends And Related Function Documentation

◆ operator<<

template<typename Vertex , typename Compare = std::less<Vertex>>

std::ostream& operator<<	(	std::ostream &	out,
		const Graph< Vertex, Compare > &	g
	)

friend

Definition at line 151 of file GraphUtils.h.

153 {

154 lambda(vertex);

Field Documentation

◆ _predecessors

template<typename Vertex , typename Compare = std::less<Vertex>>

std::map<Vertex, std::set<Vertex, Compare> > souffle::Graph< Vertex, Compare >::_predecessors

private

Definition at line 160 of file GraphUtils.h.

Referenced by souffle::Graph< const souffle::ast::Relation *, souffle::ast::NameComparison >::insert().

◆ _successors

template<typename Vertex , typename Compare = std::less<Vertex>>

std::map<Vertex, std::set<Vertex, Compare> > souffle::Graph< Vertex, Compare >::_successors

private

Definition at line 159 of file GraphUtils.h.

Referenced by souffle::Graph< const souffle::ast::Relation *, souffle::ast::NameComparison >::insert().

◆ _vertices

template<typename Vertex , typename Compare = std::less<Vertex>>

std::set<Vertex, Compare> souffle::Graph< Vertex, Compare >::_vertices

private

Definition at line 158 of file GraphUtils.h.

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

GraphUtils.h

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

template<typename Vertex, typename Compare = std::less<Vertex>> class souffle::Graph< Vertex, Compare >

Member Function Documentation

◆ clique()

◆ contains() [1/2]

◆ contains() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ predecessors()

◆ print()

◆ reaches()

◆ successors()

◆ vertices()

◆ visitDepthFirst() [1/2]

◆ visitDepthFirst() [2/2]

Friends And Related Function Documentation

◆ operator<<

Field Documentation

◆ _predecessors

◆ _successors

◆ _vertices

template<typename Vertex, typename Compare = std::less<Vertex>>
class souffle::Graph< Vertex, Compare >