# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::DfsAcyclicSubgraph Class Reference

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

#include <ogdf/layered/DfsAcyclicSubgraph.h>

Inheritance diagram for ogdf::DfsAcyclicSubgraph:

## Public Member Functions

virtual void call (const Graph &G, List< edge > &arcSet) override
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.

Public Member Functions inherited from ogdf::AcyclicSubgraphModule
AcyclicSubgraphModule ()
Initializes an acyclic subgraph module.

virtual ~AcyclicSubgraphModule ()
Destruction.

void callAndDelete (Graph &G)
Makes G acyclic by removing edges.

void callAndReverse (Graph &G)
Makes G acyclic by reversing edges.

void callAndReverse (Graph &G, List< edge > &reversed)
Makes G acyclic by reversing edges.

void operator() (const Graph &G, List< edge > &arcSet)
Computes the set of edges arcSet which have to be removed for obtaining an acyclic subgraph of G.

## Private Member Functions

void dfsBackedgesHierarchies (const GraphAttributes &AG, node v, NodeArray< int > &number, NodeArray< int > &completion, int &nNumber, int &nCompletion)

int dfsFindHierarchies (const GraphAttributes &AG, NodeArray< int > &hierarchy, int i, node v)

## 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 43 of file DfsAcyclicSubgraph.h.

## ◆ call()

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

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

Implements ogdf::AcyclicSubgraphModule.

## ◆ callUML()

 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.

## ◆ dfsBackedgesHierarchies()

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

## ◆ dfsFindHierarchies()

 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: