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
#	Content
1	//####//------------------------------------------------------------
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	#include "hypergraphlib_platform.h"
23
24	#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