hypergraphlib_findcycles.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_findcycles.cpp
//####//
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//    COPYRIGHT 2000-2024
//####//  jeu 13 jun 2024 11:53:59 EDT
//####//------------------------------------------------------------
//####//------------------------------------------------------------
#include "hypergraphlib_platform.h"
 
#include "hypergraphlib_findcycles.h"
#include "hypergraphlib_node.h"
#include "hypergraphlib_arc.h"
#include "hypergraphlib_graph.h"
#include <algorithm>
#include <iostream>
 
#undef DEBUG
 
namespace HypergraphLib {
 
int find_n( std::vector < Node * > & __depthFirstSearchNodes, Node *__n)
{
    for (unsigned i=0; i<__depthFirstSearchNodes.size(); i++)
        if (__depthFirstSearchNodes[i] == __n)
            return i;
    return -1;
}
 
int find_n( std::vector < Arc * > & __depthFirstSearchArcs, Arc *__a)
{
    for (unsigned i=0; i<__depthFirstSearchArcs.size(); i++)
        if (__depthFirstSearchArcs[i] == __a)
            return i;
    return -1;
}
 
int does_cycle_already_exist( const std::vector < std::vector < Node * > > & cycles, const std::vector < Node * > & cycle)
{
    for (unsigned i = 0; i < cycles.size(); i++)
    {
        for (unsigned j=0; j<cycles[i].size(); j++)
        {
            std::vector < Node * >::const_iterator it = std::find(cycle.begin(), cycle.end(), cycles[i][j]);
            if (it == cycle.end())
                goto not_equal_cycles;
        }
        if (cycles[i].size() == cycle.size())
        {
#ifdef DEBUG
            std::cout << "Cycle \"";
            for (int j=0; j<cycle.size(); j++)
                std::cout << cycle[j]->Id() << ", ";
            std::cout << "\" matches cycle ";
            for (int j=0; j<cycles[i].size(); j++)
                std::cout << cycles[i][j]->Id() << ", ";
            std::cout << std::endl;
#endif
        }
        else if (cycles[i].size() > cycle.size())
        {
#ifdef DEBUG
            std::cout << "the candidate cycle \"";
            for (int j=0; j<cycle.size(); j++)
                std::cout << cycle[j]->Id() << ", ";
            std::cout << "\" is shorter than the cycle \"";
            for (int j=0; j<cycles[i].size(); j++)
                std::cout << cycles[i][j]->Id() << ", ";
            std::cout << "\"";
            std::cout << std::endl;
#endif
            return i;
        }
        else
        {
#ifdef DEBUG
            std::cout << "the candidate cycle \"";
            for (int j=0; j<cycle.size(); j++)
                std::cout << cycle[j]->Id() << ", ";
            std::cout << "\" is longer than the cycle \"";
            for (int j=0; j<cycles[i].size(); j++)
                std::cout << cycles[i][j]->Id() << ", ";
            std::cout << "\"";
            std::cout << std::endl;
#endif
        }
        return -1;
not_equal_cycles:
        continue;
    }
#ifdef DEBUG
    std::cout << "Cycle \"";
    for (int j=0; j<cycle.size(); j++)
        std::cout << cycle[j]->Id() << ", ";
    std::cout << "\" is a new cycle "<< std::endl;
#endif
 
    return -2;
}
 
void
dfsCycle(Node *__n, std::vector < Node * > & __depthFirstSearchNodes, std::vector< Arc * > & __depthFirstSearchArcs, std::vector < std::vector < Node * > > & cycles )
{
    std::set < Node * > adj;
    __n->AdjacentNodes( adj );
    std::vector<Node*>::iterator  it3;
 
    //int pos_n;
    if (__depthFirstSearchNodes.size() == 0)
        __depthFirstSearchNodes.push_back(__n);
 
    for ( Node::MultimapArcsById::iterator itIncidentArcs = __n->IncidentArcs().begin();
            itIncidentArcs != __n->IncidentArcs().end();
            itIncidentArcs++ )
    {
        Arc * incidentArc = itIncidentArcs->second;
        for ( Arc::MultimapNodesById::iterator itAdjNodes = incidentArc->Nodes().begin();
                itAdjNodes != incidentArc->Nodes().end();
                itAdjNodes++)
        {
            Node * adjNode = itAdjNodes->second;
            std::vector < Node * > tempPath = __depthFirstSearchNodes;
            std::vector < Arc * > tempPathArcs = __depthFirstSearchArcs;
 
            if (__n->Owner()->IsCycle(tempPath))
            {
                //std::vector < Node * > cycle;
                //for (int i=0; i<tempPath.size(); i++)
                //    cycle.push_back(tempPath[i]);
                int is_cycle_exists = does_cycle_already_exist(cycles, tempPath);
                // if the cycle does not exists
                if (is_cycle_exists == -2)
                    cycles.push_back(tempPath);
                // if a shorter cycle exists : replace the long cycle with the short cycle
                if (is_cycle_exists > 0)
                {
                    cycles [is_cycle_exists] = tempPath;
                }
                //tempPath = __depthFirstSearchNodes;
            }
            else if ( find_n(__depthFirstSearchNodes, adjNode) == -1 && find_n(__depthFirstSearchArcs, incidentArc) == -1)
            {
                tempPath.push_back(adjNode);
                tempPathArcs.push_back(incidentArc);
                dfsCycle (adjNode, tempPath, tempPathArcs, cycles);
            }
        }
    }
}
 
 
void
FindCycles(Graph * __G, std::vector < std::vector < Node * > > & cycles)
{
    std::vector < Node * > depthFirstSearchNodes;
    std::vector < Arc * > depthFirstSearchArcs;
 
    GRAPH_FOR_EACH_NODE_CONST(__G, startNode)
    {
        depthFirstSearchNodes.clear();
        dfsCycle (startNode->second, depthFirstSearchNodes, depthFirstSearchArcs, cycles);
    }
}
}