Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

ogdf::DfsAcyclicSubgraph Class Reference

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

#include <DfsAcyclicSubgraph.h>

Inheritance diagram for ogdf::DfsAcyclicSubgraph:

List of all members.

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.

Implements ogdf::AcyclicSubgraphModule.

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.

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

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

---

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

• ogdf/layered/DfsAcyclicSubgraph.h

---