outil/src/hypergraphlib_components.cpp

#include "hypergraphlib_platform.h"

#include "hypergraphlib_components.h"
#include "hypergraphlib_dfs.h"
#include "hypergraphlib_graph.h"
#include "hypergraphlib_node.h"

/**
 * Find the strongly connected components of a graph
    // http://en.wikipedia.org/wiki/Strongly_connected_component


 STRONGLY-CONNECTED COMPONENTS (G)
 1 call DFS(G) to compute finishing times f[u] for each vertex u
 2 compute GT
 3 call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u]
 4 produce as output the vertices of each tree in the DFS forest formed in point 3 as a separate SCC.

 */
namespace HypergraphLib {

void FindSCC(Graph * __G, std::set < std::set < Node * > > & __components)
{
    std::map < int, Node * > unvisitedNodes = __G->GetNodes();

    while (unvisitedNodes.size())
    {
        std::set < Node * > depthFirstSearchNodes;
        dfs((unvisitedNodes.begin())->second, depthFirstSearchNodes);
        __components.insert ( depthFirstSearchNodes );
        for ( std::set < Node * >::const_iterator it  = depthFirstSearchNodes.begin();
                it != depthFirstSearchNodes.end();
                it++)
            unvisitedNodes.erase((*it)->Id());
    }
}

}

Revision:	1019
Committed:	Tue Jun 4 21:16:50 2019 UTC (6 years ago) by francois
File size:	1216 byte(s)
Log Message:	restructuration de magic outil est sorti de lib pour pouvoir etre utiliser en dehors de lib template est merge avec outil poly_occ et un sous projet de magic qui utilise le nouveau outil
#	User	Rev	Content
1	francois	481	#include "hypergraphlib_platform.h"
2	francois	283
3	francois	481	#include "hypergraphlib_components.h"
4			#include "hypergraphlib_dfs.h"
5			#include "hypergraphlib_graph.h"
6			#include "hypergraphlib_node.h"
7	francois	283
8			/**
9			* Find the strongly connected components of a graph
10			// http://en.wikipedia.org/wiki/Strongly_connected_component
11
12
13			STRONGLY-CONNECTED COMPONENTS (G)
14			1 call DFS(G) to compute finishing times f[u] for each vertex u
15			2 compute GT
16			3 call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u]
17			4 produce as output the vertices of each tree in the DFS forest formed in point 3 as a separate SCC.
18
19			*/
20			namespace HypergraphLib {
21
22			void FindSCC(Graph * __G, std::set < std::set < Node * > > & __components)
23			{
24			std::map < int, Node * > unvisitedNodes = __G->GetNodes();
25
26			while (unvisitedNodes.size())
27			{
28			std::set < Node * > depthFirstSearchNodes;
29			dfs((unvisitedNodes.begin())->second, depthFirstSearchNodes);
30			__components.insert ( depthFirstSearchNodes );
31			for ( std::set < Node * >::const_iterator it = depthFirstSearchNodes.begin();
32			it != depthFirstSearchNodes.end();
33			it++)
34			unvisitedNodes.erase((*it)->Id());
35			}
36	francois	102	}
37	foucault	176
38	francois	283	}
39