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
#	Content
1	//####//------------------------------------------------------------
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	#ifndef GRAPHH
23	#define GRAPHH
24
25	#include <map>
26	#include <set>
27	#include <vector>
28
29	#include "hypergraphlib_graphobject.h"
30
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