outil/src/hypergraphlib_graph.h

//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//  MAGiC
//####//  Jean Christophe Cuilliere et Vincent FRANCOIS
//####//  Departement de Genie Mecanique - UQTR
//####//------------------------------------------------------------
//####//  MAGIC est un projet de recherche de l equipe ERICCA
//####//  du departement de genie mecanique de l Universite du Quebec a Trois Rivieres
//####//  http://www.uqtr.ca/ericca
//####//  http://www.uqtr.ca/
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//
//####//       hypergraphlib_graph.h
//####//
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//    COPYRIGHT 2000-2024
//####//  jeu 13 jun 2024 11:54:00 EDT
//####//------------------------------------------------------------
//####//------------------------------------------------------------
#ifndef GRAPHH
#define GRAPHH

#include <map>
#include <set>
#include <vector>

#include "hypergraphlib_graphobject.h"

#define GRAPH_FOR_EACH_ARC_CONST(G,A)                            \
    for (HypergraphLib::Graph::MapArcsById::const_iterator A = G->GetArcs().begin();    \
         A != G->GetArcs().end();                          \
         A++)

#define GRAPH_FOR_EACH_ARC(G,A)                            \
    for (HypergraphLib::Graph::MapArcsById::iterator A = G->GetArcs().begin();    \
         A != G->GetArcs().end();                          \
         A++)

#define GRAPH_FOR_EACH_NODE_CONST(G,N)                \
    for (HypergraphLib::Graph::MapNodesById::const_iterator N = G->GetNodes().begin();    \
         N != G->GetNodes().end();                          \
         N++)

#define GRAPH_FOR_EACH_NODE(G,N)                \
    for (HypergraphLib::Graph::MapNodesById::iterator N = G->GetNodes().begin();    \
         N != G->GetNodes().end();                          \
         N++)


namespace HypergraphLib {

class Node;
class Arc;

class HYPERGRAPHLIB_ITEM Graph : public GraphObject {
public:
    typedef std::map < int, Arc * > MapArcsById;
    typedef std::map < int, Node * > MapNodesById;

    ~Graph();

    /**
     * Constructor
     */
    Graph(int __id=0);

    /**
     * copy constructor
     */
    Graph(const Graph &__G, int __clone=1, int __reverse=0);

    /**
     * subgraph constructor
     */
    Graph(const Graph &__G, const std::set  <Node *> & );
    Graph(const Graph &__G, const std::vector <Node*> & __nodes);

    /**
     * Get one node by ID
     */
    Node * GetNode (int) const;


    /**
     * Merge two nodes
     * if __keepNodes = true, then the 2 initial nodes are kept
     */
    Node* MergeNodes(Node *__A, Node *__B, int __id, bool __keepNodes=false);
    Node* MergeNodes(int   __A,int    __B, int __id, bool __keepNodes=false);

    /**
     * Get one arc by ID
     */
    Arc * GetArc (int) const;

    /**
     * Remove one node, and all its references in its incident arcs
     */
    int RemoveNode (int __id);

    /**
     * Remove one node, and all its references in its incident arcs
     */
    int RemoveNode (Node *);

    /**
     * Remove one Arc, and all its references in its nodes
     */
    int RemoveArc (int __id);

    /**
     * Remove one Arc, and all its references in its nodes
     */
    int RemoveArc (Arc *);

    /**
     * Add one node
     */
    Node * AddNode (int __id=0);

    /**
     * Add an arc
     * returns 0 if successful
     */
    Arc * AddArc (const std::vector<int> &, int __id);

    /**
     * Add an arc that links __rank Nodes Together,
     * and affects the ID __id to the new arc
     * Example : AddArc(123, 3, 4, 54, 5);
     * creates arc ID=123, Rank=3, Nodes=4;54;5
     */
    Arc * AddArc(const int __id, int __rank, ...);

    Arc * AddArc(const int __id, const std::multimap<int, Node*> & __nodes);

    /**
     * Checks if the ID already exists in the Nodes of the graph,
     * if it already exists, it get the first free one starting
     * from the lowest ID of the nodes.
     *
     * return : the ID
     */
    int CheckFreeNodeId(int __id) const;

    /**
     * Checks if the ID already exists in the Arcs of the graph,
     * if it already exists, it get the first free one starting
     * from the lowest ID of the arcs.
     *
     * return : the ID
     */
    int CheckFreeArcId(int __id) const;

