hypergraphlib_filaments.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_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>
 
 
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);
    }
 
}
}