59#ifndef DOXYGEN_SHOULD_SKIP_THIS
72 bool nodes_resize_policy,
74 bool edges_resize_policy) :
76 UndiGraph(nodes_size, nodes_resize_policy, edges_size, edges_resize_policy) {
78 GUM_CONSTRUCTOR(CliqueGraph)
83 CliqueGraph::CliqueGraph(
const CliqueGraph& from) :
86 _cliques_(from._cliques_), _separators_(from._separators_) {
87 GUM_CONS_CPY(CliqueGraph)
90 CliqueGraph::CliqueGraph(CliqueGraph&& from) :
91 NodeGraphPart(
std::move(from)),
92 UndiGraph(
std::move(from)), _cliques_(
std::move(from._cliques_)),
93 _separators_(
std::move(from._separators_)) {
94 GUM_CONS_MOV(CliqueGraph)
99 CliqueGraph::~CliqueGraph() {
100 GUM_DESTRUCTOR(CliqueGraph)
106 std::vector< NodeId > CliqueGraph::containerPath(
const NodeId node1,
const NodeId node2)
const {
110 if (!opt)
GUM_ERROR(
NotFound,
"no path between cliques containing the given nodes")
111 std::vector< NodeId > path =
std::move(*opt);
115 while ((path.size() >= 2) && (clique(path[path.size() - 2]).contains(node2)))
118 while ((path.size() >= 2) && (clique(path[1]).contains(node1)))
119 path.erase(path.begin());
128 void CliqueGraph::addToClique(const NodeId clique_id, const NodeId node_id) {
130 NodeSet& clique = _cliques_[clique_id];
133 if (clique.contains(node_id)) {
134 GUM_ERROR(DuplicateElement,
"the clique set already contains the node " << node_id)
140 for (
const auto nei: neighbours(clique_id))
141 if (_cliques_[nei].
contains(node_id)) _separators_[
Edge(nei, clique_id)].insert(node_id);
146 void CliqueGraph::eraseFromClique(
const NodeId clique_id,
const NodeId node_id) {
148 NodeSet& clique = _cliques_[clique_id];
151 if (clique.contains(node_id)) {
152 clique.erase(node_id);
155 for (
const auto nei: neighbours(clique_id)) {
156 Edge edge(nei, clique_id);
158 if (_separators_[edge].
contains(node_id)) _separators_[edge].erase(node_id);
165 bool CliqueGraph::_runningIntersectionDFS_(
const NodeId clique,
167 CliqueGraph::_RunningIntersect_& infos_DFS)
const {
170 const NodeSet& nodes_clique = _cliques_[clique];
172 for (
const auto node: nodes_clique)
173 if (infos_DFS.nodes_other_components.contains(node))
return false;
177 for (
const auto node: nodes_clique)
178 if (!infos_DFS.nodes_DFS_forbidden.contains(node))
179 infos_DFS.cliques_DFS_chain[clique].
erase(node);
183 if (infos_DFS.visited_cliques.contains(clique))
return true;
186 for (
const auto node: nodes_clique)
187 if (!infos_DFS.nodes_DFS_seen.contains(node)) infos_DFS.nodes_DFS_seen.insert(node);
190 infos_DFS.visited_cliques.insert(clique);
195 for (
const auto otherID: neighbours(clique))
196 if (otherID != from) {
199 const Edge edge(otherID, clique);
200 const NodeSet& from_separ = _separators_[edge];
202 for (
const auto node: nodes_clique) {
203 if (!from_separ.contains(node)) infos_DFS.nodes_DFS_forbidden.insert(node);
207 if (!_runningIntersectionDFS_(otherID, clique, infos_DFS))
return false;
210 for (
const auto node: nodes_clique)
211 infos_DFS.nodes_DFS_forbidden.
erase(node);
216 for (
const auto node: nodes_clique) {
217 if (!infos_DFS.nodes_DFS_forbidden.contains(node))
218 infos_DFS.cliques_DFS_chain[clique].erase(node);
227 if (neighbours(clique).size() <= 1)
228 for (
const auto node: nodes_clique)
229 if (!infos_DFS.nodes_DFS_forbidden.contains(node))
230 infos_DFS.nodes_DFS_forbidden.insert(node);
238 bool CliqueGraph::hasRunningIntersection()
const {
240 _RunningIntersect_ infos_DFS;
241 infos_DFS.cliques_DFS_chain = _cliques_;
244 for (
const auto DFSnode: nodes())
245 if (!infos_DFS.visited_cliques.contains(DFSnode)) {
247 infos_DFS.nodes_DFS_forbidden.clear();
250 infos_DFS.nodes_DFS_seen.clear();
254 if (!_runningIntersectionDFS_(DFSnode, DFSnode, infos_DFS))
return false;
259 for (
const auto node: infos_DFS.nodes_DFS_seen)
260 if (!infos_DFS.nodes_other_components.contains(node))
261 infos_DFS.nodes_other_components.insert(node);
266 for (
const auto& [node, nodes]: infos_DFS.cliques_DFS_chain)
267 if (!nodes.empty())
return false;
274 bool CliqueGraph::operator==(
const CliqueGraph& from)
const {
276 if (!UndiGraph::operator==(from))
return false;
279 for (
const auto& [node, nodes]: _cliques_)
280 if (nodes != from._cliques_[node])
return false;
285 std::string CliqueGraph::toString()
const {
286 std::stringstream stream;
287 stream <<
"list of nodes:\n";
289 for (
const auto node: nodes()) {
290 stream << std::format(
" -- node: {}\n clique:", node);
292 for (
const auto cliq: clique(node))
293 stream <<
" " << cliq;
298 stream <<
"\n\nlist of edges:\n";
300 for (
const auto& edge: edges())
301 stream << edge <<
" ";
308 std::string expandCliqueContent(
const NodeSet& clique, std::string_view delim =
"-") {
312 std::vector< NodeId > sorted(clique.begin(), clique.end());
313 std::sort(sorted.begin(), sorted.end());
314 for (
auto node: sorted) {
315 if (!first) { result += delim; }
316 result += std::to_string(node);
324 std::string expandCliqueTooltip(
const NodeSet& clique) {
325 return std::format(
"size : {}\n{}", clique.size(), expandCliqueContent(clique,
"\n"));
329 std::string separatorId(
const Edge& edge) {
330 return std::format(
"{}~{}", edge.first(), edge.second());
334 std::string dotSize(
double value) {
335 return dot::DotWriter::number(std::round(value * 1e6) / 1e6);
339 std::string CliqueGraph::toDot()
const {
return toDot(dot::DotOptions()); }
341 std::string CliqueGraph::toDot(
const dot::DotOptions& options)
const {
342 const auto style = dot::JunctionTreeDotStyle::read();
343 dot::DotWriter writer(
false);
344 dot::writePreamble(writer, style, options);
347 auto cliqueStyle =
static_cast< dot::DotStyle
>(style);
348 cliqueStyle.nodeBgColor = style.cliqueBgColor;
349 auto separatorStyle =
static_cast< dot::DotStyle
>(style);
350 separatorStyle.nodeBgColor = style.separatorBgColor;
353 for (
const auto node: nodes()) {
354 auto attributes = dot::nodeAttributes(cliqueStyle,
356 expandCliqueContent(clique(node)),
357 expandCliqueTooltip(clique(node)));
358 dot::addDefaultAttribute(attributes,
"fontsize", std::to_string(style.cliqueFontSize));
359 dot::addDefaultAttribute(attributes,
"fontcolor", style.cliqueFgColor);
360 dot::addDefaultAttribute(attributes,
"fillcolor", style.cliqueBgColor);
361 writer.node(std::to_string(node), attributes);
365 for (
const auto& edge: edges()) {
366 const auto sep = separator(edge);
367 const auto* arc = options.edge(edge.first(), edge.second());
369 dot::DotNodeOptions separatorOptions;
370 if (arc !=
nullptr) {
371 separatorOptions.bgColor = arc->color;
372 separatorOptions.label = arc->label;
373 separatorOptions.tooltip = arc->tooltip;
374 separatorOptions.attributes = arc->attributes;
377 auto attributes = dot::nodeAttributes(separatorStyle,
378 arc !=
nullptr ? &separatorOptions :
nullptr,
379 expandCliqueContent(sep),
380 expandCliqueTooltip(sep));
381 dot::addDefaultAttribute(attributes,
"margin",
"0.02");
382 dot::addDefaultAttribute(attributes,
"height",
"0");
383 dot::addDefaultAttribute(attributes,
"width",
"0");
384 dot::addDefaultAttribute(attributes,
"shape",
"box");
385 dot::addDefaultAttribute(attributes,
"fontsize", std::to_string(style.separatorFontSize));
386 dot::addDefaultAttribute(attributes,
"fontcolor", style.separatorFgColor);
387 dot::addDefaultAttribute(attributes,
"fillcolor", style.separatorBgColor);
388 writer.node(separatorId(edge), attributes);
392 for (
const auto& edge: edges()) {
393 dot::DotAttributes link;
394 const auto* arc = options.edge(edge.first(), edge.second());
395 if (arc !=
nullptr && arc->width.has_value())
396 link.push_back({
"penwidth", dot::DotWriter::number(*arc->width)});
398 writer.edge(std::to_string(edge.first()), separatorId(edge), link);
399 writer.edge(separatorId(edge), std::to_string(edge.second()), link);
405 std::string CliqueGraph::mapToDot()
const {
406 const auto style = dot::JunctionTreeDotStyle::read();
407 return mapToDot(style.mapCliqueScale,
411 style.separatorBgColor);
414 std::string CliqueGraph::mapToDot(
double scaleClique,
417 std::string_view colorClique,
418 std::string_view colorSep)
const {
419 const auto style = dot::JunctionTreeDotStyle::read();
421 dot::DotWriter writer(
false);
422 writer.graphAttributes(
423 {{
"bgcolor",
"transparent"}, {
"layout",
"neato"}, {
"size", style.mapSize}});
427 {
"fillcolor", std::string(colorClique.empty() ? style.cliqueBgColor : colorClique)}});
428 writer.edgeDefaults({{
"len", dot::DotWriter::number(lenEdge)}, {
"color", style.arcColor}});
431 for (
const auto node: nodes()) {
432 const auto& clik = clique(node);
433 writer.node(std::to_string(node),
434 {{
"tooltip", expandCliqueTooltip(clik)},
435 {
"width", dotSize(scaleClique *
double(clik.size()))}});
439 {{
"shape",
"square"},
441 {
"fillcolor", std::string(colorSep.empty() ? style.separatorBgColor : colorSep)},
445 for (
const auto& edge: edges()) {
446 const auto sep = clique(edge.first()) * clique(edge.second());
447 writer.node(separatorId(edge),
448 {{
"tooltip", expandCliqueTooltip(sep)},
449 {
"width", dotSize(scaleSep *
double(sep.size()))}});
450 writer.edge(std::to_string(edge.first()), separatorId(edge));
451 writer.edge(separatorId(edge), std::to_string(edge.second()));
459 std::ostream&
operator<<(std::ostream& stream,
const CliqueGraph& graph) {
460 stream << graph.toString();
CliqueGraph(Size nodes_size=HashTableConst::default_size, bool nodes_resize_policy=true, Size edges_size=HashTableConst::default_size, bool edges_resize_policy=true)
basic constructor: creates an empty clique graph
Class for node sets in graph.
Exception : the element we looked for cannot be found.
void insert(const Key &k)
Inserts a new element into the set.
void erase(const Key &k)
Erases an element from the set.
Base class for undirected graphs.
Basic class for all graphs of cliques (join trees, etc).
inline source of basic clique graphs
The statements common to the graphs drawn with graphviz : preamble, attributes of nodes and arcs.
#define GUM_ERROR(type, msg)
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
GUM_SHARED_PUBLIC bool contains(std::string_view s, std::string_view needle)
true if needle in s
std::optional< std::vector< NodeId > > undirectedPath(const G &g, NodeId n1, NodeId n2)
Shortest undirected path from n1 to n2 (BFS).
gum is the global namespace for all aGrUM entities
GUM_SHARED_PUBLIC std::ostream & operator<<(std::ostream &s, const gum::Variable &LDRV)
for friendly displaying the content of the variable