outil/src/hypergraphlib_findcycles.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_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;
}

/**
 * returns :
 * -2 if the cycle does not exist
 * -1 if the cycle exist
 * j if the cycle at index j is longer than the new one
 */

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

Revision:	1156
Committed:	Thu Jun 13 22:02:48 2024 UTC (14 months, 2 weeks ago) by francois
File size:	6579 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_findcycles.cpp
15			//####//
16			//####//------------------------------------------------------------
17			//####//------------------------------------------------------------
18			//####// COPYRIGHT 2000-2024
19			//####// jeu 13 jun 2024 11:53:59 EDT
20			//####//------------------------------------------------------------
21			//####//------------------------------------------------------------
22	francois	481	#include "hypergraphlib_platform.h"
23	francois	102
24	francois	481	#include "hypergraphlib_findcycles.h"
25			#include "hypergraphlib_node.h"
26			#include "hypergraphlib_arc.h"
27			#include "hypergraphlib_graph.h"
28			#include <algorithm>
29			#include <iostream>
30
31			#undef DEBUG
32
33			namespace HypergraphLib {
34
35			int find_n( std::vector < Node * > & __depthFirstSearchNodes, Node *__n)
36			{
37			for (unsigned i=0; i<__depthFirstSearchNodes.size(); i++)
38			if (__depthFirstSearchNodes[i] == __n)
39			return i;
40			return -1;
41			}
42
43			int find_n( std::vector < Arc * > & __depthFirstSearchArcs, Arc *__a)
44			{
45			for (unsigned i=0; i<__depthFirstSearchArcs.size(); i++)
46			if (__depthFirstSearchArcs[i] == __a)
47			return i;
48			return -1;
49			}
50
51			/**
52			* returns :
53			* -2 if the cycle does not exist
54			* -1 if the cycle exist
55			* j if the cycle at index j is longer than the new one
56			*/
57
58			int does_cycle_already_exist( const std::vector < std::vector < Node * > > & cycles, const std::vector < Node * > & cycle)
59			{
60			for (unsigned i = 0; i < cycles.size(); i++)
61			{
62			for (unsigned j=0; j<cycles[i].size(); j++)
63			{
64			std::vector < Node * >::const_iterator it = std::find(cycle.begin(), cycle.end(), cycles[i][j]);
65			if (it == cycle.end())
66			goto not_equal_cycles;
67			}
68			if (cycles[i].size() == cycle.size())
69			{
70			#ifdef DEBUG
71			std::cout << "Cycle \"";
72			for (int j=0; j<cycle.size(); j++)
73			std::cout << cycle[j]->Id() << ", ";
74			std::cout << "\" matches cycle ";
75			for (int j=0; j<cycles[i].size(); j++)
76			std::cout << cycles[i][j]->Id() << ", ";
77			std::cout << std::endl;
78			#endif
79			}
80			else if (cycles[i].size() > cycle.size())
81			{
82			#ifdef DEBUG
83			std::cout << "the candidate cycle \"";
84			for (int j=0; j<cycle.size(); j++)
85			std::cout << cycle[j]->Id() << ", ";
86			std::cout << "\" is shorter than the cycle \"";
87			for (int j=0; j<cycles[i].size(); j++)
88			std::cout << cycles[i][j]->Id() << ", ";
89			std::cout << "\"";
90			std::cout << std::endl;
91			#endif
92			return i;
93			}
94			else
95			{
96			#ifdef DEBUG
97			std::cout << "the candidate cycle \"";
98			for (int j=0; j<cycle.size(); j++)
99			std::cout << cycle[j]->Id() << ", ";
100			std::cout << "\" is longer than the cycle \"";
101			for (int j=0; j<cycles[i].size(); j++)
102			std::cout << cycles[i][j]->Id() << ", ";
103			std::cout << "\"";
104			std::cout << std::endl;
105			#endif
106			}
107			return -1;
108			not_equal_cycles:
109			continue;
110			}
111			#ifdef DEBUG
112			std::cout << "Cycle \"";
113			for (int j=0; j<cycle.size(); j++)
114			std::cout << cycle[j]->Id() << ", ";
115			std::cout << "\" is a new cycle "<< std::endl;
116			#endif
117
118			return -2;
119			}
120
121			void
122			dfsCycle(Node __n, std::vector < Node > & __depthFirstSearchNodes, std::vector< Arc * > & __depthFirstSearchArcs, std::vector < std::vector < Node * > > & cycles )
123			{
124			std::set < Node * > adj;
125			__n->AdjacentNodes( adj );
126			std::vector<Node*>::iterator it3;
127
128			//int pos_n;
129			if (__depthFirstSearchNodes.size() == 0)
130			__depthFirstSearchNodes.push_back(__n);
131
132			for ( Node::MultimapArcsById::iterator itIncidentArcs = __n->IncidentArcs().begin();
133			itIncidentArcs != __n->IncidentArcs().end();
134			itIncidentArcs++ )
135			{
136			Arc * incidentArc = itIncidentArcs->second;
137			for ( Arc::MultimapNodesById::iterator itAdjNodes = incidentArc->Nodes().begin();
138			itAdjNodes != incidentArc->Nodes().end();
139			itAdjNodes++)
140			{
141			Node * adjNode = itAdjNodes->second;
142			std::vector < Node * > tempPath = __depthFirstSearchNodes;
143			std::vector < Arc * > tempPathArcs = __depthFirstSearchArcs;
144
145			if (__n->Owner()->IsCycle(tempPath))
146			{
147			//std::vector < Node * > cycle;
148			//for (int i=0; i<tempPath.size(); i++)
149			// cycle.push_back(tempPath[i]);
150			int is_cycle_exists = does_cycle_already_exist(cycles, tempPath);
151			// if the cycle does not exists
152			if (is_cycle_exists == -2)
153			cycles.push_back(tempPath);
154			// if a shorter cycle exists : replace the long cycle with the short cycle
155			if (is_cycle_exists > 0)
156			{
157			cycles [is_cycle_exists] = tempPath;
158			}
159			//tempPath = __depthFirstSearchNodes;
160			}
161			else if ( find_n(__depthFirstSearchNodes, adjNode) == -1 && find_n(__depthFirstSearchArcs, incidentArc) == -1)
162			{
163			tempPath.push_back(adjNode);
164			tempPathArcs.push_back(incidentArc);
165			dfsCycle (adjNode, tempPath, tempPathArcs, cycles);
166			}
167			}
168			}
169			}
170
171
172			void
173			FindCycles(Graph * __G, std::vector < std::vector < Node * > > & cycles)
174			{
175			std::vector < Node * > depthFirstSearchNodes;
176			std::vector < Arc * > depthFirstSearchArcs;
177
178			GRAPH_FOR_EACH_NODE_CONST(__G, startNode)
179			{
180			depthFirstSearchNodes.clear();
181			dfsCycle (startNode->second, depthFirstSearchNodes, depthFirstSearchArcs, cycles);
182			}
183			}
184			}
185