outil/src/hypergraphlib_graph.cpp

#include "gestionversion.h"
#include <iostream>
#include <vector>
#include <stdarg.h>

#pragma hdrstop

#include "HypergraphLib_platform.h"

#include "HypergraphLib_Graph.h"
#include "HypergraphLib_Arc.h"
#include "HypergraphLib_Node.h"
#include <algorithm>


namespace HypergraphLib {

Graph::Graph(int __id)
        : GraphObject(NULL,__id)
{

}

Graph::~Graph()
{
    for (MapNodesById::const_iterator it=_nodes.begin();
            it!=_nodes.end();
            it ++)
    {
        Node * node = it->second;
        delete node;
    }
    for (MapArcsById::const_iterator it=_arcs.begin();
            it!=_arcs.end();
            it ++)
    {
        Arc * arc = it->second;
        delete arc;
    }
}

#undef CHECK_INTEGRITY


Graph::Graph(const Graph &__G, int __clone, int __reverse)
        :GraphObject(NULL, __G.Id())
{
    for (MapNodesById::const_iterator it=__G._nodes.begin();
            it!=__G._nodes.end();
            it ++)
    {
        Node * copy = new Node(*it->second, this);
        _nodes [ it->first ] = copy;
    }

    for (MapArcsById::const_iterator it=__G._arcs.begin();
            it!=__G._arcs.end();
            it ++)
    {
        Arc * copy = new Arc(*it->second, this);
        _arcs [ it->first ] = copy;
        for (Arc::MultimapNodesById::const_iterator it2=copy->Nodes().begin();
                it2 != copy->Nodes().end(); it2++)
        {
            it2->second->Add(copy);
        }
    }
}

Graph::Graph(const Graph &__G, const std::set <Node*> & __nodes)
        :GraphObject(NULL, __G.Id())
{
    for (std::set <Node*>::const_iterator it=__nodes.begin();
            it!=__nodes.end();
            it ++)
    {
        Node * src = *it;
        Node * n = AddNode (src->Id());
        n->SetUserData(src->GetUserData());
    }

    for (MapArcsById::const_iterator it=__G._arcs.begin();
            it!=__G._arcs.end();
            it ++)
    {
        std::vector <int> nodesIds;

        Arc * arc = it->second;
        for (Arc::MultimapNodesById::const_iterator it2=arc->Nodes().begin();
                it2 != arc->Nodes().end(); it2++)
        {
            if (_nodes.find(it2->first) != _nodes.end())
            {
                nodesIds.push_back(it2->first);
            }
        }

        if (nodesIds.size() > 0)
        {
            int id = arc->Id();
            Arc * a = AddArc(nodesIds, id);
            a->SetUserData ( arc->GetUserData() );
        }
    }
}

Graph::Graph(const Graph &__G, const std::vector <Node*> & __nodes)
        :GraphObject(NULL, __G.Id())
{
    for (std::vector <Node*>::const_iterator it=__nodes.begin();
            it!=__nodes.end();
            it ++)
    {
        Node * src = *it;
        Node * n = AddNode (src->Id());
        n->SetUserData(src->GetUserData());
    }

    for (MapArcsById::const_iterator it=__G._arcs.begin();
            it!=__G._arcs.end();
            it ++)
    {
        std::vector <int> nodesIds;

        Arc * arc = it->second;
        for (Arc::MultimapNodesById::const_iterator it2=arc->Nodes().begin();
                it2 != arc->Nodes().end(); it2++)
        {
            if (_nodes.find(it2->first) != _nodes.end())
            {
                nodesIds.push_back(it2->first);
            }
        }

        if (nodesIds.size() > 1)
        {
            int id = arc->Id();
            Arc * a = AddArc(nodesIds, id);
            a->SetUserData ( arc->GetUserData() );
        }
    }
}

Arc * Graph::DuplicateArc(int __id, int __dupId)
{
    Arc * arc = GetArc(__id);
    return DuplicateArc(arc, __dupId);
}

Arc * Graph::DuplicateArc(Arc * __arc, int __dupId)
{
    return AddArc(__dupId, __arc->Nodes());
}

Node * Graph::GetNode (int __id) const
{
    MapNodesById::const_iterator it = _nodes.find ( __id );
    if (it != _nodes.end() )
    {
        return it->second;
    }
    else
    {
        return NULL;
    }
}

Arc * Graph::GetArc (int __id) const
{
    MapArcsById::const_iterator it = _arcs.find ( __id );
    if (it != _arcs.end() )
    {
        return it->second;
    }
    else
    {
        return NULL;
    }
}

int Graph::RemoveNode (Node * __node)
{
    MapNodesById::iterator it = _nodes.find ( __node->Id() );
    if (it != _nodes.end())
    {
        // Remove all references of node n in the arcs of the graph
        for (Node::MultimapArcsById::iterator itArcs = __node->IncidentArcs().begin();
                itArcs != __node->IncidentArcs().end();
                itArcs++)
        {
            itArcs->second->Remove(__node);
        }
        // Free the memory of n
        delete __node;
        _nodes.erase ( it );
    }
    else
    {
        std::cout << "Error: Graph::RemoveNode ( "<<__node->Id()<<" )"<<std::endl;
        std::cout << "\t the node was not found !\n"<<__node->Id()<<" )"<<std::endl;
        return -1;
    }
#ifdef CHECK_INTEGRITY
    CheckIntegrity();
#endif
    return 0;
}

int Graph::RemoveNode (int __id)
{
    MapNodesById::iterator it = _nodes.find ( __id );
    if (it != _nodes.end())
    {
        Node * n = it->second;
        return RemoveNode(n);
    }
    else
    {
        std::cout << "Error: Graph::RemoveNode ( "<<__id<<" )"<<std::endl;
        std::cout << "\t the node was not found !\n"<<__id<<" )"<<std::endl;
        return -1;
    }
}

int Graph::RemoveArc (Arc *__arc)
{
    return RemoveArc (__arc->Id());
}

int Graph::RemoveArc (int __id)
{
    MapArcsById::iterator it = _arcs.find ( __id );
    if (it != _arcs.end())
    {
        Arc * tempArc = it->second;

        for (Arc::MultimapNodesById::const_iterator it2=tempArc->Nodes().begin();
                it2!=tempArc->Nodes().end();it2++)
        {
            it2->second->Remove(__id);
        }

        delete tempArc;
        _arcs.erase ( it );

        return 0;
    }
    else
    {
        std::cout << "Error: Graph::RemoveArc ( "<<__id<<" )"<<std::endl;
        std::cout << "\t the arc was not found !\n"<<__id<<" )"<<std::endl;
        return -1;
    }
}


Node *
Graph::AddNode (int __id)
{
    if (_nodes.find(__id) != _nodes.end())
        return NULL;

    Node *n = new Node(this, __id);
    _nodes [ __id ] = n;
    return n;
}

/*int Graph::CheckFreeNodeId(int __id) const
{
    int id = __id;

    // Verify that the node Id is free
    MapNodesById::const_iterator it = _nodes.find(id);
    bool idExists = (it != _nodes.end())?true:false;

    // if the id is not free, then get the first free one
    if (idExists)
        {
            id = GetFirstFreeKey(_nodes);
            std::cout << "Warning: The Node ID \""<<__id<<"\" already exists !\n";
            std::cout << "Taking the Free ID \""<<id<<"\" instead\n";
        }
    return id;
}

int Graph::CheckFreeArcId(int __id) const
{
    int id = __id;

    // Verify that the arc Id is free
    MapArcsById::const_iterator it = _arcs.find(id);
    bool idExists = (it != _arcs.end())?true:false;

    // if the id is not free, then get the first free one
    if (idExists)
        {
            id = GetFirstFreeKey(_arcs);
            std::cout << "Warning: The Arc ID \""<<__id<<"\" already exists !\n";
            std::cout << "Taking the Free ID \""<<id<<"\" instead\n";
        }
    return id;
}*/

int Graph::GetMaxArcId()
{
    return std::max_element(_arcs.begin(), _arcs.end())->first;
}

int Graph::GetMaxNodeId()
{
    return std::max_element(_nodes.begin(), _nodes.end())->first;
}

Arc *
Graph::AddArc(const int __id, int __rank, ...)
{
    if (_arcs.find(__id) != _arcs.end() )
        return NULL;

    Arc * a = new Arc (this, __id);
    _arcs [ __id ] = a;

    va_list argp;
    va_start(argp, __rank);

    for (int i=0;i<__rank;i++)
    {
        int nodeId = va_arg(argp, int);
        Node * n = GetNode(nodeId);
        a->Add(n);
        n->Add(a);
    }

    return a;
}

Arc *
Graph::AddArc(const int __id, const Arc::MultimapNodesById & __nodes)
{
    if (_arcs.find(__id) != _arcs.end() )
        return NULL;

    Arc * a = new Arc (this, __id);
    _arcs [ __id ] = a;

    for (Arc::MultimapNodesById::const_iterator itNodes = __nodes.begin();
            itNodes != __nodes.end();
            itNodes++)
    {
        Node * n = itNodes->second;
        a->Add(n);
        n->Add(a);
    }

    return a;
}

Arc * Graph::AddArc (const std::vector <int> & __nodeIds, int __id)
{
    if (_arcs.find(__id) != _arcs.end() )
        return NULL;

    Arc * a = new Arc (this, __id);
    _arcs [ __id ] = a;

    for (unsigned int i=0;i<__nodeIds.size();i++)
    {
        int nodeId = __nodeIds[i];
        Node * n = GetNode(nodeId);
        a->Add(n);
        n->Add(a);
    }

    return  a;
}


Node*
Graph::MergeNodes(int __A, int __B, int __id, bool __keepNodes)
{
    Node * A = GetNode(__A);
    Node * B = GetNode(__B);

    return MergeNodes(A, B, __id, __keepNodes);
}

/**
      Merge two nodes.

      This merge is implemented by creating a new node C, and
      replacing node A by node C in all arcs incident to A, and
      node B by node C in all arcs incident to B.

      (If there exist two arcs X--A and X--B, it *will* result two
      parallel arcs X--C.  Any arc A--B will result in a loop-arc
      C--C).

      Then nodes A and B will be removed from the graph.
*/
Node*
Graph::MergeNodes(Node *__A, Node *__B, int __id, bool __keepNodes)
{
    Node::MultimapArcsById incidentArcs;

    for (Node::MultimapArcsById::const_iterator it = __A->IncidentArcs().begin();
            it != __A->IncidentArcs().end();
            it++)
    {
        incidentArcs.insert(std::pair<int,Arc*>(it->first,it->second));
    }

    for (Node::MultimapArcsById::iterator it = __B->IncidentArcs().begin();
            it != __B->IncidentArcs().end();
            it++)
    {
        incidentArcs.insert(std::pair<int,Arc*>(it->first,it->second));
    }

    if (!__keepNodes)
    {
        RemoveNode(__A);
        RemoveNode(__B);
    }

    Node * C = this->AddNode(__id);

    for (Node::MultimapArcsById::iterator it = incidentArcs.begin();
            it != incidentArcs.end();
            it++)
    {
        it->second->Add(C);
        C->Add(it->second);
    }

    return C;
}

void Graph::CheckIntegrity()const
{
    //   * * each incident arc of each node must exist in the graph
    for (HypergraphLib::Graph::MapNodesById::const_iterator it=GetNodes().begin();
            it != GetNodes().end(); it++)
    {
        for (HypergraphLib::Node::MultimapArcsById::const_iterator it2=it->second->IncidentArcs().begin();
                it2!=it->second->IncidentArcs().end();it2++)
        {
            int id=it2->second->Id();
            Arc * arcInGraph = GetArc(id);
            if (arcInGraph != it2->second)
                std::cerr << "Error: The incident Arc "<<id<<" of node "<<it->second->Id()<<"is not referenced in the graph"<<std::endl;
        }
    }

    //   * * each node of the arcs must exist in the graph
    for (HypergraphLib::Graph::MapArcsById::const_iterator it=GetArcs().begin();
            it != GetArcs().end(); it++)
    {
        for (HypergraphLib::Arc::MultimapNodesById::const_iterator it2=it->second->Nodes().begin();
                it2!=it->second->Nodes().end();it2++)
        {
            int id=it2->second->Id();
            Node * nodeInGraph = GetNode(id);
            if (nodeInGraph != it2->second)
                std::cerr << "Error: The Node "<<id<<" of arc "<<it->first<<"is not referenced in the graph"<<std::endl;
        }
    }

    //   * * each node of each arc must reference this arc
    for (HypergraphLib::Graph::MapNodesById::const_iterator it=GetNodes().begin();
            it != GetNodes().end(); it++)
    {
        for (HypergraphLib::Node::MultimapArcsById::const_iterator it2=it->second->IncidentArcs().begin();
                it2!=it->second->IncidentArcs().end();it2++)
        {
            int nodeC=it2->second->NodeCount(it->first);
            int arcC=it->second->ArcCount(it2->first);
            if (nodeC != arcC)
            {
                std::cerr << "Error: the Arc->NodeCount("<<it->first<<")="<<nodeC<<""<<std::endl;
                std::cerr << "is not equal to the Node->ArcCount("<<it2->first<<")="<<arcC<<""<<std::endl;
            }
        }
    }

    //   * * each incident arc of each node must reference this node

    for (HypergraphLib::Graph::MapArcsById::const_iterator it2=GetArcs().begin();
            it2 != GetArcs().end(); it2++)
    {
        for (HypergraphLib::Arc::MultimapNodesById::const_iterator it=it2->second->Nodes().begin();
                it!=it2->second->Nodes().end();it++)
        {
            int nodeC=it2->second->NodeCount(it->first);
            int arcC=it->second->ArcCount(it2->first);
            if (nodeC != arcC)
            {
                std::cerr << "Error: the Arc->NodeCount("<<it->first<<")="<<nodeC<<""<<std::endl;
                std::cerr << "is not equal to the Node->ArcCount("<<it2->first<<")="<<arcC<<""<<std::endl;
            }
        }
    }
}

bool Graph::IsCycle() const
{
    if (_nodes.size() != _arcs.size())
        return false;
    for (HypergraphLib::Graph::MapArcsById::const_iterator it2=GetArcs().begin();
            it2 != GetArcs().end(); it2++)
        if (it2->second->Rank() != 2)
            return false;
    return true;
}


bool Graph::IsCycle (const std::vector < Node * > & __nodes) const
{
    if (__nodes.size () < 2 ) return false;

    //unsigned nb_nodes_having_2_neighbours = 0;

    const unsigned N  = __nodes.size();

    for (unsigned i=0; i<N; i++)
    {
        Node * n = __nodes[i];
        //unsigned nb_neighbours=0;
        int i_previous = i-1;
        if (i_previous < 0) i_previous += N;
        Node *n_previous = __nodes[i_previous];
        int i_next = (i+1)%N;
        Node *n_next = __nodes[i_next];

        Arc * arc1 = n->IsAdjacentToNode(n_next);
        Arc * arc2 = n->IsAdjacentToNode(n_previous);

        if ( arc1 && arc2 && arc1 != arc2 )
        {
            if (n_next == n_previous)
            {
                if (n->GetNbArcsToNode(n_previous) < 2)
                    return false;
                else
                    continue;
            }
        }
        else
            return false;
    }
    return true;
}

}

