outil/src/hypergraphlib_filaments.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_filaments.cpp
//####//
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//    COPYRIGHT 2000-2024
//####//  jeu 13 jun 2024 11:54:00 EDT
//####//------------------------------------------------------------
//####//------------------------------------------------------------
#include <stdlib.h>
#include "hypergraphlib_platform.h"

#include "hypergraphlib_graph.h"
#include "hypergraphlib_node.h"
#include "hypergraphlib_arc.h"

#include <set>
#include <vector>
#include <map>


/**
 * Algorithme de d�composition d'un graphe en filaments
 */

namespace HypergraphLib {

HYPERGRAPHLIB_ITEM void
Filaments ( Graph * G, std::vector < std::vector < int > > & __filaments )
{
    std::set <int> visited;
    std::set <int> next;
    std::vector <int> filament;
    std::set <int> unvisited;
    std::set <int> adjacentNodes;

    // Initialize the set of unvisited nodes
    for (Graph::MapNodesById::const_iterator itNodes = G->GetNodes().begin();
            itNodes != G->GetNodes().end();
            itNodes++ )
    {
        unvisited.insert (itNodes->first);
    }

    while (unvisited.size() > 0)
    {
        Node * N = G->GetNode(*(unvisited.begin()));
        for (std::set<int>::const_iterator itAN = unvisited.begin();
                itAN != unvisited.end();
                itAN++ )
        {
            Node * N2 = G->GetNode(*itAN);
            if (N2->IncidentArcs().size() == 1)
            {
                N = N2;
                break;
            }
        }

        visited.insert(N->Id());
        unvisited.erase(unvisited.find(N->Id()));
        next.clear();
        adjacentNodes.clear();
        N->AdjacentNodes(adjacentNodes);
        for (std::set<int>::const_iterator itAN = adjacentNodes.begin();
                itAN != adjacentNodes.end();
                itAN++ )
        {
            if ( visited.find (*itAN) == visited.end() )
            {
                next.insert (*itAN);
                break;
            }
        }
        filament.clear();
        filament.push_back (N->Id());

        while (next.size() > 0)
        {
            N = G->GetNode(*(next.begin()));
            visited.insert(N->Id());
            unvisited.erase(unvisited.find(N->Id()));
            adjacentNodes.clear();
            next.clear();
            filament.push_back (N->Id());

            N->AdjacentNodes(adjacentNodes);
            for (std::set<int>::const_iterator itAN = adjacentNodes.begin();
                    itAN != adjacentNodes.end();
                    itAN++ )
            {
                if ( visited.find (*itAN) == visited.end() )
                {
                    int count_filament_adjacency = 0;
                    std::vector<int>::const_iterator it_fil = filament.begin();
                    bool is_adjacent_to_start=false;
                    bool is_adjacent_to_end=false;
                    Node * fN=NULL;

                    it_fil = filament.begin();
                    fN = G->GetNode (*it_fil);
                    is_adjacent_to_start = fN->IsAdjacentToNode(*itAN);


                    it_fil = filament.end();
                    it_fil--;
                    fN = G->GetNode (*it_fil);
                    is_adjacent_to_end = fN->IsAdjacentToNode(*itAN);

                    for ( it_fil = filament.begin();
                            it_fil != filament.end(); it_fil++)
                    {
                        fN = G->GetNode (*it_fil);
                        if (fN->IsAdjacentToNode(*itAN))
                            count_filament_adjacency++;
                    }
                    it_fil = filament.end();
                    it_fil--;
                    it_fil = filament.begin();

                    bool is_not_T = true;
                    if ( is_adjacent_to_end && is_adjacent_to_start)
                    {

                        for ( it_fil = filament.begin();
                                it_fil != filament.end(); it_fil++)
                        {
                            fN = G->GetNode (*it_fil);
                            for ( Node::MultimapArcsById::const_iterator itArcs = fN->IncidentArcs().begin();
                                    itArcs !=  fN->IncidentArcs().end();
                                    itArcs++ )
                            {
                                Arc * arc = itArcs->second;

                                if ( arc->Nodes().find(*itAN) != arc->Nodes().end()
                                        && arc->Nodes().find(filament[0]) != arc->Nodes().end()
                                        && arc->Nodes().find(filament[filament.size()-1]) != arc->Nodes().end() )
                                {
                                    is_not_T = false;
                                }
                            }
                        }

                    }

                    if (count_filament_adjacency == 1 || ( is_adjacent_to_end && is_adjacent_to_start && is_not_T)  )
                    {
                        next.insert (*itAN);
                        break;
                    }
                }
            }
        }
        __filaments.push_back(filament);
    }

}
}

