ffasp/ComponentFinder.h at master · mushthofa/ffasp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/***************************************************************************
 *   Copyright (C) 2009 by Mushthofa   								*
 *   unintendedchoice@gmail.com   									*
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/


#ifndef _COMPONENTFINDER_H
#define _COMPONENTFINDER_H


#include <map>
#include <vector>
#include <iostream>

#include "AtomNode.h"


/**
 * @brief ComponentFinder.h
 *
 * Finds the components in a dependency graph
 *
 */
class ComponentFinder
{
	public:

		/**
	 * Single Vertex Type.
		 */
		typedef unsigned Vertex;

    		/**
		 * List of Vertices.
		 */
		typedef std::vector<Vertex> Vertices;

    		/**
		 * An Edge is a pair of Vertices.
		 */
		typedef std::pair<Vertex, Vertex> Edge;

    		/**
		 * List of Edges.
		 */
		typedef std::vector<Edge> Edges;

    		/**
		 * A ComponentIdx uniquely identifies a Component.
		 */

    		/**
		 * A ComponentAssignment associates a Vertex with a Component.
		 */


	     /**
		 * A ComponentList is a set of Vertices that belong to a single
		 * Component.
		 */
		typedef std::vector<Vertices> ComponentList;

		virtual ~ComponentFinder() {}

	protected:

    		/// Ctor.
		ComponentFinder()
		{ }

	public:


   		/**
		 * @brief Method for finding Strongly Connected Components.
		 */
		virtual void findStrongComponents(const std::vector<AtomNodePtr>&,
								    std::vector<std::vector<AtomNodePtr> >&)
		{ }

    		/**
		 * @brief For verbose and debugging.
		 */
		void dumpAssignment(const ComponentList&, std::ostream&) const;
};


/**
 * @brief Simple Component finder for testing purposes.
 *
 * This Component Finder puts every Vertex in a single WCC and finds no SCC.
 *
 */

class SimpleComponentFinder : public ComponentFinder
{
	public:

    		/// Ctor.
		SimpleComponentFinder()
		{ }
};

#endif