outil/src/hypergraphlib_graph.cpp

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