hypergraphlib_graph.cpp

Aller à la documentation de ce fichier.

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