Arcane  v4.1.0.0
Documentation utilisateur
Chargement...
Recherche...
Aucune correspondance
Classes | Types publics | Fonctions membres publiques | Liste de tous les membres
Référence du modèle de la classe Arcane::DirectedAcyclicGraphT< VertexType, EdgeType >

#include <arcane/utils/DirectedAcyclicGraphT.h>

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)
 

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.

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

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.

Références Arcane::GraphBaseT< VertexType, EdgeType >::GraphBaseT().

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

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

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