outil/src/hypergraphlib_findcycles.cpp

#include "gestionversion.h"
#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:	283
Committed:	Tue Sep 13 21:11:20 2011 UTC (13 years, 8 months ago) by francois
Original Path:	*magic/lib/outil/src/HypergraphLib_FindCycles.cpp*
File size:	5355 byte(s)
Log Message:	structure de l'écriture
#	User	Rev	Content
1	francois	113	#include "gestionversion.h"
2	francois	283	#include "HypergraphLib_platform.h"
3
4			#include "HypergraphLib_FindCycles.h"
5			#include "HypergraphLib_Node.h"
6			#include "HypergraphLib_Arc.h"
7			#include "HypergraphLib_Graph.h"
8			#include <algorithm>
9			#include <iostream>
10
11			#undef DEBUG
12
13			namespace HypergraphLib {
14
15			int find_n( std::vector < Node * > & __depthFirstSearchNodes, Node *__n)
16			{
17			for (unsigned i=0; i<__depthFirstSearchNodes.size(); i++)
18			if (__depthFirstSearchNodes[i] == __n)
19			return i;
20			return -1;
21	francois	102	}
22	francois	283
23			int find_n( std::vector < Arc * > & __depthFirstSearchArcs, Arc *__a)
24			{
25			for (unsigned i=0; i<__depthFirstSearchArcs.size(); i++)
26			if (__depthFirstSearchArcs[i] == __a)
27			return i;
28			return -1;
29			}
30
31			/**
32			* returns :
33			* -2 if the cycle does not exist
34			* -1 if the cycle exist
35			* j if the cycle at index j is longer than the new one
36			*/
37
38			int does_cycle_already_exist( const std::vector < std::vector < Node * > > & cycles, const std::vector < Node * > & cycle)
39			{
40			for (unsigned i = 0; i < cycles.size(); i++)
41			{
42			for (unsigned j=0; j<cycles[i].size(); j++)
43			{
44			std::vector < Node * >::const_iterator it = std::find(cycle.begin(), cycle.end(), cycles[i][j]);
45			if (it == cycle.end())
46			goto not_equal_cycles;
47			}
48			if (cycles[i].size() == cycle.size())
49			{
50			#ifdef DEBUG
51			std::cout << "Cycle \"";
52			for (int j=0; j<cycle.size(); j++)
53			std::cout << cycle[j]->Id() << ", ";
54			std::cout << "\" matches cycle ";
55			for (int j=0; j<cycles[i].size(); j++)
56			std::cout << cycles[i][j]->Id() << ", ";
57			std::cout << std::endl;
58			#endif
59			}
60			else if (cycles[i].size() > cycle.size())
61			{
62			#ifdef DEBUG
63			std::cout << "the candidate cycle \"";
64			for (int j=0; j<cycle.size(); j++)
65			std::cout << cycle[j]->Id() << ", ";
66			std::cout << "\" is shorter than the cycle \"";
67			for (int j=0; j<cycles[i].size(); j++)
68			std::cout << cycles[i][j]->Id() << ", ";
69			std::cout << "\"";
70			std::cout << std::endl;
71			#endif
72			return i;
73			}
74			else
75			{
76			#ifdef DEBUG
77			std::cout << "the candidate cycle \"";
78			for (int j=0; j<cycle.size(); j++)
79			std::cout << cycle[j]->Id() << ", ";
80			std::cout << "\" is longer than the cycle \"";
81			for (int j=0; j<cycles[i].size(); j++)
82			std::cout << cycles[i][j]->Id() << ", ";
83			std::cout << "\"";
84			std::cout << std::endl;
85			#endif
86			}
87			return -1;
88			not_equal_cycles:
89			continue;
90			}
91			#ifdef DEBUG
92			std::cout << "Cycle \"";
93			for (int j=0; j<cycle.size(); j++)
94			std::cout << cycle[j]->Id() << ", ";
95			std::cout << "\" is a new cycle "<< std::endl;
96			#endif
97
98			return -2;
99			}
100
101			void
102			dfsCycle(Node __n, std::vector < Node > & __depthFirstSearchNodes, std::vector< Arc * > & __depthFirstSearchArcs, std::vector < std::vector < Node * > > & cycles )
103			{
104			std::set < Node * > adj;
105			__n->AdjacentNodes( adj );
106			std::vector<Node*>::iterator it3;
107
108			//int pos_n;
109			if (__depthFirstSearchNodes.size() == 0)
110			__depthFirstSearchNodes.push_back(__n);
111
112			for ( Node::MultimapArcsById::iterator itIncidentArcs = __n->IncidentArcs().begin();
113			itIncidentArcs != __n->IncidentArcs().end();
114			itIncidentArcs++ )
115			{
116			Arc * incidentArc = itIncidentArcs->second;
117			for ( Arc::MultimapNodesById::iterator itAdjNodes = incidentArc->Nodes().begin();
118			itAdjNodes != incidentArc->Nodes().end();
119			itAdjNodes++)
120			{
121			Node * adjNode = itAdjNodes->second;
122			std::vector < Node * > tempPath = __depthFirstSearchNodes;
123			std::vector < Arc * > tempPathArcs = __depthFirstSearchArcs;
124
125			if (__n->Owner()->IsCycle(tempPath))
126			{
127			//std::vector < Node * > cycle;
128			//for (int i=0; i<tempPath.size(); i++)
129			// cycle.push_back(tempPath[i]);
130			int is_cycle_exists = does_cycle_already_exist(cycles, tempPath);
131			// if the cycle does not exists
132			if (is_cycle_exists == -2)
133			cycles.push_back(tempPath);
134			// if a shorter cycle exists : replace the long cycle with the short cycle
135			if (is_cycle_exists > 0)
136			{
137			cycles [is_cycle_exists] = tempPath;
138			}
139			//tempPath = __depthFirstSearchNodes;
140			}
141			else if ( find_n(__depthFirstSearchNodes, adjNode) == -1 && find_n(__depthFirstSearchArcs, incidentArc) == -1)
142			{
143			tempPath.push_back(adjNode);
144			tempPathArcs.push_back(incidentArc);
145			dfsCycle (adjNode, tempPath, tempPathArcs, cycles);
146			}
147			}
148			}
149			}
150
151
152			void
153			FindCycles(Graph * __G, std::vector < std::vector < Node * > > & cycles)
154			{
155			std::vector < Node * > depthFirstSearchNodes;
156			std::vector < Arc * > depthFirstSearchArcs;
157
158			GRAPH_FOR_EACH_NODE_CONST(__G, startNode)
159			{
160			depthFirstSearchNodes.clear();
161			dfsCycle (startNode->second, depthFirstSearchNodes, depthFirstSearchArcs, cycles);
162			}
163			}
164			}
165	francois	102