Arcane  4.1.12.0
User documentation
Loading...
Searching...
No Matches
Arcane::DirectedAcyclicGraphT< VertexType, EdgeType > Class Template Reference

#include <arcane/utils/DirectedAcyclicGraphT.h>

Classes

class  SortedElementSet

Public Types

typedef GraphBaseT< VertexType, EdgeType > Base
typedef SortedElementSet< typename Base::EdgeTypeRefArray > SortedEdgeSet
typedef SortedElementSet< typename Base::VertexTypeRefArray > SortedVertexSet
typedef std::map< typename Base::VertexTypeConstRef, Integer > VertexLevelMap
typedef std::map< typename Base::EdgeTypeConstRef, Integer > EdgeLevelMap
typedef std::set< std::pair< VertexType, Integer >, std::function< bool(std::pair< VertexType, Integer >, std::pair< VertexType, Integer >)> > VertexLevelSet
Public Types inherited from Arcane::GraphBaseT< VertexType, EdgeType >
typedef std::reference_wrapper< VertexType > VertexTypeRef
typedef std::reference_wrapper< const VertexType > VertexTypeConstRef
typedef std::reference_wrapper< EdgeType > EdgeTypeRef
typedef std::reference_wrapper< const EdgeType > EdgeTypeConstRef
typedef std::list< VertexType > VertexList
typedef std::list< EdgeType > EdgeList
typedef SharedArray< VertexTypeRef > VertexTypeRefArray
typedef SharedArray< VertexTypeConstRef > VertexTypeConstRefArray
typedef SharedArray< EdgeTypeRef > EdgeTypeRefArray
typedef SharedArray< EdgeTypeConstRef > EdgeTypeConstRefArray
typedef std::map< VertexTypeConstRef, std::pair< VertexTypeRefArray, EdgeTypeRefArray > > AdjacencyListType
typedef std::pair< VertexTypeRef, VertexTypeRef > VertexPair
typedef std::map< EdgeTypeConstRef, VertexPair > EdgeToVertexMap
typedef IterableEnsembleT< VertexList > VertexSet
typedef IterableEnsembleT< EdgeList > EdgeSet
typedef IterableEnsembleT< EdgeTypeRefArray > ConnectedEdgeSet
typedef VertexType VertexRef
typedef EdgeType EdgeRef

Public Member Functions

 DirectedAcyclicGraphT (ITraceMng *trace_mng)
virtual ~DirectedAcyclicGraphT ()
void addEdge (const VertexType &source_vertex, const VertexType &target_vertex, const EdgeType &source_to_target_edge)
void addEdge (VertexType &&source_vertex, VertexType &&target_vertex, EdgeType &&source_to_target_edge)
SortedVertexSet topologicalSort ()
SortedEdgeSet spanningTree ()
void print ()
bool hasCycle ()
Public Member Functions inherited from Arcane::GraphBaseT< VertexType, EdgeType >
void addEdge (const VertexType &source_vertex, const VertexType &target_vertex, const EdgeType &source_to_target_edge)
 Multiple edges (consisting of the same source and target nodes) are not allowed (throws FatalErrorException).
void addEdge (VertexType &&source_vertex, VertexType &&target_vertex, EdgeType &&source_to_target_edge)
template<class Vertex, class Edge>
void _addEdge (Vertex source_vertex, Vertex target_vertex, Edge source_to_target_edge)
EdgeType * getEdge (const VertexType &source_vertex, const VertexType &target_vertex)
 Returns a pointer to the EdgeType instance stored in the graph or nullptr if not found.
const EdgeType * getEdge (const VertexType &source_vertex, const VertexType &target_vertex) const
 Returns a pointer to the EdgeType instance stored in the graph or nullptr if not found.
EdgeType * _getEdge (const VertexType &source_vertex, const VertexType &target_vertex)
VertexType * getSourceVertex (const EdgeType &edge)
const VertexType * getSourceVertex (const EdgeType &edge) const
VertexType * getTargetVertex (const EdgeType &edge)
const VertexType * getTargetVertex (const EdgeType &edge) const
VertexSet vertices ()
EdgeSet edges ()
ConnectedEdgeSet inEdges (const VertexType &vertex)
ConnectedEdgeSet outEdges (const VertexType &vertex)

Additional Inherited Members

Protected Member Functions inherited from Arcane::GraphBaseT< VertexType, EdgeType >
 GraphBaseT (ITraceMng *trace_mng)
virtual ~GraphBaseT ()
Protected Attributes inherited from Arcane::GraphBaseT< VertexType, EdgeType >
ITraceMng * m_trace_mng
VertexList m_vertices
EdgeList m_edges
AdjacencyListType m_adjacency_list
AdjacencyListType m_adjacency_list_transposed
 source_vertex -> target_vertices
EdgeToVertexMap m_edge_to_vertex_map
 target_vertex -> source_vertices

Detailed Description

template<class VertexType, class EdgeType>
class Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >

Template class for DirectedAcyclicGraph. VertexType must implement a less comparison operator.

Definition at line 38 of file DirectedAcyclicGraphT.h.

Member Typedef Documentation

◆ Base

template<class VertexType, class EdgeType>
typedef GraphBaseT<VertexType, EdgeType> Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::Base

Definition at line 125 of file DirectedAcyclicGraphT.h.

◆ EdgeLevelMap

template<class VertexType, class EdgeType>
typedef std::map<typename Base::EdgeTypeConstRef, Integer> Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::EdgeLevelMap

Definition at line 129 of file DirectedAcyclicGraphT.h.

◆ SortedEdgeSet

template<class VertexType, class EdgeType>
typedef SortedElementSet<typename Base::EdgeTypeRefArray> Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::SortedEdgeSet

Definition at line 126 of file DirectedAcyclicGraphT.h.

◆ SortedVertexSet

template<class VertexType, class EdgeType>
typedef SortedElementSet<typename Base::VertexTypeRefArray> Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::SortedVertexSet

Definition at line 127 of file DirectedAcyclicGraphT.h.

◆ VertexLevelMap

template<class VertexType, class EdgeType>
typedef std::map<typename Base::VertexTypeConstRef, Integer> Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::VertexLevelMap

Definition at line 128 of file DirectedAcyclicGraphT.h.

◆ VertexLevelSet

template<class VertexType, class EdgeType>
typedef std::set<std::pair<VertexType, Integer>, std::function<bool(std::pair<VertexType, Integer>, std::pair<VertexType, Integer>)> > Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::VertexLevelSet

Definition at line 130 of file DirectedAcyclicGraphT.h.

Constructor & Destructor Documentation

◆ DirectedAcyclicGraphT()

template<class VertexType, class EdgeType>
Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::DirectedAcyclicGraphT ( ITraceMng * trace_mng)
inline

Constructor of the class

Definition at line 47 of file DirectedAcyclicGraphT.h.

References Arcane::GraphBaseT< VertexType, EdgeType >::GraphBaseT().

◆ ~DirectedAcyclicGraphT()

template<class VertexType, class EdgeType>
virtual Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::~DirectedAcyclicGraphT ( )
inlinevirtual

Destructor of the class

Definition at line 53 of file DirectedAcyclicGraphT.h.

Member Function Documentation

◆ addEdge() [1/2]

template<class VertexType, class EdgeType>
void Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::addEdge ( const VertexType & source_vertex,
const VertexType & target_vertex,
const EdgeType & source_to_target_edge )
inline

Definition at line 132 of file DirectedAcyclicGraphT.h.

◆ addEdge() [2/2]

template<class VertexType, class EdgeType>
void Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::addEdge ( VertexType && source_vertex,
VertexType && target_vertex,
EdgeType && source_to_target_edge )
inline

Definition at line 138 of file DirectedAcyclicGraphT.h.

◆ hasCycle()

template<class VertexType, class EdgeType>
bool Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::hasCycle ( )
inline

Cycle detection is done using a lazy pattern which is only triggered when calling topologicalSort() and print(). This method allows knowing if the graph contains a cycle (which would cause topologicalSort() to fail).

Definition at line 190 of file DirectedAcyclicGraphT.h.

◆ print()

template<class VertexType, class EdgeType>
void Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::print ( )
inline

Definition at line 172 of file DirectedAcyclicGraphT.h.

◆ spanningTree()

template<class VertexType, class EdgeType>
SortedEdgeSet Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::spanningTree ( )
inline

Definition at line 156 of file DirectedAcyclicGraphT.h.

◆ topologicalSort()

template<class VertexType, class EdgeType>
SortedVertexSet Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::topologicalSort ( )
inline

Definition at line 144 of file DirectedAcyclicGraphT.h.

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