Changeset 189 for trunk

Timestamp:

02/05/10 16:03:25 (14 years ago)

Author:

bernard

Message:

debut d'implementation de la fonction setMacroGraph

Location:

trunk/yao

Files:

• bin/Yao9Generator (modified) (previous)
• src/YAOObjects/Order.cpp (modified) (2 diffs)
• src/YAOObjects/Order.hpp (modified) (1 diff)

trunk/yao/src/YAOObjects/Order.cpp

@@ -768 +768 @@
                 for(int i = 0; i < outerComp.size(); i++) Read3D(i);
 
+                setMacroGraph();
+
                 break;
 
@@ -2928 +2930 @@
 };
         
+void Order::setMacroGraph() {
+
+
+        // Data structure used by boost to register informations on component search 
+        // -------------------------------------------------------------------------
+
+        std::vector<int> componentList;
+
+        // Resizign the structure : one element for each main graph vertex
+        // ----------------------------------------------------------------
+
+        componentList.resize(boost::num_vertices(myGraph));
+
+        // Data strcture used by boost to perform component search
+        // -------------------------------------------------------
+
+        std::vector<vertexDescriptor> verticesDiscoverList(boost::num_vertices(myGraph));
+
+        // Perform a component search on the main graph 
+        // --------------------------------------------
+
+        boost::strong_components(myGraph, &componentList[0], boost::root_map(&verticesDiscoverList[0]));
+
+        // Register vertices properties on affected components
+        // ---------------------------------------------------
+
+        for(int i = 0; i < componentList.size(); i++) put(get(boost::vertex_affected_comp_t(), myGraph), i, componentList[i]);
+
+        // Getting the number of components 
+        // --------------------------------
+
+        int nbComponents = *max_element(componentList.begin(), componentList.end()) + 1;
+
+        // Graph that will be the reduced graph from the main graph 
+        // --------------------------------------------------------
+
+        myGraphType cfcGraph;
+
+        // Reduce the main graph and set up the reduced graph 
+        // --------------------------------------------------
+
+        reduceGraph(myGraph, cfcGraph, nbComponents);
+
+        // Data structure used by boost to register informations on topological sort 
+        // -------------------------------------------------------------------------
+
+        std::deque<int> topoOrder;
+
+        // Do not perform a topological sort if there is just one vertex in the graph 
+        // --------------------------------------------------------------------------
+
+        if(boost::num_vertices(cfcGraph) > 1) {
+
+        // Perform a topological sort on the reduced graph
+        // -----------------------------------------------
+
+        boost::topological_sort(cfcGraph, std::front_inserter(topoOrder), boost::vertex_index_map(boost::identity_property_map()));
+
+        // Sort the vertices affected components accordignly to the topological order 
+        // --------------------------------------------------------------------------
+
+        for(int noComponent = 0; noComponent < topoOrder.size(); noComponent++)
+                                        put(get(boost::vertex_affected_comp_t(), cfcGraph), noComponent, topoOrder[noComponent]);
+        }
+
+};
+
 
 

trunk/yao/src/YAOObjects/Order.hpp

@@ -372 +372 @@
         void keepComponent(int noComp, myGraphType& upperGraph);
 
+        /**
+        * Function that set-up a graph that will be used to perform the final groupping procedure 
+        *
+        * This function create a graph composed by macro-vertices from the main graph : every vertex of this graph
+        * is made from a component of the main graph and every edge of this graph is an edge that link two components
+        * of the main graph. 
+        * 
+        * As the component Id affected to each vertex must match the component structure "outerComp" (because many 
+        * relevant informations needed by the groupping procedure will be found inside the component structures), it 
+        * is very important to keep the correct component Id in the "vertex_affected_comp" property of each macro-vertex. 
+        * To keep the referencing between structures and macro-vertices, the same operations than those performed on the
+        * main graph inside the setOuter() function are performed here. 
+        * 
+        * As every vertex have an affected component (even a single vertex), this graph embed all the relevant informations
+        * to perform the final groupping procedure :
+        *
+        *       - Informations on edges linking components are already carried by the graph.
+        *       - Informations on components will be naturally found by looking at the tructures indexed by the macro-vertices
+        *         "vertex_affected_comp" property
+        *
+        * It could seems to be an overhead to perform the component search and the sorting on the main graph because it have already
+        * been done inside the setOuter() procedure but this is just a first step : 3D components,  2D components and 1D components
+        * should be mixed all together in the same graph, so several operations, not yet implemented, will be needed. 
+        */
+        void setMacroGraph();
+
+
+
         // -- Fonction de gestion des signes et des axes --