    /**
     * Returns the maximum value of the arcs' IDs of this graph
     */
    int GetMaxArcId();

    /**
     * Returns the maximum value of the nodes' IDs of this graph
     */
    int GetMaxNodeId();

    /**
     * Get the array of arcs by ID
     */
    const MapArcsById & GetArcs()const {
        return _arcs;
    } ;

    /**
     * Get the array of nodes by ID
     */
    const MapNodesById & GetNodes()const {
        return _nodes;
    } ;

    /**
     * DEBUGGING PURPOSES
     * Verifies the integrity of the Graph :
     * * each node of the arcs must exist in the graph
     * * each incident arc of each node must exist in the graph
     * * each incident arc of each node must reference this node
     * * each node of each arc must reference this arc
     */
    void CheckIntegrity()const;

    /**
     * Extract filaments of the graph
     */
    void Filaments (  std::vector < std::vector < int > > & __filaments );

    /**
     *  Tests wether the graph is a cycle or not
     */
    bool IsCycle () const;
    bool IsCycle (const std::vector < Node * > & __nodes) const;

    /**
    * duplicate an arc, use the second argument to set
    * the id of the new arc
    */
    Arc * DuplicateArc(int __id, int __dupId);
    Arc * DuplicateArc(Arc * __arc, int __dupId);

protected:
    MapArcsById _arcs;
    MapNodesById _nodes;
};

} // end namespace HypergraphLib


