Essentia  2.1-beta5-dev
graphutils.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2006-2016 Music Technology Group - Universitat Pompeu Fabra
3  *
4  * This file is part of Essentia
5  *
6  * Essentia is free software: you can redistribute it and/or modify it under
7  * the terms of the GNU Affero General Public License as published by the Free
8  * Software Foundation (FSF), either version 3 of the License, or (at your
9  * option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14  * details.
15  *
16  * You should have received a copy of the Affero GNU General Public License
17  * version 3 along with this program. If not, see http://www.gnu.org/licenses/
18  */
19 
20 #ifndef ESSENTIA_SCHEDULER_GRAPHUTILS_H
21 #define ESSENTIA_SCHEDULER_GRAPHUTILS_H
22 
23 #include <vector>
24 #include <stack>
25 #include <string>
26 #include <algorithm>
27 #include "network.h"
28 #include "../streaming/streamingalgorithm.h"
29 
30 namespace essentia {
31 namespace scheduler {
32 
33 
34 template <typename NodeType>
35 void depthFirstApply(NodeType* root, void (*nodeFunc)(NodeType* node)) {
36  if (!root) return;
37 
38  std::stack<NodeType*> toVisit;
39  std::set<NodeType*> visited;
40  toVisit.push(root);
41 
42  while (!toVisit.empty()) {
43  NodeType* currentNode = toVisit.top();
44  toVisit.pop();
45 
46  if (visited.find(currentNode) != visited.end()) continue;
47  visited.insert(currentNode);
48 
49  nodeFunc(currentNode);
50 
51  const std::vector<NodeType*>& children = currentNode->children();
52  // only add the nodes which have not been previously visited
53  // NB: we could let the check on currentNode at the beginning of this loop take care
54  // of this, but doing it here is faster because it spares us adding the node and
55  // removing it immediately after
56  for (int i=0; i<(int)children.size(); i++) {
57  if (visited.find(children[i]) == visited.end()) {
58  toVisit.push(children[i]);
59  }
60  }
61  }
62 }
63 
64 
65 
66 template <typename NodeType, typename MappedType>
67 std::vector<MappedType> depthFirstMap(NodeType* root,
68  MappedType (*mapFunc)(NodeType* node)) {
69 
70  if (!root) return std::vector<MappedType>();
71 
72  std::vector<MappedType> result;
73  std::stack<NodeType*> toVisit;
74  std::set<NodeType*> visited;
75  toVisit.push(root);
76 
77  while (!toVisit.empty()) {
78  NodeType* currentNode = toVisit.top();
79  toVisit.pop();
80 
81  if (visited.find(currentNode) != visited.end()) continue;
82  visited.insert(currentNode);
83 
84  result.push_back(mapFunc(currentNode));
85 
86  const std::vector<NodeType*>& children = currentNode->children();
87  // only add the nodes which have not been previously visited
88  // NB: we could let the check on currentNode at the beginning of this loop take care
89  // of this, but doing it here is faster because it spares us adding the node and
90  // removing it immediately after
91  for (int i=0; i<(int)children.size(); i++) {
92  if (visited.find(children[i]) == visited.end()) {
93  toVisit.push(children[i]);
94  }
95  }
96  }
97 
98  return result;
99 }
100 
101 template <typename NodeType>
102 NodeType* returnIdentity(NodeType* node) {
103  return node;
104 }
105 
106 template <typename NodeType>
107 std::vector<NodeType*> depthFirstSearch(NodeType* root) {
108  return depthFirstMap(root, returnIdentity<NodeType>);
109 }
110 
111 inline std::string removeNodeIdFromName(const std::string& name) {
112  std::string::size_type idpos = std::min(name.find('<'), name.find('['));
113  if (idpos == std::string::npos) return name;
114  return name.substr(0, idpos);
115 }
116 
117 inline std::pair<NetworkNode*, std::string> getIdentityAndName(NetworkNode* node) {
118  return std::make_pair(node, removeNodeIdFromName(node->algorithm()->name()));
119 }
120 
122  return node->algorithm();
123 }
124 
125 template <typename T, typename U>
127  public:
128  bool operator()(const std::pair<T, U>& p1, const std::pair<T, U>& p2) const {
129  if (p1.second < p2.second) return true;
130  if (p1.second > p2.second) return false;
131  return p1.first < p2.first;
132  }
133 };
134 
135 template <typename NodeType>
136 void adjacencyMatrix(const std::vector<std::pair<NodeType*, std::string> >& nodes,
137  std::vector<std::vector<bool> >& adjMatrix) {
138  int nnodes = nodes.size();
139  adjMatrix = std::vector<std::vector<bool> >(nnodes, std::vector<bool>(nnodes, false));
140 
141  for (int i=0; i<nnodes; i++) {
142  NodeType* start = nodes[i].first;
143  const std::vector<NodeType*>& children = start->children();
144  for (int j=0; j<(int)children.size(); j++) {
145  for (int k=0; k<nnodes; k++) {
146  if (children[j] == nodes[k].first) adjMatrix[i][k] = true;
147  }
148  }
149  }
150 }
151 
152 // most likely this overload is not very dangerous
153 template <typename NodeType>
154 void printAdjacencyMatrix(const std::vector<std::vector<bool> >& adjMatrix,
155  const std::vector<std::pair<NodeType*, std::string> >& nodes) {
156  int size = adjMatrix.size();
157  for (int i=0; i<size; i++) {
158  for (int j=0; j<size; j++) {
159  E_DEBUG_NONL(EGraph, (adjMatrix[i][j] ? " 1" : " 0"));
160  }
161  E_DEBUG_NONL(EGraph, " " << nodes[i].second << " ->");
162  for (int j=0; j<size; j++) {
163  E_DEBUG_NONL(EGraph, (adjMatrix[i][j] ? (" " + nodes[j].second) : ""));
164  }
165  E_DEBUG(EGraph, "");
166  }
167 }
168 
169 template <typename NodeType>
170 bool areNetworkTopologiesEqual(NodeType* n1, NodeType* n2) {
171  // this function compares both network and decide whether they have the same topology
172  // to do this, we apply the following algorithm (not the most efficient, yeah)
173  // - get list of all nodes (if not same number -> different networks)
174  // - order them by alphabetical order (need to be same order)
175  // - for each duplicate node name, generate permutations for this node
176  // - for each permutation, generate adjacency matrix and compare them:
177  // - if there is 1 permutation for which the matrices are equal, then the networks are equal
178  // - if the matrices are different for all the permutations, then the networks are different
179 
180  // get the list of nodes and their names
181  std::vector<std::pair<NodeType*, std::string> > nodes1 = depthFirstMap(n1, getIdentityAndName);
182  std::vector<std::pair<NodeType*, std::string> > nodes2 = depthFirstMap(n2, getIdentityAndName);
183 
184  E_DEBUG(EGraph, "Comparing network topologies:");
185  E_DEBUG(EGraph, " n1.size() = " << nodes1.size() << " - n2.size() = " << nodes2.size());
186 
187  if (nodes1.size() != nodes2.size()) return false;
188  int nnodes = nodes1.size();
189 
190  // sort the nodes by their names and compare them
191  std::sort(nodes1.begin(), nodes1.end(), ReversePairCompare<NodeType*, std::string>());
192  std::sort(nodes2.begin(), nodes2.end(), ReversePairCompare<NodeType*, std::string>());
193 
194  E_DEBUG(EGraph, " nodes1: " << nodes1);
195  E_DEBUG(EGraph, " nodes2: " << nodes2);
196 
197  for (int i=0; i<nnodes; i++) {
198  if (nodes1[i].second != nodes2[i].second) return false;
199  }
200 
201  // now try all the permutations of the nodes with the same name and try to look whether there is
202  // one for which the adjacency matrices are equal
203  std::vector<std::pair<int, int> > same; // ranges for the nodes which have the same name
204 
205  int idx = 0;
206  while (idx < (nnodes-1)) {
207  if (nodes1[idx].second != nodes1[idx+1].second) { idx++; continue; }
208  // we have at least 2 nodes with the same name
209  int start_idx = idx;
210  const std::string& name = nodes1[idx].second;
211  idx++;
212  while (idx < nnodes && nodes1[idx].second == name) idx++;
213  same.push_back(std::make_pair(start_idx, idx));
214  }
215 
216  // reset the positions for the permutations to work correctly
217  for (int i=0; i<(int)same.size(); i++) {
218  std::sort(nodes1.begin() + same[i].first,
219  nodes1.begin() + same[i].second);
220  }
221 
222  std::vector<std::vector<bool> > adjMatrix1;
223  std::vector<std::vector<bool> > adjMatrix2;
224 
225  // 2 will be fixed, compute its adjacency matrix now
226  adjacencyMatrix(nodes2, adjMatrix2);
227 
228 
229  E_DEBUG(EGraph, "adj matrix 2:");
230  printAdjacencyMatrix(adjMatrix2, nodes2);
231 
232 
233  // try each permutation and compare adj. matrices
234  while (true) {
235  // if adjacency matrices are equal, return true;
236  adjacencyMatrix(nodes1, adjMatrix1);
237 
238  E_DEBUG(EGraph, "comparing with");
239  printAdjacencyMatrix(adjMatrix1, nodes1);
240 
241  if (adjMatrix1 == adjMatrix2) return true;
242 
243  // otherwise, advance to next permutation
244  int permidx = 0;
245  bool nextgroup = true;
246  while (nextgroup) {
247  if (permidx == (int)same.size()) return false; // we exhausted all permutations and didn't find a correspondence
248  // we want to permute the next group only if the current group finished a full cycle
249  nextgroup = !std::next_permutation(nodes1.begin() + same[permidx].first,
250  nodes1.begin() + same[permidx].second);
251  permidx++;
252  }
253  }
254 
255  assert(false);
256 }
257 
258 } // namespace scheduler
259 } // namespace essentia
260 
261 
262 #endif // ESSENTIA_SCHEDULER_GRAPHUTILS_H
Definition: network.h:56
const streaming::Algorithm * algorithm() const
Definition: network.h:64
void printAdjacencyMatrix(const std::vector< std::vector< bool > > &adjMatrix, const std::vector< std::pair< NodeType *, std::string > > &nodes)
Definition: graphutils.h:154
std::pair< NetworkNode *, std::string > getIdentityAndName(NetworkNode *node)
Definition: graphutils.h:117
std::vector< MappedType > depthFirstMap(NodeType *root, MappedType(*mapFunc)(NodeType *node))
Definition: graphutils.h:67
void depthFirstApply(NodeType *root, void(*nodeFunc)(NodeType *node))
Definition: graphutils.h:35
const std::string & name() const
Definition: configurable.h:48
Definition: debugging.h:46
std::vector< NodeType * > depthFirstSearch(NodeType *root)
Definition: graphutils.h:107
Definition: graphutils.h:126
std::string removeNodeIdFromName(const std::string &name)
Definition: graphutils.h:111
void adjacencyMatrix(const std::vector< std::pair< NodeType *, std::string > > &nodes, std::vector< std::vector< bool > > &adjMatrix)
Definition: graphutils.h:136
bool operator()(const std::pair< T, U > &p1, const std::pair< T, U > &p2) const
Definition: graphutils.h:128
Definition: algorithm.h:28
streaming::Algorithm * returnAlgorithm(NetworkNode *node)
Definition: graphutils.h:121
Definition: streamingalgorithm.h:140
NodeType * returnIdentity(NodeType *node)
Definition: graphutils.h:102
bool areNetworkTopologiesEqual(NodeType *n1, NodeType *n2)
Definition: graphutils.h:170
#define E_DEBUG_NONL(module, msg)
Definition: debugging.h:156
#define E_DEBUG(module, msg)
Definition: debugging.h:157