sdfg::graph Namespace Reference

Classes
struct	DFSVisitor

Typedefs
typedef boost::adjacency_list< boost::listS, boost::listS, boost::bidirectionalS >	Graph
typedef boost::graph_traits< Graph >::vertex_descriptor	Vertex
typedef boost::graph_traits< Graph >::edge_descriptor	Edge
typedef boost::adjacency_list< boost::listS, boost::listS, boost::undirectedS >	UndirectedGraph
typedef boost::graph_traits< UndirectedGraph >::edge_descriptor	UndirectedEdge
typedef boost::reverse_graph< Graph >	ReverseGraph
typedef boost::graph_traits< ReverseGraph >::edge_descriptor	ReverseEdge
typedef std::unordered_map< Vertex, size_t >	IndexMap

Functions
const ReverseGraph	reverse (const Graph &graph)
const std::tuple< std::unique_ptr< const UndirectedGraph >, const std::unordered_map< Vertex, Vertex >, const std::unordered_map< Vertex, Vertex > >	undirected (const Graph &graph)
const std::list< Vertex >	depth_first_search (const Graph &graph, const graph::Vertex start)
std::pair< int, std::unordered_map< Vertex, size_t > >	strongly_connected_components (const Graph &graph)
std::pair< size_t, const std::unordered_map< Vertex, size_t > >	weakly_connected_components (const Graph &graph)
const std::unordered_map< Vertex, Vertex >	dominator_tree (const Graph &graph, const Vertex src)
const std::unordered_map< Vertex, Vertex >	post_dominator_tree (Graph &graph)
const std::list< graph::Vertex >	topological_sort (const Graph &graph)
bool	is_acyclic (const Graph &graph)
const std::list< Edge >	back_edges (const Graph &graph, const graph::Vertex start)
void	all_simple_paths_dfs (const Graph &graph, const Edge edge, const Vertex v, std::list< std::list< Edge > > &all_paths, std::list< Edge > &current_path, std::set< Vertex > &visited)
const std::list< std::list< Edge > >	all_simple_paths (const Graph &graph, const Vertex src, const Vertex dst)

Typedef Documentation

Edge

typedef boost::graph_traits<Graph>::edge_descriptor sdfg::graph::Edge

Graph

typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS> sdfg::graph::Graph

IndexMap

typedef std::unordered_map<Vertex, size_t> sdfg::graph::IndexMap

ReverseEdge

typedef boost::graph_traits<ReverseGraph>::edge_descriptor sdfg::graph::ReverseEdge

ReverseGraph

typedef boost::reverse_graph<Graph> sdfg::graph::ReverseGraph

UndirectedEdge

typedef boost::graph_traits<UndirectedGraph>::edge_descriptor sdfg::graph::UndirectedEdge

UndirectedGraph

typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS> sdfg::graph::UndirectedGraph

Vertex

typedef boost::graph_traits<Graph>::vertex_descriptor sdfg::graph::Vertex

Function Documentation

all_simple_paths()

const std::list< std::list< Edge > > sdfg::graph::all_simple_paths	(	const Graph &	graph,
		const Vertex	src,
		const Vertex	dst )

all_simple_paths_dfs()

void sdfg::graph::all_simple_paths_dfs	(	const Graph &	graph,
		const Edge	edge,
		const Vertex	v,
		std::list< std::list< Edge > > &	all_paths,
		std::list< Edge > &	current_path,
		std::set< Vertex > &	visited )

back_edges()

const std::list< Edge > sdfg::graph::back_edges	(	const Graph &	graph,
		const graph::Vertex	start )

depth_first_search()

const std::list< Vertex > sdfg::graph::depth_first_search	(	const Graph &	graph,
		const graph::Vertex	start )

dominator_tree()

const std::unordered_map< Vertex, Vertex > sdfg::graph::dominator_tree	(	const Graph &	graph,
		const Vertex	src )

is_acyclic()

bool sdfg::graph::is_acyclic

(

const Graph &

graph

)

post_dominator_tree()

const std::unordered_map< Vertex, Vertex > sdfg::graph::post_dominator_tree

(

Graph &

graph

)

reverse()

const ReverseGraph sdfg::graph::reverse

(

const Graph &

graph

)

strongly_connected_components()

std::pair< int, std::unordered_map< Vertex, size_t > > sdfg::graph::strongly_connected_components

(

const Graph &

graph

)

topological_sort()

const std::list< graph::Vertex > sdfg::graph::topological_sort

(

const Graph &

graph

)

undirected()

const std::tuple< std::unique_ptr< const UndirectedGraph >, const std::unordered_map< Vertex, Vertex >, const std::unordered_map< Vertex, Vertex > > sdfg::graph::undirected

(

const Graph &

graph

)

weakly_connected_components()

std::pair< size_t, const std::unordered_map< Vertex, size_t > > sdfg::graph::weakly_connected_components

(

const Graph &

graph

)