nom::algorithm::Tarjans< T, U > Class Template Reference

Tarjans algorithm implementation. More...

#include <TarjansImpl.h>

Public Member Functions
	Tarjans (Graph< T, U... > *g)
	Constructor wraps the input graph with an annotated graph set up with the datastructures needed for the algorithm. More...
void	connect (typename WrappedGraph::NodeRef n)
	Helper function for finding strongly connected components. More...
Subgraph< T, U... >	unwrapSubgraph (const WrappedSubgraph &wrappedSubgraph)
	Helper function for recovering a valid subgraph output. More...
std::vector< Subgraph< T, U... > >	run ()

Detailed Description

template<typename T, typename... U>
class nom::algorithm::Tarjans< T, U >

Tarjans algorithm implementation.

See details on how the algorithm works here: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

The algorithm works by annotating nodes, but we want to be able to handle generic graphs. Thus, we wrap the input graph with nodes that contain data composed of references to the original graph (for later recovery) and the data required for the algorithm (see NodeWrapper).

We then run the algorithm and return a reverse-topologically sorted vector of strongly connect components in the form of Subgraphs on the Graph.

Note

Head/Tail is used in reverse in Tarjan's early papers.

Bug:

Edges not included in returned subgraphs.

Definition at line 45 of file TarjansImpl.h.

Constructor & Destructor Documentation

template<typename T , typename... U>

nom::algorithm::Tarjans< T, U >::Tarjans ( Graph< T, U... > *  g )

inline

Constructor wraps the input graph with an annotated graph set up with the datastructures needed for the algorithm.

g The graph Tarjan's will be run on.

Definition at line 62 of file TarjansImpl.h.

Member Function Documentation

template<typename T , typename... U>

void nom::algorithm::Tarjans< T, U >::connect ( typename WrappedGraph::NodeRef  n )

inline

Helper function for finding strongly connected components.

n A reference to a node within the wrapped graph.

Definition at line 86 of file TarjansImpl.h.

template<typename T , typename... U>

Subgraph<T, U...> nom::algorithm::Tarjans< T, U >::unwrapSubgraph ( const WrappedSubgraph &  wrappedSubgraph )

inline

Helper function for recovering a valid subgraph output.

wrappedS A wrapped subgraph.

Returns

A subgraph of the original input graph.

Definition at line 139 of file TarjansImpl.h.

---

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

• caffe2/core/nomnigraph/include/nomnigraph/Graph/TarjansImpl.h