Référence de l'espace de nommage HypergraphLib

Classes
class	Arc
class	Graph
class	GraphObject
class	Node

Fonctions
void	FindSCC (Graph *__G, std::set< std::set< Node * > > &__components)
void HYPERGRAPHLIB_ITEM	dfs (Node *__n, std::set< Node * > &__depthFirstSearchNodes)
double HYPERGRAPHLIB_ITEM	Dijkstra (Graph *__G, Node *source, Node *destination, double(*distanceFunc)(HypergraphLib::Node *, HypergraphLib::Node *, HypergraphLib::Arc *), std::vector< Node * > &pathNodes, std::vector< Arc * > &pathArcs)
HYPERGRAPHLIB_ITEM void	Filaments (Graph *G, std::vector< std::vector< int > > &__filaments)
int	find_n (std::vector< Node * > &__depthFirstSearchNodes, Node *__n)
int	find_n (std::vector< Arc * > &__depthFirstSearchArcs, Arc *__a)
int	does_cycle_already_exist (const std::vector< std::vector< Node * > > &cycles, const std::vector< Node * > &cycle)
void	dfsCycle (Node *__n, std::vector< Node * > &__depthFirstSearchNodes, std::vector< Arc * > &__depthFirstSearchArcs, std::vector< std::vector< Node * > > &cycles)
void	FindCycles (Graph *__G, std::vector< std::vector< Node * > > &cycles)
HYPERGRAPHLIB_ITEM void	dfsCycle (Node *__n, std::vector< Node * > &__depthFirstSearchNodes, std::vector< std::vector< Node * > > &cycle)

Description détaillée

Find the strongly connected components of a graph http://en.wikipedia.org/wiki/Strongly_connected_component

STRONGLY-CONNECTED COMPONENTS (G) 1 call DFS(G) to compute finishing times f[u] for each vertex u 2 compute GT 3 call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u] 4 produce as output the vertices of each tree in the DFS forest formed in point 3 as a separate SCC.

Algorithme de d�composition d'un graphe en filaments

Documentation des fonctions

dfs()

HYPERGRAPHLIB_ITEM void HypergraphLib::dfs	(	Node *	__n,
		std::set< Node * > &	__depthFirstSearchNodes
	)

Depth First Search Algorithm : given one start node, find all nodes that are connected to it and return them

Définition à la ligne 31 du fichier hypergraphlib_dfs.cpp.

Références HypergraphLib::Node::AdjacentNodes().

Référencé par FindSCC().

Voici le graphe d'appel pour cette fonction :

Voici le graphe des appelants de cette fonction :

dfsCycle() [1/2]

void HypergraphLib::dfsCycle	(	Node *	__n,
		std::vector< Node * > &	__depthFirstSearchNodes,
		std::vector< Arc * > &	__depthFirstSearchArcs,
		std::vector< std::vector< Node * > > &	cycles
	)

Définition à la ligne 122 du fichier hypergraphlib_findcycles.cpp.

Références HypergraphLib::Node::AdjacentNodes(), does_cycle_already_exist(), find_n(), HypergraphLib::Node::IncidentArcs(), HypergraphLib::Graph::IsCycle(), HypergraphLib::Arc::Nodes(), et HypergraphLib::GraphObject::Owner().

Référencé par FindCycles().

Voici le graphe d'appel pour cette fonction :

Voici le graphe des appelants de cette fonction :

dfsCycle() [2/2]

HYPERGRAPHLIB_ITEM void HypergraphLib::dfsCycle	(	Node *	__n,
		std::vector< Node * > &	__depthFirstSearchNodes,
		std::vector< std::vector< Node * > > &	cycle
	)

Dijkstra()

double HypergraphLib::Dijkstra	(	Graph *	__G,
		Node *	source,
		Node *	destination,
		double(*)(HypergraphLib::Node *, HypergraphLib::Node *, HypergraphLib::Arc *)	distanceFunc,
		std::vector< Node * > &	pathNodes,
		std::vector< Arc * > &	pathArcs
	)

Définition à la ligne 41 du fichier hypergraphlib_dijkstra.cpp.

Références DJNode::d, djnode, HypergraphLib::Graph::GetNode(), HypergraphLib::Graph::GetNodes(), HypergraphLib::GraphObject::Id(), HypergraphLib::Node::IncidentArcs(), DJNode::n, DJNode::nbVisit, node, HypergraphLib::Arc::Nodes(), DJNode::prevArc, DJNode::previous, et HypergraphLib::GraphObject::SetUserData().

Référencé par CAD4FE::ShortestPath::Find(), et CAD4FE::MCAA::NodeConstrictedSection().

Voici le graphe d'appel pour cette fonction :

Voici le graphe des appelants de cette fonction :

does_cycle_already_exist()

int HypergraphLib::does_cycle_already_exist	(	const std::vector< std::vector< Node * > > &	cycles,
		const std::vector< Node * > &	cycle
	)

returns : -2 if the cycle does not exist -1 if the cycle exist j if the cycle at index j is longer than the new one

Définition à la ligne 58 du fichier hypergraphlib_findcycles.cpp.

Référencé par dfsCycle().

Voici le graphe des appelants de cette fonction :

Filaments()

void HYPERGRAPHLIB_ITEM HypergraphLib::Filaments	(	Graph *	G,
		std::vector< std::vector< int > > &	__filaments
	)

Définition à la ligne 41 du fichier hypergraphlib_filaments.cpp.

Références HypergraphLib::Node::AdjacentNodes(), HypergraphLib::Graph::GetNode(), HypergraphLib::Graph::GetNodes(), HypergraphLib::GraphObject::Id(), HypergraphLib::Node::IncidentArcs(), HypergraphLib::Node::IsAdjacentToNode(), et HypergraphLib::Arc::Nodes().

Voici le graphe d'appel pour cette fonction :

find_n() [1/2]

int HypergraphLib::find_n	(	std::vector< Arc * > &	__depthFirstSearchArcs,
		Arc *	__a
	)

Définition à la ligne 43 du fichier hypergraphlib_findcycles.cpp.

find_n() [2/2]

int HypergraphLib::find_n	(	std::vector< Node * > &	__depthFirstSearchNodes,
		Node *	__n
	)

Définition à la ligne 35 du fichier hypergraphlib_findcycles.cpp.

Référencé par dfsCycle().

Voici le graphe des appelants de cette fonction :

FindCycles()

HYPERGRAPHLIB_ITEM void HypergraphLib::FindCycles	(	Graph *	__G,
		std::vector< std::vector< Node * > > &	cycles
	)

Définition à la ligne 173 du fichier hypergraphlib_findcycles.cpp.

Références dfsCycle(), et GRAPH_FOR_EACH_NODE_CONST.

Référencé par CAD4FE::MCBody::Face_GetCycles().

Voici le graphe d'appel pour cette fonction :

Voici le graphe des appelants de cette fonction :

FindSCC()

HYPERGRAPHLIB_ITEM void HypergraphLib::FindSCC	(	Graph *	__G,
		std::set< std::set< Node * > > &	__components
	)

Définition à la ligne 43 du fichier hypergraphlib_components.cpp.

Références dfs(), et HypergraphLib::Graph::GetNodes().

Référencé par CAD4FE::MCBody::Face_GetUnsortedLoops().

Voici le graphe d'appel pour cette fonction :

Voici le graphe des appelants de cette fonction :