DFS-based algorithm for computing a maximal acyclic subgraph. More...

Inheritance diagram for ogdf::DfsAcyclicSubgraph:

Public Member Functions
void	call (const Graph &G, List< edge > &arcSet)
	Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph.
void	callUML (const GraphAttributes &AG, List< edge > &arcSet)
	Call for UML graph.
Private Member Functions
int	dfsFindHierarchies (const GraphAttributes &AG, NodeArray< int > &hierarchy, int i, node v)
void	dfsBackedgesHierarchies (const GraphAttributes &AG, node v, NodeArray< int > &number, NodeArray< int > &completion, int &nNumber, int &nCompletion)

Detailed Description

DFS-based algorithm for computing a maximal acyclic subgraph.

The algorithm simply removes all DFS-backedges and works in linear-time.

Definition at line 72 of file DfsAcyclicSubgraph.h.

Member Function Documentation

void ogdf::DfsAcyclicSubgraph::call	(	const Graph &	G,
		List< edge > &	arcSet
	)			`[virtual]`

Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph.

void ogdf::DfsAcyclicSubgraph::callUML	(	const GraphAttributes &	AG,
		List< edge > &	arcSet
	)

Call for UML graph.

Computes the set of edges arcSet, which have to be deleted in the acyclic subgraph.

void ogdf::DfsAcyclicSubgraph::dfsBackedgesHierarchies	(	const GraphAttributes &	AG,
		node	v,
		NodeArray< int > &	number,
		NodeArray< int > &	completion,
		int &	nNumber,
		int &	nCompletion
	)			`[private]`

int ogdf::DfsAcyclicSubgraph::dfsFindHierarchies	(	const GraphAttributes &	AG,
		NodeArray< int > &	hierarchy,
		int	i,
		node	v
	)			`[private]`

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