Revision:	1156
Committed:	Thu Jun 13 22:02:48 2024 UTC (14 months, 2 weeks ago) by francois
File size:	5997 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_filaments.cpp
15			//####//
16			//####//------------------------------------------------------------
17			//####//------------------------------------------------------------
18			//####// COPYRIGHT 2000-2024
19			//####// jeu 13 jun 2024 11:54:00 EDT
20			//####//------------------------------------------------------------
21			//####//------------------------------------------------------------
22	francois	313	#include <stdlib.h>
23	francois	481	#include "hypergraphlib_platform.h"
24	francois	283
25	francois	481	#include "hypergraphlib_graph.h"
26			#include "hypergraphlib_node.h"
27			#include "hypergraphlib_arc.h"
28	francois	283
29			#include <set>
30			#include <vector>
31			#include <map>
32
33
34			/**
35			* Algorithme de d�composition d'un graphe en filaments
36			*/
37
38			namespace HypergraphLib {
39
40			HYPERGRAPHLIB_ITEM void
41			Filaments ( Graph * G, std::vector < std::vector < int > > & __filaments )
42			{
43			std::set <int> visited;
44			std::set <int> next;
45			std::vector <int> filament;
46			std::set <int> unvisited;
47			std::set <int> adjacentNodes;
48
49			// Initialize the set of unvisited nodes
50			for (Graph::MapNodesById::const_iterator itNodes = G->GetNodes().begin();
51			itNodes != G->GetNodes().end();
52			itNodes++ )
53			{
54			unvisited.insert (itNodes->first);
55			}
56
57			while (unvisited.size() > 0)
58			{
59			Node * N = G->GetNode(*(unvisited.begin()));
60			for (std::set<int>::const_iterator itAN = unvisited.begin();
61			itAN != unvisited.end();
62			itAN++ )
63			{
64			Node * N2 = G->GetNode(*itAN);
65			if (N2->IncidentArcs().size() == 1)
66			{
67			N = N2;
68			break;
69			}
70			}
71
72			visited.insert(N->Id());
73			unvisited.erase(unvisited.find(N->Id()));
74			next.clear();
75			adjacentNodes.clear();
76			N->AdjacentNodes(adjacentNodes);
77			for (std::set<int>::const_iterator itAN = adjacentNodes.begin();
78			itAN != adjacentNodes.end();
79			itAN++ )
80			{
81			if ( visited.find (*itAN) == visited.end() )
82			{
83			next.insert (*itAN);
84			break;
85			}
86			}
87			filament.clear();
88			filament.push_back (N->Id());
89
90			while (next.size() > 0)
91			{
92			N = G->GetNode(*(next.begin()));
93			visited.insert(N->Id());
94			unvisited.erase(unvisited.find(N->Id()));
95			adjacentNodes.clear();
96			next.clear();
97			filament.push_back (N->Id());
98
99			N->AdjacentNodes(adjacentNodes);
100			for (std::set<int>::const_iterator itAN = adjacentNodes.begin();
101			itAN != adjacentNodes.end();
102			itAN++ )
103			{
104			if ( visited.find (*itAN) == visited.end() )
105			{
106			int count_filament_adjacency = 0;
107			std::vector<int>::const_iterator it_fil = filament.begin();
108			bool is_adjacent_to_start=false;
109			bool is_adjacent_to_end=false;
110			Node * fN=NULL;
111
112			it_fil = filament.begin();
113			fN = G->GetNode (*it_fil);
114			is_adjacent_to_start = fN->IsAdjacentToNode(*itAN);
115
116
117			it_fil = filament.end();
118			it_fil--;
119			fN = G->GetNode (*it_fil);
120			is_adjacent_to_end = fN->IsAdjacentToNode(*itAN);
121
122			for ( it_fil = filament.begin();
123			it_fil != filament.end(); it_fil++)
124			{
125			fN = G->GetNode (*it_fil);
126			if (fN->IsAdjacentToNode(*itAN))
127			count_filament_adjacency++;
128			}
129			it_fil = filament.end();
130			it_fil--;
131			it_fil = filament.begin();
132
133			bool is_not_T = true;
134			if ( is_adjacent_to_end && is_adjacent_to_start)
135			{
136
137			for ( it_fil = filament.begin();
138			it_fil != filament.end(); it_fil++)
139			{
140			fN = G->GetNode (*it_fil);
141			for ( Node::MultimapArcsById::const_iterator itArcs = fN->IncidentArcs().begin();
142			itArcs != fN->IncidentArcs().end();
143			itArcs++ )
144			{
145			Arc * arc = itArcs->second;
146
147			if ( arc->Nodes().find(*itAN) != arc->Nodes().end()
148			&& arc->Nodes().find(filament[0]) != arc->Nodes().end()
149			&& arc->Nodes().find(filament[filament.size()-1]) != arc->Nodes().end() )
150			{
151			is_not_T = false;
152			}
153			}
154			}
155
156			}
157
158			if (count_filament_adjacency == 1 \|\| ( is_adjacent_to_end && is_adjacent_to_start && is_not_T) )
159			{
160			next.insert (*itAN);
161			break;
162			}
163			}
164			}
165			}
166			__filaments.push_back(filament);
167			}
168
169	francois	102	}
170	francois	283	}
171	francois	313