Revision:	283
Committed:	Tue Sep 13 21:11:20 2011 UTC (13 years, 8 months ago) by francois
Original Path:	*magic/lib/outil/src/HypergraphLib_Graph.cpp*
File size:	14120 byte(s)
Log Message:	structure de l'écriture
#	User	Rev	Content
1	francois	113	#include "gestionversion.h"
2	francois	283	#include <iostream>
3			#include <vector>
4			#include <stdarg.h>
5
6			#pragma hdrstop
7
8			#include "HypergraphLib_platform.h"
9
10			#include "HypergraphLib_Graph.h"
11			#include "HypergraphLib_Arc.h"
12			#include "HypergraphLib_Node.h"
13			#include <algorithm>
14
15
16			namespace HypergraphLib {
17
18			Graph::Graph(int __id)
19			: GraphObject(NULL,__id)
20			{
21
22	francois	102	}
23	foucault	176
24	francois	283	Graph::~Graph()
25			{
26			for (MapNodesById::const_iterator it=_nodes.begin();
27			it!=_nodes.end();
28			it ++)
29			{
30			Node * node = it->second;
31			delete node;
32			}
33			for (MapArcsById::const_iterator it=_arcs.begin();
34			it!=_arcs.end();
35			it ++)
36			{
37			Arc * arc = it->second;
38			delete arc;
39			}
40			}
41
42			#undef CHECK_INTEGRITY
43
44
45			Graph::Graph(const Graph &__G, int __clone, int __reverse)
46			:GraphObject(NULL, __G.Id())
47			{
48			for (MapNodesById::const_iterator it=__G._nodes.begin();
49			it!=__G._nodes.end();
50			it ++)
51			{
52			Node * copy = new Node(*it->second, this);
53			_nodes [ it->first ] = copy;
54			}
55
56			for (MapArcsById::const_iterator it=__G._arcs.begin();
57			it!=__G._arcs.end();
58			it ++)
59			{
60			Arc * copy = new Arc(*it->second, this);
61			_arcs [ it->first ] = copy;
62			for (Arc::MultimapNodesById::const_iterator it2=copy->Nodes().begin();
63			it2 != copy->Nodes().end(); it2++)
64			{
65			it2->second->Add(copy);
66			}
67			}
68			}
69
70			Graph::Graph(const Graph &__G, const std::set <Node*> & __nodes)
71			:GraphObject(NULL, __G.Id())
72			{
73			for (std::set <Node*>::const_iterator it=__nodes.begin();
74			it!=__nodes.end();
75			it ++)
76			{
77			Node * src = *it;
78			Node * n = AddNode (src->Id());
79			n->SetUserData(src->GetUserData());
80			}
81
82			for (MapArcsById::const_iterator it=__G._arcs.begin();
83			it!=__G._arcs.end();
84			it ++)
85			{
86			std::vector <int> nodesIds;
87
88			Arc * arc = it->second;
89			for (Arc::MultimapNodesById::const_iterator it2=arc->Nodes().begin();
90			it2 != arc->Nodes().end(); it2++)
91			{
92			if (_nodes.find(it2->first) != _nodes.end())
93			{
94			nodesIds.push_back(it2->first);
95			}
96			}
97
98			if (nodesIds.size() > 0)
99			{
100			int id = arc->Id();
101			Arc * a = AddArc(nodesIds, id);
102			a->SetUserData ( arc->GetUserData() );
103			}
104			}
105			}
106
107			Graph::Graph(const Graph &__G, const std::vector <Node*> & __nodes)
108			:GraphObject(NULL, __G.Id())
109			{
110			for (std::vector <Node*>::const_iterator it=__nodes.begin();
111			it!=__nodes.end();
112			it ++)
113			{
114			Node * src = *it;
115			Node * n = AddNode (src->Id());
116			n->SetUserData(src->GetUserData());
117			}
118
119			for (MapArcsById::const_iterator it=__G._arcs.begin();
120			it!=__G._arcs.end();
121			it ++)
122			{
123			std::vector <int> nodesIds;
124
125			Arc * arc = it->second;
126			for (Arc::MultimapNodesById::const_iterator it2=arc->Nodes().begin();
127			it2 != arc->Nodes().end(); it2++)
128			{
129			if (_nodes.find(it2->first) != _nodes.end())
130			{
131			nodesIds.push_back(it2->first);
132			}
133			}
134
135			if (nodesIds.size() > 1)
136			{
137			int id = arc->Id();
138			Arc * a = AddArc(nodesIds, id);
139			a->SetUserData ( arc->GetUserData() );
140			}
141			}
142			}
143
144			Arc * Graph::DuplicateArc(int __id, int __dupId)
145			{
146			Arc * arc = GetArc(__id);
147			return DuplicateArc(arc, __dupId);
148			}
149
150			Arc * Graph::DuplicateArc(Arc * __arc, int __dupId)
151			{
152			return AddArc(__dupId, __arc->Nodes());
153			}
154
155			Node * Graph::GetNode (int __id) const
156			{
157			MapNodesById::const_iterator it = _nodes.find ( __id );
158			if (it != _nodes.end() )
159			{
160			return it->second;
161			}
162			else
163			{
164			return NULL;
165			}
166			}
167
168			Arc * Graph::GetArc (int __id) const
169			{
170			MapArcsById::const_iterator it = _arcs.find ( __id );
171			if (it != _arcs.end() )
172			{
173			return it->second;
174			}
175			else
176			{
177			return NULL;
178			}
179			}
180
181			int Graph::RemoveNode (Node * __node)
182			{
183			MapNodesById::iterator it = _nodes.find ( __node->Id() );
184			if (it != _nodes.end())
185			{
186			// Remove all references of node n in the arcs of the graph
187			for (Node::MultimapArcsById::iterator itArcs = __node->IncidentArcs().begin();
188			itArcs != __node->IncidentArcs().end();
189			itArcs++)
190			{
191			itArcs->second->Remove(__node);
192			}
193			// Free the memory of n
194			delete __node;
195			_nodes.erase ( it );
196			}
197			else
198			{
199			std::cout << "Error: Graph::RemoveNode ( "<<__node->Id()<<" )"<<std::endl;
200			std::cout << "\t the node was not found !\n"<<__node->Id()<<" )"<<std::endl;
201			return -1;
202			}
203			#ifdef CHECK_INTEGRITY
204			CheckIntegrity();
205			#endif
206			return 0;
207			}
208
209			int Graph::RemoveNode (int __id)
210			{
211			MapNodesById::iterator it = _nodes.find ( __id );
212			if (it != _nodes.end())
213			{
214			Node * n = it->second;
215			return RemoveNode(n);
216			}
217			else
218			{
219			std::cout << "Error: Graph::RemoveNode ( "<<__id<<" )"<<std::endl;
220			std::cout << "\t the node was not found !\n"<<__id<<" )"<<std::endl;
221			return -1;
222			}
223			}
224
225			int Graph::RemoveArc (Arc *__arc)
226			{
227			return RemoveArc (__arc->Id());
228			}
229
230			int Graph::RemoveArc (int __id)
231			{
232			MapArcsById::iterator it = _arcs.find ( __id );
233			if (it != _arcs.end())
234			{
235			Arc * tempArc = it->second;
236
237			for (Arc::MultimapNodesById::const_iterator it2=tempArc->Nodes().begin();
238			it2!=tempArc->Nodes().end();it2++)
239			{
240			it2->second->Remove(__id);
241			}
242
243			delete tempArc;
244			_arcs.erase ( it );
245
246			return 0;
247			}
248			else
249			{
250			std::cout << "Error: Graph::RemoveArc ( "<<__id<<" )"<<std::endl;
251			std::cout << "\t the arc was not found !\n"<<__id<<" )"<<std::endl;
252			return -1;
253			}
254			}
255
256
257			Node *
258			Graph::AddNode (int __id)
259			{
260			if (_nodes.find(__id) != _nodes.end())
261			return NULL;
262
263			Node *n = new Node(this, __id);
264			_nodes [ __id ] = n;
265			return n;
266			}
267
268			/*int Graph::CheckFreeNodeId(int __id) const
269			{
270			int id = __id;
271
272			// Verify that the node Id is free
273			MapNodesById::const_iterator it = _nodes.find(id);
274			bool idExists = (it != _nodes.end())?true:false;
275
276			// if the id is not free, then get the first free one
277			if (idExists)
278			{
279			id = GetFirstFreeKey(_nodes);
280			std::cout << "Warning: The Node ID \""<<__id<<"\" already exists !\n";
281			std::cout << "Taking the Free ID \""<<id<<"\" instead\n";
282			}
283			return id;
284			}
285
286			int Graph::CheckFreeArcId(int __id) const
287			{
288			int id = __id;
289
290			// Verify that the arc Id is free
291			MapArcsById::const_iterator it = _arcs.find(id);
292			bool idExists = (it != _arcs.end())?true:false;
293
294			// if the id is not free, then get the first free one
295			if (idExists)
296			{
297			id = GetFirstFreeKey(_arcs);
298			std::cout << "Warning: The Arc ID \""<<__id<<"\" already exists !\n";
299			std::cout << "Taking the Free ID \""<<id<<"\" instead\n";
300			}
301			return id;
302			}*/
303
304			int Graph::GetMaxArcId()
305			{
306			return std::max_element(_arcs.begin(), _arcs.end())->first;
307			}
308
309			int Graph::GetMaxNodeId()
310			{
311			return std::max_element(_nodes.begin(), _nodes.end())->first;
312			}
313
314			Arc *
315			Graph::AddArc(const int __id, int __rank, ...)
316			{
317			if (_arcs.find(__id) != _arcs.end() )
318			return NULL;
319
320			Arc * a = new Arc (this, __id);
321			_arcs [ __id ] = a;
322
323			va_list argp;
324			va_start(argp, __rank);
325
326			for (int i=0;i<__rank;i++)
327			{
328			int nodeId = va_arg(argp, int);
329			Node * n = GetNode(nodeId);
330			a->Add(n);
331			n->Add(a);
332			}
333
334			return a;
335			}
336
337			Arc *
338			Graph::AddArc(const int __id, const Arc::MultimapNodesById & __nodes)
339			{
340			if (_arcs.find(__id) != _arcs.end() )
341			return NULL;
342
343			Arc * a = new Arc (this, __id);
344			_arcs [ __id ] = a;
345
346			for (Arc::MultimapNodesById::const_iterator itNodes = __nodes.begin();
347			itNodes != __nodes.end();
348			itNodes++)
349			{
350			Node * n = itNodes->second;
351			a->Add(n);
352			n->Add(a);
353			}
354
355			return a;
356			}
357
358			Arc * Graph::AddArc (const std::vector <int> & __nodeIds, int __id)
359			{
360			if (_arcs.find(__id) != _arcs.end() )
361			return NULL;
362
363			Arc * a = new Arc (this, __id);
364			_arcs [ __id ] = a;
365
366			for (unsigned int i=0;i<__nodeIds.size();i++)
367			{
368			int nodeId = __nodeIds[i];
369			Node * n = GetNode(nodeId);
370			a->Add(n);
371			n->Add(a);
372			}
373
374			return a;
375			}
376
377
378			Node*
379			Graph::MergeNodes(int __A, int __B, int __id, bool __keepNodes)
380			{
381			Node * A = GetNode(__A);
382			Node * B = GetNode(__B);
383
384			return MergeNodes(A, B, __id, __keepNodes);
385			}
386
387			/**
388			Merge two nodes.
389
390			This merge is implemented by creating a new node C, and
391			replacing node A by node C in all arcs incident to A, and
392			node B by node C in all arcs incident to B.
393
394			(If there exist two arcs X--A and X--B, it will result two
395			parallel arcs X--C. Any arc A--B will result in a loop-arc
396			C--C).
397
398			Then nodes A and B will be removed from the graph.
399			*/
400			Node*
401			Graph::MergeNodes(Node __A, Node __B, int __id, bool __keepNodes)
402			{
403			Node::MultimapArcsById incidentArcs;
404
405			for (Node::MultimapArcsById::const_iterator it = __A->IncidentArcs().begin();
406			it != __A->IncidentArcs().end();
407			it++)
408			{
409			incidentArcs.insert(std::pair<int,Arc*>(it->first,it->second));
410			}
411
412			for (Node::MultimapArcsById::iterator it = __B->IncidentArcs().begin();
413			it != __B->IncidentArcs().end();
414			it++)
415			{
416			incidentArcs.insert(std::pair<int,Arc*>(it->first,it->second));
417			}
418
419			if (!__keepNodes)
420			{
421			RemoveNode(__A);
422			RemoveNode(__B);
423			}
424
425			Node * C = this->AddNode(__id);
426
427			for (Node::MultimapArcsById::iterator it = incidentArcs.begin();
428			it != incidentArcs.end();
429			it++)
430			{
431			it->second->Add(C);
432			C->Add(it->second);
433			}
434
435			return C;
436			}
437
438			void Graph::CheckIntegrity()const
439			{
440			// * * each incident arc of each node must exist in the graph
441			for (HypergraphLib::Graph::MapNodesById::const_iterator it=GetNodes().begin();
442			it != GetNodes().end(); it++)
443			{
444			for (HypergraphLib::Node::MultimapArcsById::const_iterator it2=it->second->IncidentArcs().begin();
445			it2!=it->second->IncidentArcs().end();it2++)
446			{
447			int id=it2->second->Id();
448			Arc * arcInGraph = GetArc(id);
449			if (arcInGraph != it2->second)
450			std::cerr << "Error: The incident Arc "<<id<<" of node "<<it->second->Id()<<"is not referenced in the graph"<<std::endl;
451			}
452			}
453
454			// * * each node of the arcs must exist in the graph
455			for (HypergraphLib::Graph::MapArcsById::const_iterator it=GetArcs().begin();
456			it != GetArcs().end(); it++)
457			{
458			for (HypergraphLib::Arc::MultimapNodesById::const_iterator it2=it->second->Nodes().begin();
459			it2!=it->second->Nodes().end();it2++)
460			{
461			int id=it2->second->Id();
462			Node * nodeInGraph = GetNode(id);
463			if (nodeInGraph != it2->second)
464			std::cerr << "Error: The Node "<<id<<" of arc "<<it->first<<"is not referenced in the graph"<<std::endl;
465			}
466			}
467
468			// * * each node of each arc must reference this arc
469			for (HypergraphLib::Graph::MapNodesById::const_iterator it=GetNodes().begin();
470			it != GetNodes().end(); it++)
471			{
472			for (HypergraphLib::Node::MultimapArcsById::const_iterator it2=it->second->IncidentArcs().begin();
473			it2!=it->second->IncidentArcs().end();it2++)
474			{
475			int nodeC=it2->second->NodeCount(it->first);
476			int arcC=it->second->ArcCount(it2->first);
477			if (nodeC != arcC)
478			{
479			std::cerr << "Error: the Arc->NodeCount("<<it->first<<")="<<nodeC<<""<<std::endl;
480			std::cerr << "is not equal to the Node->ArcCount("<<it2->first<<")="<<arcC<<""<<std::endl;
481			}
482			}
483			}
484
485			// * * each incident arc of each node must reference this node
486
487			for (HypergraphLib::Graph::MapArcsById::const_iterator it2=GetArcs().begin();
488			it2 != GetArcs().end(); it2++)
489			{
490			for (HypergraphLib::Arc::MultimapNodesById::const_iterator it=it2->second->Nodes().begin();
491			it!=it2->second->Nodes().end();it++)
492			{
493			int nodeC=it2->second->NodeCount(it->first);
494			int arcC=it->second->ArcCount(it2->first);
495			if (nodeC != arcC)
496			{
497			std::cerr << "Error: the Arc->NodeCount("<<it->first<<")="<<nodeC<<""<<std::endl;
498			std::cerr << "is not equal to the Node->ArcCount("<<it2->first<<")="<<arcC<<""<<std::endl;
499			}
500			}
501			}
502			}
503
504			bool Graph::IsCycle() const
505			{
506			if (_nodes.size() != _arcs.size())
507			return false;
508			for (HypergraphLib::Graph::MapArcsById::const_iterator it2=GetArcs().begin();
509			it2 != GetArcs().end(); it2++)
510			if (it2->second->Rank() != 2)
511			return false;
512			return true;
513			}
514
515
516			bool Graph::IsCycle (const std::vector < Node * > & __nodes) const
517			{
518			if (__nodes.size () < 2 ) return false;
519
520			//unsigned nb_nodes_having_2_neighbours = 0;
521
522			const unsigned N = __nodes.size();
523
524			for (unsigned i=0; i<N; i++)
525			{
526			Node * n = __nodes[i];
527			//unsigned nb_neighbours=0;
528			int i_previous = i-1;
529			if (i_previous < 0) i_previous += N;
530			Node *n_previous = __nodes[i_previous];
531			int i_next = (i+1)%N;
532			Node *n_next = __nodes[i_next];
533
534			Arc * arc1 = n->IsAdjacentToNode(n_next);
535			Arc * arc2 = n->IsAdjacentToNode(n_previous);
536
537			if ( arc1 && arc2 && arc1 != arc2 )
538			{
539			if (n_next == n_previous)
540			{
541			if (n->GetNbArcsToNode(n_previous) < 2)
542			return false;
543			else
544			continue;
545			}
546			}
547			else
548			return false;
549			}
550			return true;
551			}
552
553			}
554