#endif // GRAPH_H
Revision:	1156
Committed:	Thu Jun 13 22:02:48 2024 UTC (14 months, 2 weeks ago) by francois
Content type:	text/plain
File size:	5959 byte(s)
Log Message:	compatibilité Ubuntu 22.04 Suppression des refeences à Windows Ajout d'une banière
#	User	Rev	Content
1	francois	1156	//####//------------------------------------------------------------
2			//####//------------------------------------------------------------
3			//####// MAGiC
4			//####// Jean Christophe Cuilliere et Vincent FRANCOIS
5			//####// Departement de Genie Mecanique - UQTR
6			//####//------------------------------------------------------------
7			//####// MAGIC est un projet de recherche de l equipe ERICCA
8			//####// du departement de genie mecanique de l Universite du Quebec a Trois Rivieres
9			//####// http://www.uqtr.ca/ericca
10			//####// http://www.uqtr.ca/
11			//####//------------------------------------------------------------
12			//####//------------------------------------------------------------
13			//####//
14			//####// hypergraphlib_graph.h
15			//####//
16			//####//------------------------------------------------------------
17			//####//------------------------------------------------------------
18			//####// COPYRIGHT 2000-2024
19			//####// jeu 13 jun 2024 11:54:00 EDT
20			//####//------------------------------------------------------------
21			//####//------------------------------------------------------------
22	francois	283	#ifndef GRAPHH
23			#define GRAPHH
24
25			#include <map>
26			#include <set>
27			#include <vector>
28
29	francois	481	#include "hypergraphlib_graphobject.h"
30	francois	283
31			#define GRAPH_FOR_EACH_ARC_CONST(G,A) \
32			for (HypergraphLib::Graph::MapArcsById::const_iterator A = G->GetArcs().begin(); \
33			A != G->GetArcs().end(); \
34			A++)
35
36			#define GRAPH_FOR_EACH_ARC(G,A) \
37			for (HypergraphLib::Graph::MapArcsById::iterator A = G->GetArcs().begin(); \
38			A != G->GetArcs().end(); \
39			A++)
40
41			#define GRAPH_FOR_EACH_NODE_CONST(G,N) \
42			for (HypergraphLib::Graph::MapNodesById::const_iterator N = G->GetNodes().begin(); \
43			N != G->GetNodes().end(); \
44			N++)
45
46			#define GRAPH_FOR_EACH_NODE(G,N) \
47			for (HypergraphLib::Graph::MapNodesById::iterator N = G->GetNodes().begin(); \
48			N != G->GetNodes().end(); \
49			N++)
50
51
52
53			namespace HypergraphLib {
54
55			class Node;
56			class Arc;
57
58			class HYPERGRAPHLIB_ITEM Graph : public GraphObject {
59			public:
60			typedef std::map < int, Arc * > MapArcsById;
61			typedef std::map < int, Node * > MapNodesById;
62
63			~Graph();
64
65			/**
66			* Constructor
67			*/
68			Graph(int __id=0);
69
70			/**
71			* copy constructor
72			*/
73			Graph(const Graph &__G, int __clone=1, int __reverse=0);
74
75			/**
76			* subgraph constructor
77			*/
78			Graph(const Graph &__G, const std::set <Node *> & );
79			Graph(const Graph &__G, const std::vector <Node*> & __nodes);
80
81			/**
82			* Get one node by ID
83			*/
84			Node * GetNode (int) const;
85
86
87			/**
88			* Merge two nodes
89			* if __keepNodes = true, then the 2 initial nodes are kept
90			*/
91			Node* MergeNodes(Node __A, Node __B, int __id, bool __keepNodes=false);
92			Node* MergeNodes(int __A,int __B, int __id, bool __keepNodes=false);
93
94			/**
95			* Get one arc by ID
96			*/
97			Arc * GetArc (int) const;
98
99			/**
100			* Remove one node, and all its references in its incident arcs
101			*/
102			int RemoveNode (int __id);
103
104			/**
105			* Remove one node, and all its references in its incident arcs
106			*/
107			int RemoveNode (Node *);
108
109			/**
110			* Remove one Arc, and all its references in its nodes
111			*/
112			int RemoveArc (int __id);
113
114			/**
115			* Remove one Arc, and all its references in its nodes
116			*/
117			int RemoveArc (Arc *);
118
119			/**
120			* Add one node
121			*/
122			Node * AddNode (int __id=0);
123
124			/**
125			* Add an arc
126			* returns 0 if successful
127			*/
128			Arc * AddArc (const std::vector<int> &, int __id);
129
130			/**
131			* Add an arc that links __rank Nodes Together,
132			* and affects the ID __id to the new arc
133			* Example : AddArc(123, 3, 4, 54, 5);
134			* creates arc ID=123, Rank=3, Nodes=4;54;5
135			*/
136			Arc * AddArc(const int __id, int __rank, ...);
137
138			Arc * AddArc(const int __id, const std::multimap<int, Node*> & __nodes);
139
140			/**
141			* Checks if the ID already exists in the Nodes of the graph,
142			* if it already exists, it get the first free one starting
143			* from the lowest ID of the nodes.
144			*
145			* return : the ID
146			*/
147			int CheckFreeNodeId(int __id) const;
148
149			/**
150			* Checks if the ID already exists in the Arcs of the graph,
151			* if it already exists, it get the first free one starting
152			* from the lowest ID of the arcs.
153			*
154			* return : the ID
155			*/
156			int CheckFreeArcId(int __id) const;
157
158			/**
159			* Returns the maximum value of the arcs' IDs of this graph
160			*/
161			int GetMaxArcId();
162
163			/**
164			* Returns the maximum value of the nodes' IDs of this graph
165			*/
166			int GetMaxNodeId();
167
168			/**
169			* Get the array of arcs by ID
170			*/
171			const MapArcsById & GetArcs()const {
172			return _arcs;
173			} ;
174
175			/**
176			* Get the array of nodes by ID
177			*/
178			const MapNodesById & GetNodes()const {
179			return _nodes;
180			} ;
181
182			/**
183			* DEBUGGING PURPOSES
184			* Verifies the integrity of the Graph :
185			* * each node of the arcs must exist in the graph
186			* * each incident arc of each node must exist in the graph
187			* * each incident arc of each node must reference this node
188			* * each node of each arc must reference this arc
189			*/
190			void CheckIntegrity()const;
191
192			/**
193			* Extract filaments of the graph
194			*/
195			void Filaments ( std::vector < std::vector < int > > & __filaments );
196
197			/**
198			* Tests wether the graph is a cycle or not
199			*/
200			bool IsCycle () const;
201			bool IsCycle (const std::vector < Node * > & __nodes) const;
202
203			/**
204			* duplicate an arc, use the second argument to set
205			* the id of the new arc
206			*/
207			Arc * DuplicateArc(int __id, int __dupId);
208			Arc * DuplicateArc(Arc * __arc, int __dupId);
209
210			protected:
211			MapArcsById _arcs;
212			MapNodesById _nodes;
213			};
214
215			} // end namespace HypergraphLib
216
217
218			#endif // GRAPH_H