-
Notifications
You must be signed in to change notification settings - Fork 20
/
max_acyclic_subgraph.h
86 lines (73 loc) · 2.34 KB
/
max_acyclic_subgraph.h
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
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libcola - A library providing force-directed network layout using the
* stress-majorization method subject to separation constraints.
*
* Copyright (C) 2006-2008 Monash University
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library 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
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library in the file LICENSE; if not,
* write to the Free Software Foundation, Inc., 59 Temple Place,
* Suite 330, Boston, MA 02111-1307 USA
*
*/
#ifndef MAX_ACYCLIC_SUBGRAPH_H
#define MAX_ACYCLIC_SUBGRAPH_H
#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include "libcola/cola.h"
namespace max_acyclic_subgraph {
typedef std::vector<cola::Edge> Edges;
class Node {
public:
unsigned id;
Edges incoming;
Edges outgoing;
Node(unsigned id) { this->id = id; }
// copy constructor
Node(const Node &old) {
#ifdef COPY_CONS_DEBUG
std::cout << "Node copy constructor(" << old.id << ")" << endl;
#endif
this->id = old.id;
this->incoming = old.incoming;
this->outgoing = old.outgoing;
}
~Node() {}
};
typedef std::vector<Node *> NodeList;
class MaxAcyclicSubgraph {
public:
MaxAcyclicSubgraph(unsigned numVertices, Edges *edges);
~MaxAcyclicSubgraph();
Edges *find_subgraph();
void mod_graph(unsigned numVertices, Edges *edges);
unsigned getV() { return this->V; }
Edges *getEdges() { return this->edges; }
private:
// attributes
unsigned V;
Edges *edges;
// internally used variables.
NodeList *nodes; // the nodes in the graph
// internally used methods
void make_matrix();
bool find_node(unsigned k);
NodeList *copy_graph();
void printNodes(NodeList*& n);
};
}
#endif