Arcane  v3.14.10.0
Documentation développeur
Chargement...
Recherche...
Aucune correspondance
Classes | Types publics | Fonctions membres publiques | Types privés | Fonctions membres privées | Attributs privés | Liste de tous les membres
Référence du modèle de la classe Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >

#include <arcane/utils/DirectedAcyclicGraphT.h>

+ Graphe d'héritage de Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >:
+ Graphe de collaboration de Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >:

Classes

class  SortedElementSet
 

Types publics

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
 
- Types publics hérités de 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
 

Fonctions membres publiques

 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 ()
 
- Fonctions membres publiques hérités de Arcane::GraphBaseT< VertexType, EdgeType >
void addEdge (const VertexType &source_vertex, const VertexType &target_vertex, const EdgeType &source_to_target_edge)
 Les arêtes multiples (constituées des mêmes noeuds source et target) ne sont pas autorisées (throw 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)
 Renvoie un pointeur vers l'instance d'EdgeType stockée dans le graphe ou nullptr si non trouvé.
 
const EdgeType * getEdge (const VertexType &source_vertex, const VertexType &target_vertex) const
 Renvoie un pointeur vers l'instance d'EdgeType stockée dans le graphe ou nullptr si non trouvé.
 
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)
 

Types privés

typedef VertexType & VertexRef
 
typedef EdgeType & EdgeRef
 

Fonctions membres privées

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

Attributs privés

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

Membres hérités additionnels

- Fonctions membres protégées hérités de Arcane::GraphBaseT< VertexType, EdgeType >
 GraphBaseT (ITraceMng *trace_mng)
 
virtual ~GraphBaseT ()
 
- Attributs protégés hérités de 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
 

Description détaillée

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

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

Définition à la ligne 38 du fichier DirectedAcyclicGraphT.h.

Documentation des définitions de type membres

◆ Base

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

Définition à la ligne 108 du fichier DirectedAcyclicGraphT.h.

◆ EdgeLevelMap

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

Définition à la ligne 112 du fichier DirectedAcyclicGraphT.h.

◆ EdgeRef

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

Définition à la ligne 42 du fichier DirectedAcyclicGraphT.h.

◆ SortedEdgeSet

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

Définition à la ligne 109 du fichier DirectedAcyclicGraphT.h.

◆ SortedVertexSet

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

Définition à la ligne 110 du fichier DirectedAcyclicGraphT.h.

◆ VertexLevelMap

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

Définition à la ligne 111 du fichier 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

Définition à la ligne 113 du fichier DirectedAcyclicGraphT.h.

◆ VertexRef

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

Définition à la ligne 41 du fichier DirectedAcyclicGraphT.h.

Documentation des constructeurs et destructeur

◆ DirectedAcyclicGraphT()

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

Constructeur de la classe

Définition à la ligne 46 du fichier DirectedAcyclicGraphT.h.

◆ ~DirectedAcyclicGraphT()

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

Destructeur de la classe

Définition à la ligne 51 du fichier DirectedAcyclicGraphT.h.

Documentation des fonctions membres

◆ _computeEdgeLevel()

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

Définition à la ligne 226 du fichier DirectedAcyclicGraphT.h.

◆ _computeVertexLevel()

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

Définition à la ligne 199 du fichier DirectedAcyclicGraphT.h.

◆ _computeVertexLevels()

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

Définition à la ligne 189 du fichier DirectedAcyclicGraphT.h.

◆ _printGraphEntry()

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

Définition à la ligne 238 du fichier 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

Définition à la ligne 115 du fichier 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

Définition à la ligne 121 du fichier DirectedAcyclicGraphT.h.

◆ hasCycle()

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

La detection de cycle se fait avec un pattern lazy qui n'est lancé que lors de l'appel à topologicalSort() et print(). Cette méthode permet de savoir si le graphe contient un cycle (ce qui produirait l'échec de topologicalSort())

Définition à la ligne 170 du fichier DirectedAcyclicGraphT.h.

◆ print()

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

Définition à la ligne 153 du fichier DirectedAcyclicGraphT.h.

◆ spanningTree()

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

Définition à la ligne 137 du fichier DirectedAcyclicGraphT.h.

◆ topologicalSort()

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

Définition à la ligne 127 du fichier DirectedAcyclicGraphT.h.

Documentation des données membres

◆ m_colored_vertices

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

Définition à la ligne 182 du fichier DirectedAcyclicGraphT.h.

◆ m_compute_vertex_levels

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

Définition à la ligne 185 du fichier DirectedAcyclicGraphT.h.

◆ m_edge_level_map

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

Définition à la ligne 184 du fichier DirectedAcyclicGraphT.h.

◆ m_vertex_level_map

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

Définition à la ligne 183 du fichier DirectedAcyclicGraphT.h.

La documentation de cette classe a été générée à partir du fichier suivant :