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

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

Voici le graphe d'appel pour cette fonction :

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

DirectedAcyclicGraphT.h

Classes

Types publics

Fonctions membres publiques

Types privés

Fonctions membres privées

Attributs privés

Membres hérités additionnels

Description détaillée

Documentation des définitions de type membres

◆ Base

◆ EdgeLevelMap

◆ EdgeRef

◆ SortedEdgeSet

◆ SortedVertexSet

◆ VertexLevelMap

◆ VertexLevelSet

◆ VertexRef

Documentation des constructeurs et destructeur

◆ DirectedAcyclicGraphT()

◆ ~DirectedAcyclicGraphT()

Documentation des fonctions membres

◆ _computeEdgeLevel()

◆ _computeVertexLevel()

◆ _computeVertexLevels()

◆ _printGraphEntry()

◆ addEdge() [1/2]

◆ addEdge() [2/2]

◆ hasCycle()

◆ print()

◆ spanningTree()

◆ topologicalSort()

Documentation des données membres

◆ m_colored_vertices

◆ m_compute_vertex_levels

◆ m_edge_level_map

◆ m_vertex_level_map