#include <chi_directed_graph.h>

Data Structures
class	VertexAccessor

Public Member Functions
void	AddVertex (size_t id, void *context=nullptr)

void	AddVertex (void *context=nullptr)

void	RemoveVertex (size_t v)

bool	AddEdge (size_t from, size_t to, double weight=1.0)

void	RemoveEdge (size_t from, size_t to)

size_t	GetNumSinks ()

size_t	GetNumSources ()

std::vector< std::vector< size_t > >	FindStronglyConnectedComponents ()

std::vector< size_t >	GenerateTopologicalSort ()

std::vector< size_t >	FindApproxMinimumFAS ()

void	PrintGraphviz (int location_mask=0)

void	PrintSubGraphviz (const std::vector< int > &verts_to_print, int location_mask=0)

std::vector< std::pair< size_t, size_t > >	RemoveCyclicDependencies ()

void	Clear ()

	~DirectedGraph ()

Data Fields
VertexAccessor	vertices

Private Member Functions
void	DFSAlgorithm (std::vector< size_t > &traversal, std::vector< bool > &visited, size_t cur_vid)

void	SCCAlgorithm (size_t u, int &time, std::vector< int > &disc, std::vector< int > &low, std::vector< bool > &on_stack, std::stack< size_t > &stack, std::vector< std::vector< size_t > > &SCCs)

Detailed Description

Simple implementation of a directed graph. This implementation was considered to serve more versatile strategies with regards to grid parallel partitioning.

Definition at line 11 of file chi_directed_graph.h.

Constructor & Destructor Documentation

◆ ~DirectedGraph()

chi::DirectedGraph::~DirectedGraph ( )

Destructor.

Definition at line 577 of file chi_directed_graph.cc.

Member Function Documentation

◆ AddEdge()

bool chi::DirectedGraph::AddEdge	(	size_t	from,
		size_t	to,
		double	weight = `1.0`
	)

Adds an edge to the graph. Range checks are supplied by the vertex accessor.

Definition at line 106 of file chi_directed_graph.cc.

◆ AddVertex() [1/2]

void chi::DirectedGraph::AddVertex	(	size_t	id,
		void *	context = `nullptr`
	)

Adds a vertex to the graph. By default context is assumed to be nullptr.

Definition at line 78 of file chi_directed_graph.cc.

◆ AddVertex() [2/2]

void chi::DirectedGraph::AddVertex ( void * context = nullptr )

Adds a vertex to the graph. By default context is assumed to be nullptr and id is assumed to be assigned automatically. In the latter case the vertex id will be the same as the order in which it was added (0,1,2,3,etc ... will have id's 0,1,2,3,etc)

Definition at line 89 of file chi_directed_graph.cc.

◆ Clear()

void chi::DirectedGraph::Clear ( )

Clears all the data structures associated with the graph.

Definition at line 569 of file chi_directed_graph.cc.

◆ DFSAlgorithm()

void chi::DirectedGraph::DFSAlgorithm	(	std::vector< size_t > &	traversal,
		std::vector< bool > &	visited,
		size_t	cur_vid
	)

private

Depth-First-Search main recursive algorithm. This is the recursive portion of the method below this one (chi_graph::DirectedGraph::DepthFirstSearch).

Definition at line 131 of file chi_directed_graph.cc.

◆ FindApproxMinimumFAS()

std::vector< size_t > chi::DirectedGraph::FindApproxMinimumFAS ( )

Finds a sequence that minimizes the Feedback Arc Set (FAS). This algorithm implements the algorithm depicted in [1].

[1] Eades P., Lin X., Smyth W.F., "Fast & Effective heuristic for the feedback arc set problem", Information Processing Letters, Volume 47. 1993.

Definition at line 300 of file chi_directed_graph.cc.

◆ FindStronglyConnectedComponents()

std::vector< std::vector< size_t > > chi::DirectedGraph::FindStronglyConnectedComponents ( )

Find strongly connected components. This method is the implementation of Tarjan's algorithm [1].

[1] Tarjan R.E. "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1972.

It returns collections of vertices that form strongly connected components excluding singletons.

Definition at line 203 of file chi_directed_graph.cc.

◆ GenerateTopologicalSort()

std::vector< size_t > chi::DirectedGraph::GenerateTopologicalSort ( )

Generates a topological sort. This method is the implementation of Kahn's algorithm [1].

[1] Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM, 5 (11): 558–562

Returns: Returns the vertex ids sorted topologically. If this vector is empty the algorithm failed because it detected cyclic dependencies.

Definition at line 236 of file chi_directed_graph.cc.

◆ GetNumSinks()

size_t chi::DirectedGraph::GetNumSinks ( )

inline

Definition at line 118 of file chi_directed_graph.h.

◆ GetNumSources()

size_t chi::DirectedGraph::GetNumSources ( )

inline

Definition at line 127 of file chi_directed_graph.h.

◆ PrintGraphviz()

void chi::DirectedGraph::PrintGraphviz ( int location_mask = 0 )

Prints the graph in Graphviz format.

Definition at line 371 of file chi_directed_graph.cc.

◆ PrintSubGraphviz()

void chi::DirectedGraph::PrintSubGraphviz	(	const std::vector< int > &	verts_to_print,
		int	location_mask = `0`
	)

Prints a sub-graph in Graphviz format.

Definition at line 400 of file chi_directed_graph.cc.

◆ RemoveCyclicDependencies()

std::vector< std::pair< size_t, size_t > > chi::DirectedGraph::RemoveCyclicDependencies ( )

Definition at line 436 of file chi_directed_graph.cc.

◆ RemoveEdge()

void chi::DirectedGraph::RemoveEdge	(	size_t	from,
		size_t	to
	)

Remove an edge from the graph. Range checks are supplied by the vertex accessor.

Definition at line 121 of file chi_directed_graph.cc.

◆ RemoveVertex()

void chi::DirectedGraph::RemoveVertex ( size_t v )

Removes a vertex from the graph. This method does not free any context related data.

Definition at line 97 of file chi_directed_graph.cc.

◆ SCCAlgorithm()

void chi::DirectedGraph::SCCAlgorithm	(	size_t	u,
		int &	time,
		std::vector< int > &	disc,
		std::vector< int > &	low,
		std::vector< bool > &	on_stack,
		std::stack< size_t > &	stack,
		std::vector< std::vector< size_t > > &	SCCs
	)

private

SCC main recursive algorithm. This is the recursive call for the method defined below this one (chi_graph::DirectedGraph::FindStronglyConnectedConnections).

Definition at line 149 of file chi_directed_graph.cc.

Field Documentation

◆ vertices

VertexAccessor chi::DirectedGraph::vertices

Definition at line 110 of file chi_directed_graph.h.

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

framework/graphs/chi_directed_graph.h
framework/graphs/chi_directed_graph.cc

Data Structures

Public Member Functions

Data Fields

Private Member Functions