aGrUM  0.13.2
structuralComparator.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}@lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
20 
22 
23 
24 #ifndef DOXYGEN_SHOULD_SKIP_THIS
25 
26 namespace gum {
28  GUM_CONSTRUCTOR(StructuralComparator);
29  }
30 
33  GUM_DESTRUCTOR(StructuralComparator);
34  }
35 
36  void StructuralComparator::compare(const DiGraph& ref, const DiGraph& test) {
37  if (ref.size() != test.size()) {
38  GUM_ERROR(OperationNotAllowed, "Graphs of different sizes");
39  }
40  for (const NodeId node : ref.asNodeSet()) {
41  if (!test.existsNode(node)) {
42  GUM_ERROR(InvalidNode, "Test doesn't contain all nodes from ref");
43  }
44  }
45  // compute the orientation matrix
46  // no edges so these stay null
47  __true_edge = 0;
48  __wrong_edge_arc = 0;
50  __wrong_arc_edge = 0;
52  // these will be filled
53  __true_arc = 0;
54  __true_none = 0;
56  __wrong_arc_none = 0;
57  __wrong_none_arc = 0;
58 
59  for (const Arc& arc : ref.arcs()) {
60  if (test.existsArc(arc)) {
61  ++__true_arc;
62  } else if (test.existsArc(arc.head(), arc.tail())) {
64  } else {
66  }
67  }
68  for (const Arc& arc : test.arcs()) {
69  if (!ref.existsArc(arc) && !ref.existsArc(arc.head(), arc.tail())) {
71  }
72  }
73  // TN = #possible arcs - #existing arcs
74  __true_none = ref.size() * (ref.size() - 1) - __true_arc - __misoriented_arc
76  }
77 
78  void StructuralComparator::compare(const UndiGraph& ref, const UndiGraph& test) {
79  if (ref.size() != test.size()) {
80  GUM_ERROR(OperationNotAllowed, "Graphs of different sizes");
81  }
82  for (const NodeId node : ref.asNodeSet()) {
83  if (!test.existsNode(node)) {
84  GUM_ERROR(InvalidNode, "Test doesn't contain all nodes from ref");
85  }
86  }
87  // compute the orientation matrix
88  // no arcs so these stay null
89  __true_arc = 0;
91  __wrong_arc_none = 0;
92  __wrong_none_arc = 0;
93  __wrong_edge_arc = 0;
94  __wrong_arc_edge = 0;
95  // these will be filled
96  __true_edge = 0;
97  __true_none = 0;
100 
101  for (const Edge& edge : ref.edges()) {
102  if (test.existsEdge(edge)) {
103  ++__true_edge;
104  } else {
106  }
107  }
108  for (const Edge& edge : test.edges()) {
109  if (!ref.existsEdge(edge)) { ++__wrong_edge_none; }
110  }
111  // TN = #possible edges - #existing edges
112  __true_none = ref.size() * (ref.size() - 1) / 2 - __true_edge
114  }
115 
116  void StructuralComparator::compare(const MixedGraph& ref,
117  const MixedGraph& test) {
118  if (ref.size() != test.size()) {
119  GUM_ERROR(OperationNotAllowed, "Graphs of different sizes");
120  }
121  for (const NodeId node : ref.asNodeSet()) {
122  if (!test.existsNode(node)) {
123  GUM_ERROR(InvalidNode, "Test doesn't contain all nodes from ref");
124  }
125  }
126 
127  // compute the orientation matrix
128  __true_arc = 0;
129  __true_edge = 0;
130  __true_none = 0;
131  __misoriented_arc = 0;
132  __wrong_arc_edge = 0;
133  __wrong_arc_none = 0;
134  __wrong_edge_arc = 0;
135  __wrong_edge_none = 0;
136  __wrong_none_arc = 0;
137  __wrong_none_edge = 0;
138 
139  for (const Arc& arc : ref.arcs()) {
140  if (test.existsArc(arc)) {
141  ++__true_arc;
142  } else if (test.existsArc(arc.head(), arc.tail())) {
144  } else if (test.existsEdge(arc.tail(), arc.head())) {
146  } else {
148  }
149  }
150  for (const Edge& edge : ref.edges()) {
151  if (test.existsEdge(edge)) {
152  ++__true_edge;
153  } else if (test.existsArc(edge.first(), edge.second())
154  || test.existsArc(edge.second(), edge.first())) {
156  } else {
158  }
159  }
160  for (const Arc& arc : test.arcs()) {
161  if (!ref.existsArc(arc) && !ref.existsArc(arc.head(), arc.tail())
162  && !ref.existsEdge(arc.tail(), arc.head())) {
164  }
165  }
166  for (const Edge& edge : test.edges()) {
167  if (!ref.existsEdge(edge) && !ref.existsArc(edge.first(), edge.second())
168  && !ref.existsArc(edge.second(), edge.first())) {
170  }
171  }
172  // TN = #possible edges - #existing edges
173  __true_none = ref.size() * (ref.size() - 1) / 2 - __true_edge
176  }
177 
179  double tp, fp, precision;
183  precision = tp / (tp + fp);
184  return precision;
185  }
186 
188  double tp, fn, recall;
192  recall = tp / (tp + fn);
193  return recall;
194  }
195 
197  double tp, fp, fn, precision, recall, f_score;
202 
203  precision = tp / (tp + fp);
204  recall = tp / (tp + fn);
205  f_score = 2 * precision * recall / (precision + recall);
206  return f_score;
207  }
208 
209  double StructuralComparator::precision() const {
210  double tp, fp, precision;
211  tp = __true_arc + __true_edge;
214  precision = tp / (tp + fp);
215  return precision;
216  }
217 
218  double StructuralComparator::recall() const {
219  double tp, fn, recall;
220  tp = __true_arc + __true_edge;
222  recall = tp / (tp + fn);
223  return recall;
224  }
225 
226  double StructuralComparator::f_score() const {
227  double tp, fp, fn, precision, recall, f_score;
228  tp = __true_arc + __true_edge;
232 
233  precision = tp / (tp + fp);
234  recall = tp / (tp + fn);
235 
236  f_score = 2 * precision * recall / (precision + recall);
237  return f_score;
238  }
239 
240 } /* namespace gum */
241 
242 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
double f_score() const
compare two DiGraphs
double recall() const
compare two DiGraphs
double recall_skeleton() const
compare two DiGraphs
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
double precision() const
Measures for the graphs.
StructuralComparator()
default constructor
A class for comparing graphs based on their structures.
void compare(const DiGraph &ref, const DiGraph &test)
compare two DiGraphs
double __true_edge
Confusion matrix.
double precision_skeleton() const
Measures for the skeleton, aka graph without orientations.
~StructuralComparator()
destructor
double f_score_skeleton() const
compare two DiGraphs
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66