aGrUM  0.20.2
a C++ library for (probabilistic) graphical models
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 
39  bool arcs_resize_policy) :
42  mutableTopologicalOrder__(nullptr) {
44  }
45 
46  DiGraph::DiGraph(const DiGraph& g) :
49  if (g.mutableTopologicalOrder__ != nullptr) {
52  }
53  }
54 
57  if (mutableTopologicalOrder__ != nullptr) { delete mutableTopologicalOrder__; }
58  }
59 
60  std::string DiGraph::toString() const {
62  s += " , ";
63  s += ArcGraphPart::toString();
64  return s;
65  }
66 
67  std::string DiGraph::toDot() const {
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
86  stream << g.toString();
87  return stream;
88  }
89 
90  const Sequence< NodeId >& DiGraph::topologicalOrder(bool clear) const {
91  if (clear
93  == nullptr)) { // we have to call topologicalOrder_
94  if (mutableTopologicalOrder__ == nullptr) {
96  } else {
97  // clear is True
99  }
100 
102  }
103 
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()) {
118  "cycles prevent the creation of a topological ordering.");
119  }
121  roots.pop_back();
122 
125  auto child = *(dag.children(back).begin());
127 
128  if (dag.parents(child).empty()) { roots.push_back(child); }
129  }
130  }
131 
132  GUM_ASSERT(dag.sizeArcs() == (gum::Size)(0));
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;
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)) {
158  marked.insert(chi);
159  }
160  }
161  }
162 
163  return false;
164  }
165 
166 } /* namespace gum */
INLINE void emplace(Args &&... args)
Definition: set_tpl.h:669
std::ostream & operator<<(std::ostream &aStream, const Instantiation &i)
Print information of the instantiation in the stream.