outil/src/hypergraphlib_graph.h

#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:	283
Committed:	Tue Sep 13 21:11:20 2011 UTC (13 years, 8 months ago) by francois
Content type:	text/plain
Original Path:	*magic/lib/outil/src/HypergraphLib_Graph.h*
File size:	4877 byte(s)
Log Message:	structure de l'écriture
#	User	Rev	Content
1	francois	283	#ifndef GRAPHH
2			#define GRAPHH
3
4			#include <map>
5			#include <set>
6			#include <vector>
7
8			#include "HypergraphLib_GraphObject.h"
9
10			#define GRAPH_FOR_EACH_ARC_CONST(G,A) \
11			for (HypergraphLib::Graph::MapArcsById::const_iterator A = G->GetArcs().begin(); \
12			A != G->GetArcs().end(); \
13			A++)
14
15			#define GRAPH_FOR_EACH_ARC(G,A) \
16			for (HypergraphLib::Graph::MapArcsById::iterator A = G->GetArcs().begin(); \
17			A != G->GetArcs().end(); \
18			A++)
19
20			#define GRAPH_FOR_EACH_NODE_CONST(G,N) \
21			for (HypergraphLib::Graph::MapNodesById::const_iterator N = G->GetNodes().begin(); \
22			N != G->GetNodes().end(); \
23			N++)
24
25			#define GRAPH_FOR_EACH_NODE(G,N) \
26			for (HypergraphLib::Graph::MapNodesById::iterator N = G->GetNodes().begin(); \
27			N != G->GetNodes().end(); \
28			N++)
29
30
31
32			namespace HypergraphLib {
33
34			class Node;
35			class Arc;
36
37			class HYPERGRAPHLIB_ITEM Graph : public GraphObject {
38			public:
39			typedef std::map < int, Arc * > MapArcsById;
40			typedef std::map < int, Node * > MapNodesById;
41
42			~Graph();
43
44			/**
45			* Constructor
46			*/
47			Graph(int __id=0);
48
49			/**
50			* copy constructor
51			*/
52			Graph(const Graph &__G, int __clone=1, int __reverse=0);
53
54			/**
55			* subgraph constructor
56			*/
57			Graph(const Graph &__G, const std::set <Node *> & );
58			Graph(const Graph &__G, const std::vector <Node*> & __nodes);
59
60			/**
61			* Get one node by ID
62			*/
63			Node * GetNode (int) const;
64
65
66			/**
67			* Merge two nodes
68			* if __keepNodes = true, then the 2 initial nodes are kept
69			*/
70			Node* MergeNodes(Node __A, Node __B, int __id, bool __keepNodes=false);
71			Node* MergeNodes(int __A,int __B, int __id, bool __keepNodes=false);
72
73			/**
74			* Get one arc by ID
75			*/
76			Arc * GetArc (int) const;
77
78			/**
79			* Remove one node, and all its references in its incident arcs
80			*/
81			int RemoveNode (int __id);
82
83			/**
84			* Remove one node, and all its references in its incident arcs
85			*/
86			int RemoveNode (Node *);
87
88			/**
89			* Remove one Arc, and all its references in its nodes
90			*/
91			int RemoveArc (int __id);
92
93			/**
94			* Remove one Arc, and all its references in its nodes
95			*/
96			int RemoveArc (Arc *);
97
98			/**
99			* Add one node
100			*/
101			Node * AddNode (int __id=0);
102
103			/**
104			* Add an arc
105			* returns 0 if successful
106			*/
107			Arc * AddArc (const std::vector<int> &, int __id);
108
109			/**
110			* Add an arc that links __rank Nodes Together,
111			* and affects the ID __id to the new arc
112			* Example : AddArc(123, 3, 4, 54, 5);
113			* creates arc ID=123, Rank=3, Nodes=4;54;5
114			*/
115			Arc * AddArc(const int __id, int __rank, ...);
116
117			Arc * AddArc(const int __id, const std::multimap<int, Node*> & __nodes);
118
119			/**
120			* Checks if the ID already exists in the Nodes of the graph,
121			* if it already exists, it get the first free one starting
122			* from the lowest ID of the nodes.
123			*
124			* return : the ID
125			*/
126			int CheckFreeNodeId(int __id) const;
127
128			/**
129			* Checks if the ID already exists in the Arcs of the graph,
130			* if it already exists, it get the first free one starting
131			* from the lowest ID of the arcs.
132			*
133			* return : the ID
134			*/
135			int CheckFreeArcId(int __id) const;
136
137			/**
138			* Returns the maximum value of the arcs' IDs of this graph
139			*/
140			int GetMaxArcId();
141
142			/**
143			* Returns the maximum value of the nodes' IDs of this graph
144			*/
145			int GetMaxNodeId();
146
147			/**
148			* Get the array of arcs by ID
149			*/
150			const MapArcsById & GetArcs()const {
151			return _arcs;
152			} ;
153
154			/**
155			* Get the array of nodes by ID
156			*/
157			const MapNodesById & GetNodes()const {
158			return _nodes;
159			} ;
160
161			/**
162			* DEBUGGING PURPOSES
163			* Verifies the integrity of the Graph :
164			* * each node of the arcs must exist in the graph
165			* * each incident arc of each node must exist in the graph
166			* * each incident arc of each node must reference this node
167			* * each node of each arc must reference this arc
168			*/
169			void CheckIntegrity()const;
170
171			/**
172			* Extract filaments of the graph
173			*/
174			void Filaments ( std::vector < std::vector < int > > & __filaments );
175
176			/**
177			* Tests wether the graph is a cycle or not
178			*/
179			bool IsCycle () const;
180			bool IsCycle (const std::vector < Node * > & __nodes) const;
181
182			/**
183			* duplicate an arc, use the second argument to set
184			* the id of the new arc
185			*/
186			Arc * DuplicateArc(int __id, int __dupId);
187			Arc * DuplicateArc(Arc * __arc, int __dupId);
188
189			protected:
190			MapArcsById _arcs;
191			MapNodesById _nodes;
192			};
193
194			} // end namespace HypergraphLib
195
196
197			#endif // GRAPH_H