aGrUM
0.20.2
a C++ library for (probabilistic) graphical models
Main Page
Related Pages
Modules
+
Namespaces
Namespace List
+
Namespace Members
+
All
_
a
b
c
d
e
f
g
h
i
j
l
m
n
o
p
r
s
t
v
w
+
Functions
_
a
b
c
d
e
f
g
h
i
l
m
n
o
p
r
s
t
v
Variables
Typedefs
Enumerations
+
Enumerator
a
c
e
f
g
h
i
l
p
s
t
w
+
Classes
Class List
Class Index
Class Hierarchy
+
Class Members
+
All
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
~
+
Functions
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
z
~
+
Variables
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
+
Typedefs
a
b
c
d
e
f
g
h
i
k
l
m
n
o
p
q
r
s
t
v
+
Enumerations
a
b
c
e
f
i
k
l
n
p
r
s
t
+
Enumerator
a
b
c
d
e
f
i
l
m
n
o
p
r
s
t
u
v
+
Related Functions
b
c
d
f
g
h
l
m
n
o
p
r
s
t
+
Files
File List
+
File Members
+
All
a
b
d
e
f
g
i
l
m
n
o
r
s
t
u
v
w
Functions
Variables
Enumerations
Enumerator
+
Macros
a
b
d
e
f
g
i
l
m
r
s
t
u
v
diGraph.cpp
Go to the documentation of this file.
1
/**
2
*
3
* Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
4
* info_at_agrum_dot_org
5
*
6
* This library is free software: you can redistribute it and/or modify
7
* it under the terms of the GNU Lesser General Public License as published by
8
* the Free Software Foundation, either version 3 of the License, or
9
* (at your option) any later version.
10
*
11
* This library is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
* GNU Lesser General Public License for more details.
15
*
16
* You should have received a copy of the GNU Lesser General Public License
17
* along with this library. If not, see <http://www.gnu.org/licenses/>.
18
*
19
*/
20
21
22
/** @file
23
* @brief Source implementation of Base classes for oriented graphs
24
*
25
* @author Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
26
*
27
*/
28
#
include
<
agrum
/
tools
/
graphs
/
diGraph
.
h
>
29
30
#
ifdef
GUM_NO_INLINE
31
#
include
<
agrum
/
tools
/
graphs
/
diGraph_inl
.
h
>
32
#
endif
// GUM_NOINLINE
33
34
namespace
gum
{
35
36
DiGraph
::
DiGraph
(
Size
nodes_size
,
37
bool
nodes_resize_policy
,
38
Size
arcs_size
,
39
bool
arcs_resize_policy
) :
40
NodeGraphPart
(
nodes_size
,
nodes_resize_policy
),
41
ArcGraphPart
(
arcs_size
,
arcs_resize_policy
),
42
mutableTopologicalOrder__
(
nullptr
) {
43
GUM_CONSTRUCTOR
(
DiGraph
);
44
}
45
46
DiGraph
::
DiGraph
(
const
DiGraph
&
g
) :
47
NodeGraphPart
(
g
),
ArcGraphPart
(
g
),
mutableTopologicalOrder__
(
nullptr
) {
48
GUM_CONS_CPY
(
DiGraph
);
49
if
(
g
.
mutableTopologicalOrder__
!=
nullptr
) {
50
mutableTopologicalOrder__
51
=
new
Sequence
<
NodeId
>(*(
g
.
mutableTopologicalOrder__
));
52
}
53
}
54
55
DiGraph
::~
DiGraph
() {
56
GUM_DESTRUCTOR
(
DiGraph
);
57
if
(
mutableTopologicalOrder__
!=
nullptr
) {
delete
mutableTopologicalOrder__
; }
58
}
59
60
std
::
string
DiGraph
::
toString
()
const
{
61
std
::
string
s
=
NodeGraphPart
::
toString
();
62
s
+=
" , "
;
63
s
+=
ArcGraphPart
::
toString
();
64
return
s
;
65
}
66
67
std
::
string
DiGraph
::
toDot
()
const
{
68
std
::
stringstream
strBuff
;
69
std
::
string
tab
=
" "
;
70
strBuff
<<
"digraph {"
<<
std
::
endl
;
71
72
for
(
const
auto
node
:
nodes
())
73
strBuff
<<
tab
<<
node
<<
";"
<<
std
::
endl
;
74
75
strBuff
<<
std
::
endl
;
76
77
for
(
const
auto
&
arc
:
arcs
())
78
strBuff
<<
tab
<<
arc
.
tail
() <<
" -> "
<<
arc
.
head
() <<
";"
<<
std
::
endl
;
79
80
strBuff
<<
"}"
<<
std
::
endl
<<
std
::
endl
;
81
return
strBuff
.
str
();
82
}
83
84
/// for friendly displaying the content of directed graphs
85
std
::
ostream
&
operator
<<(
std
::
ostream
&
stream
,
const
DiGraph
&
g
) {
86
stream << g.toString();
87
return
stream;
88
}
89
90
const
Sequence
<
NodeId
>&
DiGraph
::
topologicalOrder
(
bool
clear
)
const
{
91
if
(
clear
92
|| (
mutableTopologicalOrder__
93
==
nullptr
)) {
// we have to call topologicalOrder_
94
if
(
mutableTopologicalOrder__
==
nullptr
) {
95
mutableTopologicalOrder__
=
new
Sequence
<
NodeId
>();
96
}
else
{
97
// clear is True
98
mutableTopologicalOrder__
->
clear
();
99
}
100
101
topologicalOrder__
();
102
}
103
104
return
*
mutableTopologicalOrder__
;
105
}
106
107
void
DiGraph
::
topologicalOrder__
()
const
{
108
auto
dag
= *
this
;
109
auto
roots
=
std
::
vector
<
NodeId
>();
110
111
for
(
const
auto
node
:
dag
.
nodes
()) {
112
if
(
dag
.
parents
(
node
).
empty
()) {
roots
.
push_back
(
node
); }
113
}
114
115
while
(
roots
.
size
()) {
116
if
(
mutableTopologicalOrder__
->
exists
(
roots
.
back
())) {
117
GUM_ERROR
(
InvalidDirectedCycle
,
118
"cycles prevent the creation of a topological ordering."
);
119
}
120
mutableTopologicalOrder__
->
insert
(
roots
.
back
());
121
roots
.
pop_back
();
122
123
while
(
dag
.
children
(
mutableTopologicalOrder__
->
back
()).
size
()) {
124
auto
back
=
mutableTopologicalOrder__
->
back
();
125
auto
child
= *(
dag
.
children
(
back
).
begin
());
126
dag
.
eraseArc
(
Arc
(
back
,
child
));
127
128
if
(
dag
.
parents
(
child
).
empty
()) {
roots
.
push_back
(
child
); }
129
}
130
}
131
132
GUM_ASSERT
(
dag
.
sizeArcs
() == (
gum
::
Size
)(0));
133
GUM_ASSERT
(
mutableTopologicalOrder__
->
size
() ==
dag
.
size
());
134
}
135
136
bool
DiGraph
::
hasDirectedPath
(
const
NodeId
from
,
const
NodeId
to
) {
137
if
(!
exists
(
from
))
return
false
;
138
139
// not recursive version => use a FIFO for simulating the recursion
140
List
<
NodeId
>
nodeFIFO
;
141
nodeFIFO
.
pushBack
(
from
);
142
143
NodeSet
marked
;
144
marked
.
insert
(
from
);
145
146
NodeId
new_one
;
147
148
while
(!
nodeFIFO
.
empty
()) {
149
new_one
=
nodeFIFO
.
front
();
150
// std::cout<<new_one<<std::endl;
151
nodeFIFO
.
popFront
();
152
153
for
(
const
auto
chi
:
children
(
new_one
)) {
154
if
(
chi
==
to
)
return
true
;
155
156
if
(!
marked
.
contains
(
chi
)) {
157
nodeFIFO
.
pushBack
(
chi
);
158
marked
.
insert
(
chi
);
159
}
160
}
161
}
162
163
return
false
;
164
}
165
166
}
/* namespace gum */
gum::Set::emplace
INLINE void emplace(Args &&... args)
Definition:
set_tpl.h:669
gum::operator<<
std::ostream & operator<<(std::ostream &aStream, const Instantiation &i)
Print information of the instantiation in the stream.
Definition:
instantiation.cpp:265