outil/src/hypergraphlib_graph.cpp

#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);
        }

        _arcs.erase ( it );
        delete tempArc;

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