aGrUM
3.3.2
a C++ library for (probabilistic) graphical models
Toggle main menu visibility
cycleDetection_tpl.h
Go to the documentation of this file.
1
/****************************************************************************
2
* This file is part of the aGrUM/pyAgrum library. *
3
* *
4
* Copyright (c) 2005-2026 by *
5
* - Pierre-Henri WUILLEMIN(_at_LIP6) *
6
* - Christophe GONZALES(_at_AMU) *
7
* *
8
* The aGrUM/pyAgrum library is free software; you can redistribute it *
9
* and/or modify it under the terms of either : *
10
* *
11
* - the GNU Lesser General Public License as published by *
12
* the Free Software Foundation, either version 3 of the License, *
13
* or (at your option) any later version, *
14
* - the MIT license (MIT), *
15
* - or both in dual license, as here. *
16
* *
17
* (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18
* *
19
* This aGrUM/pyAgrum library is distributed in the hope that it will be *
20
* useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21
* INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22
* FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26
* OTHER DEALINGS IN THE SOFTWARE. *
27
* *
28
* See LICENCES for more details. *
29
* *
30
* SPDX-FileCopyrightText: Copyright 2005-2026 *
31
* - Pierre-Henri WUILLEMIN(_at_LIP6) *
32
* - Christophe GONZALES(_at_AMU) *
33
* SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34
* *
35
* Contact : info_at_agrum_dot_org *
36
* homepage : http://agrum.gitlab.io *
37
* gitlab : https://gitlab.com/agrumery/agrum *
38
* *
39
****************************************************************************/
40
41
42
#pragma once
43
44
#include <
agrum/base/graphs/algorithms/generic/cycleDetection.h
>
45
46
namespace
gum::graph
{
47
48
template
< GUM_DiGraphable G >
49
Sequence< NodeId >
topologicalOrder
(
const
G& g) {
50
if
(g.empty())
return
{};
51
52
NodeProperty< Size >
indegree;
53
std::vector< NodeId > border;
54
border.reserve(g.size() / 2);
55
56
for
(
const
auto
node: g.nodes()) {
57
const
auto
& par = g.parents(node);
58
indegree.
insert
(node, par.size());
59
if
(par.empty()) border.push_back(node);
60
}
61
62
if
(border.empty())
63
GUM_ERROR
(
InvalidDirectedCycle
,
"cycles prevent the creation of a topological ordering."
)
64
65
Sequence< NodeId >
result;
66
while
(!border.empty()) {
67
const
NodeId
root = border.back();
68
border.pop_back();
69
70
if
(result.
exists
(root))
71
GUM_ERROR
(
InvalidDirectedCycle
,
"cycles prevent the creation of a topological ordering."
)
72
result.
insert
(root);
73
74
for
(
const
auto
child: g.children(root)) {
75
const
Size
deg = indegree[child];
76
if
(deg == 0)
77
GUM_ERROR
(
InvalidDirectedCycle
,
"cycles prevent the creation of a topological ordering."
)
78
if
(deg == 1) border.push_back(child);
79
indegree[child] = deg - 1;
80
}
81
}
82
83
GUM_ASSERT(result.
size
() == g.size());
84
return
result;
85
}
86
87
template
< GUM_UndiGraphable G >
88
bool
hasUndirectedCycle
(
const
G& g) {
89
NodeProperty< bool >
visited;
90
for
(
const
auto
node: g.nodes())
91
visited.
insert
(node,
false
);
92
93
for
(
const
auto
node: g.nodes()) {
94
if
(visited[node])
continue
;
95
visited[node] =
true
;
96
97
List< std::pair< NodeId, NodeId >
> frontier;
98
frontier.
pushBack
({node, node});
99
100
while
(!frontier.
empty
()) {
101
const
auto
[current, from] = frontier.
front
();
102
frontier.
popFront
();
103
104
for
(
const
auto
next: g.neighbours(current)) {
105
if
(next == from)
continue
;
106
if
(visited[next])
return
true
;
107
visited[next] =
true
;
108
frontier.
pushBack
({next, current});
109
}
110
}
111
}
112
113
return
false
;
114
}
115
116
}
// namespace gum::graph
gum::HashTable::insert
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
Definition
hashTable_tpl.h:754
InvalidDirectedCycle
Exception : existence of a directed cycle in a graph.
gum::List
Generic doubly linked lists.
Definition
list.h:378
gum::List::front
Val & front() const
Returns a reference to first element of a list, if any.
Definition
list_tpl.h:1694
gum::List::pushBack
Val & pushBack(const Val &val)
Inserts a new element (a copy) at the end of the chained list.
Definition
list_tpl.h:1481
gum::List::empty
bool empty() const noexcept
Returns a boolean indicating whether the chained list is empty.
Definition
list_tpl.h:1822
gum::List::popFront
void popFront()
Removes the first element of a List, if any.
Definition
list_tpl.h:1816
gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::insert
void insert(const Key &k)
gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::exists
bool exists(const Key &k) const
gum::SequenceImplementation< Key, std::is_scalar< Key >::value >::size
Size size() const noexcept
gum::Sequence< NodeId >
cycleDetection.h
Generic cycle-detection algorithms for aGrUM graphs.
GUM_ERROR
#define GUM_ERROR(type, msg)
Definition
exceptions.h:76
gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition
types.h:74
gum::NodeId
Size NodeId
Type for node ids.
Definition
graphElements.h:117
gum::NodeProperty
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
Definition
graphElements.h:407
gum::graph
Definition
bayesBall.h:79
gum::graph::hasUndirectedCycle
bool hasUndirectedCycle(const G &g)
Returns true if g contains at least one undirected cycle.
Definition
cycleDetection_tpl.h:88
gum::graph::topologicalOrder
Sequence< NodeId > topologicalOrder(const G &g)
Returns a topological ordering of the nodes of g (Kahn's algorithm).
Definition
cycleDetection_tpl.h:49
aGrUM
3.3.2
© PHW&CG&others - 2022
DoXyGeN 1.18.0