Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. More...
 
void callUML (const GraphAttributes &AG, List< edge > &arcSet)
 Call for UML graph. More...
 
- Public Member Functions inherited from ogdf::AcyclicSubgraphModule
 AcyclicSubgraphModule ()
 Initializes an acyclic subgraph module. More...
 
virtual ~AcyclicSubgraphModule ()
 Destruction. More...
 
void callAndDelete (Graph &G)
 Makes G acyclic by removing edges. More...
 
void callAndReverse (Graph &G)
 Makes G acyclic by reversing edges. More...
 
void callAndReverse (Graph &G, List< edge > &reversed)
 Makes G acyclic by reversing edges. More...
 
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. More...
 

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.

Member Function Documentation

◆ 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: