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

#include <arcane/utils/DirectedAcyclicGraphT.h>

Inheritance diagram for Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >:
Collaboration diagram for Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >:

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)

Private Types

typedef VertexType & VertexRef
typedef EdgeType & EdgeRef

Private Member Functions

void _computeVertexLevels ()
void _computeVertexLevel (const VertexType &vertex, Integer level)
Integer _computeEdgeLevel (const EdgeType &edge)
void _printGraphEntry (const typename Base::AdjacencyListType::value_type &vertex_entry)

Private Attributes

std::set< typename Base::VertexTypeConstRef > m_colored_vertices
VertexLevelMap m_vertex_level_map
EdgeLevelMap m_edge_level_map
bool m_compute_vertex_levels

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.

◆ EdgeRef

template<class VertexType, class EdgeType>
typedef EdgeType& Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::EdgeRef
private

Definition at line 42 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.

◆ VertexRef

template<class VertexType, class EdgeType>
typedef VertexType& Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::VertexRef
private

Definition at line 41 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().

Here is the call graph for this function:

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

◆ _computeEdgeLevel()

template<class VertexType, class EdgeType>
Integer Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::_computeEdgeLevel ( const EdgeType & edge)
inlineprivate

Definition at line 249 of file DirectedAcyclicGraphT.h.

◆ _computeVertexLevel()

template<class VertexType, class EdgeType>
void Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::_computeVertexLevel ( const VertexType & vertex,
Integer level )
inlineprivate

Definition at line 221 of file DirectedAcyclicGraphT.h.

◆ _computeVertexLevels()

template<class VertexType, class EdgeType>
void Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::_computeVertexLevels ( )
inlineprivate

Definition at line 211 of file DirectedAcyclicGraphT.h.

◆ _printGraphEntry()

template<class VertexType, class EdgeType>
void Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::_printGraphEntry ( const typename Base::AdjacencyListType::value_type & vertex_entry)
inlineprivate

Definition at line 263 of file DirectedAcyclicGraphT.h.

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

Member Data Documentation

◆ m_colored_vertices

template<class VertexType, class EdgeType>
std::set<typename Base::VertexTypeConstRef> Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::m_colored_vertices
private

Definition at line 204 of file DirectedAcyclicGraphT.h.

◆ m_compute_vertex_levels

template<class VertexType, class EdgeType>
bool Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::m_compute_vertex_levels
private

Definition at line 207 of file DirectedAcyclicGraphT.h.

◆ m_edge_level_map

template<class VertexType, class EdgeType>
EdgeLevelMap Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::m_edge_level_map
private

Definition at line 206 of file DirectedAcyclicGraphT.h.

◆ m_vertex_level_map

template<class VertexType, class EdgeType>
VertexLevelMap Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >::m_vertex_level_map
private

Definition at line 205 of file DirectedAcyclicGraphT.h.

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