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
120
121
122
123
124
125
126
127
|
/****************************************************************************
**
** Copyright (C) 2021 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of Qt for Python.
**
** $QT_BEGIN_LICENSE:COMM$
**
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** $QT_END_LICENSE$
**
****************************************************************************/
#include "graph.h"
#include <QVector>
#include <QDebug>
#include <QSet>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <QFile>
struct Graph::GraphPrivate
{
enum Color { WHITE, GRAY, BLACK };
using Edges = QVector<QSet<int> >;
Edges edges;
GraphPrivate(int numNodes) : edges(numNodes)
{
}
void dfsVisit(int node, Graph::Indexes &result, QVector<Color> &colors) const
{
colors[node] = GRAY;
for (const auto &c : edges.at(node)) {
if (colors[c] == WHITE)
dfsVisit(c, result, colors);
else if (colors[c] == GRAY) // This is not a DAG!
return;
}
colors[node] = BLACK;
result.append(node);
}
};
Graph::Graph(int numNodes) : m_d(new GraphPrivate(numNodes))
{
}
Graph::~Graph()
{
delete m_d;
}
int Graph::nodeCount() const
{
return m_d->edges.size();
}
Graph::Indexes Graph::topologicalSort() const
{
const int nodeCount = Graph::nodeCount();
Indexes result;
result.reserve(nodeCount);
QVector<GraphPrivate::Color> colors(nodeCount, GraphPrivate::WHITE);
for (int i = 0; i < nodeCount; ++i) {
if (colors[i] == GraphPrivate::WHITE)
m_d->dfsVisit(i, result, colors);
}
if (result.size() == nodeCount)
std::reverse(result.begin(), result.end());
else
result.clear(); // Not a DAG!
return result;
}
bool Graph::containsEdge(int from, int to)
{
return m_d->edges[from].contains(to);
}
void Graph::addEdge(int from, int to)
{
Q_ASSERT(to < m_d->edges.size());
m_d->edges[from].insert(to);
}
void Graph::removeEdge(int from, int to)
{
m_d->edges[from].remove(to);
}
void Graph::dump() const
{
for (int i = 0; i < m_d->edges.size(); ++i) {
std::cout << i << " -> ";
std::copy(m_d->edges[i].begin(), m_d->edges[i].end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
}
void Graph::dumpDot(const QHash< int, QString >& nodeNames, const QString& fileName) const
{
QFile output(fileName);
if (!output.open(QIODevice::WriteOnly))
return;
QTextStream s(&output);
s << "digraph D {\n";
for (int i = 0; i < m_d->edges.size(); ++i) {
for (auto it = m_d->edges[i].cbegin(), end = m_d->edges[i].cend(); it != end; ++it)
s << '"' << nodeNames[i] << "\" -> \"" << nodeNames[*it] << "\"\n";
}
s << "}\n";
}
|
