SMIL  0.9.1
DGraph.hpp
1 /*
2  * Copyright (c) 2011-2016, Matthieu FAESSEL and ARMINES
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * * Neither the name of Matthieu FAESSEL, or ARMINES nor the
14  * names of its contributors may be used to endorse or promote products
15  * derived from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #ifndef _D_GRAPH_HPP
30 #define _D_GRAPH_HPP
31 
32 #include "Core/include/DBaseObject.h"
33 
34 #include <list>
35 #include <algorithm>
36 #include <vector>
37 #include <utility>
38 #include <iostream>
39 #include <stdexcept>
40 #include <set>
41 #include <queue>
42 
43 namespace smil
44 {
45 
46 
51  template <class NodeT=size_t, class WeightT=size_t>
52  class Edge
53  {
54  public:
55  typedef WeightT WeightType;
57  Edge()
58  : source(0), target(0), weight(1)
59  {
60  }
62  Edge(NodeT a, NodeT b, WeightT w=1)
63  : source(a), target(b), weight(w)
64  {
65  }
67  Edge(const Edge &rhs)
68  : source(rhs.source), target(rhs.target), weight(rhs.weight)
69  {
70  }
71 
72  virtual ~Edge()
73  {
74  }
75 
76  Edge &operator =(const Edge &rhs)
77  {
78  source = rhs.source;
79  target = rhs.target;
80  weight = rhs.weight;
81  return *this;
82  }
83 
85  NodeT source;
87  NodeT target;
89  WeightT weight;
90 
91  inline bool isActive() const { return (source!=0 || target!=0); }
92  inline void desactivate()
93  {
94  source = 0;
95  target = 0;
96  }
97  // Don't test the weight values (only to check if the edge exists)
98  inline bool operator ==(const Edge &rhs) const
99  {
100  if (rhs.source==source && rhs.target==target)
101  return true;
102  else if (rhs.source==target && rhs.target==source)
103  return true;
104  return false;
105  }
106  inline bool operator !=(const Edge &rhs) const { return !this->operator ==(rhs); }
107 
108  inline bool operator <(const Edge &rhs) const
109  {
110  return weight>rhs.weight;
111  }
112 
113  virtual void printSelf(ostream &os = std::cout, string s="") const
114  {
115  os << s << (int)source << "-" << (int)target << " (" << (int)weight << ")" << endl;
116  }
117  };
118 
119  // Compare two vectors of edges (test also the weight values)
120  template <class NodeT, class WeightT>
121  bool operator == (const vector< Edge<NodeT,WeightT> > &e1, const vector< Edge<NodeT,WeightT> > &e2)
122  {
123  if (e1.size()!=e2.size())
124  return false;
125 
126  typedef Edge<NodeT,WeightT> EdgeT;
127  typename vector<EdgeT>::const_iterator it1 = e1.begin(), it2 = e2.begin();
128 
129  for (;it1!=e1.end();it1++, it2++)
130  {
131  if ((*it1)!=(*it2))
132  return false;
133  if (it1->weight!=it2->weight)
134  return false;
135  }
136  return true;
137  }
138 
143  template <class NodeT=size_t, class WeightT=size_t>
144  class Graph : public BaseObject
145  {
146  public:
148 
149  typedef NodeT NodeType;
150  typedef WeightT NodeWeightType;
151  typedef std::map<NodeT, WeightT> NodeValuesType;
152  typedef set<NodeT> NodeListType;
153 
155  typedef WeightT EdgeWeightType;
156 
157  typedef std::vector< Edge<NodeT,WeightT> > EdgeListType;
158  typedef std::vector<size_t> NodeEdgesType;
159  typedef std::map< NodeT, NodeEdgesType > NodeEdgeListType;
160  protected:
161  size_t edgeNbr;
162  NodeListType nodes;
163  NodeValuesType nodeValues;
164  EdgeListType edges;
165  NodeEdgeListType nodeEdgeList;
166 
167  public:
170  : BaseObject("Graph"),
171  edgeNbr(0)
172  {
173  }
175  Graph(const Graph &rhs)
176  : BaseObject("Graph"),
177  edgeNbr(rhs.edgeNbr),
178  nodes(rhs.nodes),
179  nodeValues(rhs.nodeValues),
180  edges(rhs.edges),
181  nodeEdgeList(rhs.nodeEdgeList)
182  {
183  }
184 
185  virtual ~Graph() {}
186 
187  Graph &operator =(const Graph &rhs)
188  {
189  nodes = rhs.nodes;
190  nodeValues = rhs.nodeValues;
191  edges = rhs.edges;
192  nodeEdgeList = rhs.nodeEdgeList;
193  edgeNbr = rhs.edgeNbr;
194  return *this;
195  }
196 
198  void clear()
199  {
200  nodes.clear();
201  nodeValues.clear();
202  edges.clear();
203  nodeEdgeList.clear();
204  edgeNbr = 0;
205  }
206 
208  void addNode(const NodeT &ind)
209  {
210  nodes.insert(ind);
211  }
212  void addNode(const NodeT &ind, const WeightT &val)
213  {
214  nodes.insert(ind);
215  nodeValues[ind] = val;
216  }
217 
218  inline int findEdge(const EdgeType &e)
219  {
220  typename EdgeListType::iterator foundEdge = find(edges.begin(), edges.end(), e);
221  if (foundEdge!=edges.end())
222  return foundEdge-edges.begin();
223  else return -1;
224  }
225 
226  inline int findEdge(const NodeT &src, const NodeT &targ)
227  {
228  return findEdge(EdgeType(src, targ));
229  }
230 
237  void addEdge(const EdgeType &e, bool checkIfExists=true)
238  {
239  if (checkIfExists)
240  if (findEdge(e)!=-1)
241  return;
242 
243  edges.push_back(e);
244  nodes.insert(e.source);
245  nodes.insert(e.target);
246  nodeEdgeList[e.source].push_back(edgeNbr);
247  nodeEdgeList[e.target].push_back(edgeNbr);
248 
249  edgeNbr++;
250  }
251 
258  void addEdge(const NodeT src, const NodeT targ, WeightT weight=0, bool checkIfExists=true)
259  {
260  addEdge(EdgeType(src, targ, weight), checkIfExists);
261  }
262 
263  void sortEdges(bool reverse=false)
264  {
265  EdgeListType sEdges = edges;
266  if (!reverse)
267  sort(sEdges.begin(), sEdges.end());
268  else
269  sort(sEdges.rbegin(), sEdges.rend());
270 
271  nodes.clear();
272  edges.clear();
273  nodeEdgeList.clear();
274  edgeNbr = 0;
275 
276  for (typename EdgeListType::const_iterator it=sEdges.begin();it!=sEdges.end();it++)
277  addEdge(*it, false);
278  }
279 
280  GraphType clone()
281  {
282  return GraphType(*this);
283  }
284 
285  size_t getNodeNbr()
286  {
287  return nodes.size();
288  }
289 
290  size_t getEdgeNbr()
291  {
292  return edges.size();
293  }
294 
295  protected:
296  void removeNode(const NodeT ind)
297  {
298  typename NodeListType::iterator fNode = nodes.find(ind);
299  if (fNode!=nodes.end())
300  nodes.erase(fNode);
301  removeNodeEdges(ind);
302  }
303  void removeNodeEdge(const NodeT node, const size_t edgeIndex)
304  {
305  typename NodeEdgeListType::iterator nEdges = nodeEdgeList.find(node);
306  if (nEdges==nodeEdgeList.end())
307  return;
308 
309  NodeEdgesType &eList = nEdges->second;
310 
311  typename NodeEdgesType::iterator ei = find(eList.begin(), eList.end(), edgeIndex);
312  if (ei!=eList.end())
313  eList.erase(ei);
314  }
315  public:
317  void removeNodeEdges(const NodeT node)
318  {
319  typename NodeEdgeListType::iterator fNodeEdges = nodeEdgeList.find(node);
320  if (fNodeEdges==nodeEdgeList.end())
321  return;
322 
323  NodeEdgesType &nedges = fNodeEdges->second;
324  for (NodeEdgesType::iterator it=nedges.begin();it!=nedges.end();it++)
325  {
326  EdgeType &e = edges[*it];
327  if (e.source==node)
328  removeNodeEdge(e.target, *it);
329  else
330  removeNodeEdge(e.source, *it);
331  e.desactivate();
332  }
333  nedges.clear();
334  }
336  void removeEdge(const size_t index)
337  {
338  if (index>=edges.size())
339  return;
340 
341  EdgeType &edge = edges[index];
342 
343  removeNodeEdge(edge.source, index);
344  removeNodeEdge(edge.target, index);
345  edge.desactivate();
346  }
348  void removeEdge(const NodeT src, const NodeT targ)
349  {
350  typename EdgeListType::iterator foundEdge = find(edges.begin(), edges.end(), EdgeType(src,targ));
351  if (foundEdge==edges.end())
352  return;
353 
354  return removeEdge(foundEdge-edges.begin());
355  }
356  // Remove a given edge
357  void removeEdge(const EdgeType &edge)
358  {
359  typename EdgeListType::iterator foundEdge = find(edges.begin(), edges.end(), edge);
360  if (foundEdge==edges.end())
361  return;
362 
363  return removeEdge(foundEdge-edges.begin());
364  }
365 
366  void removeHighEdges( EdgeWeightType EdgeThreshold)
367  {
368  size_t nb_edges = edges.size();
369  for (size_t index= 0; index < nb_edges; index++)
370  {
371  EdgeType &e = edges[index];
372  if (e.weight>EdgeThreshold)
373  removeEdge(index);
374 
375  }
376  }
377 
378  void removeLowEdges( EdgeWeightType EdgeThreshold)
379  {
380  size_t nb_edges = edges.size();
381  for (size_t index= 0; index < nb_edges; index++)
382  {
383  EdgeType &e = edges[index];
384  if (e.weight<EdgeThreshold)
385  removeEdge(index);
386 
387  }
388  }
389 
390 #ifndef SWIG
391  const NodeListType &getNodes() const { return nodes; } // lvalue
392  const EdgeListType &getEdges() const { return edges; } // lvalue
393  const NodeValuesType &getNodeValues() const { return nodeValues; } // lvalue
394  const NodeEdgeListType &getNodeEdges() const { return nodeEdgeList; } // lvalue
395 #endif // SWIG
396  NodeListType &getNodes() { return nodes; } // rvalue
398  EdgeListType &getEdges() { return edges; } // rvalue
399  NodeValuesType &getNodeValues() { return nodeValues; } // rvalue
400  NodeEdgeListType &getNodeEdges() { return nodeEdgeList; } // rvalue
401 
403  NodeEdgesType getNodeEdges(const size_t &node)
404  {
405  typename NodeEdgeListType::iterator it = nodeEdgeList.find(node);
406  if (it!=nodeEdgeList.end())
407  return it->second;
408  else return vector<size_t>();
409 
410  }
411 
413  GraphType computeMST()
414  {
415  return graphMST(*this);
416  }
417 
418  virtual void printSelf(ostream &os = std::cout, string s ="") const
419  {
420  os << s << "Number of nodes: " << nodes.size() << endl;
421  os << s << "Number of edges: " << edges.size() << endl;
422  os << s << "Edges: " << endl << "source-target (weight) " << endl;
423 
424  string s2 = s + "\t";
425  for (typename EdgeListType::const_iterator it=edges.begin();it!=edges.end();it++)
426  if ((*it).isActive())
427  (*it).printSelf(os, s2);
428  }
429 
433  map<NodeT,NodeT> labelizeNodes() const
434  {
435  map<NodeT,NodeT> lookup;
436  set<NodeT> nodeList(nodes);
437 
438  while(!nodeList.empty())
439  {
440  propagateLabel(*(nodeList.begin()), *(nodeList.begin()), lookup, nodeList);
441  }
442  return lookup;
443  }
444 
445  protected:
446  void propagateLabel(const NodeT ind, const NodeT lbl, map<NodeT,NodeT> &lookup, set<NodeT> &nList) const
447  {
448  typename NodeListType::iterator foundNode = nList.find(ind);
449  if (foundNode==nList.end())
450  return;
451 
452  lookup[ind] = lbl;
453  nList.erase(foundNode);
454 
455  const NodeEdgesType &nEdges = nodeEdgeList.at(ind);
456 
457  for (typename NodeEdgesType::const_iterator it=nEdges.begin();it!=nEdges.end();it++)
458  {
459  const EdgeType &e = edges[*it];
460  if (e.source!=ind)
461  propagateLabel(e.source, lbl, lookup, nList);
462  else if (e.target!=ind)
463  propagateLabel(e.target, lbl, lookup, nList);
464  }
465  }
466 
467  };
468 
469  template <class graphT>
470  graphT graphMST(const graphT &graph)
471  {
472  typedef typename graphT::NodeType NodeType;
473  typedef typename graphT::EdgeType EdgeType;
474  typedef typename graphT::EdgeListType EdgeListType;
475  typedef typename graphT::NodeEdgesType NodeEdgesType;
476  typedef typename graphT::NodeEdgeListType NodeEdgeListType;
477 
478  std::set<NodeType> visitedNodes;
479  std::priority_queue< EdgeType > pq;
480  graphT mst;
481 
482  const EdgeListType &edges = graph.getEdges();
483  const NodeEdgeListType &nodeEdgeList = graph.getNodeEdges();
484 
485  NodeType curNode = (*nodeEdgeList.begin()).first;
486  visitedNodes.insert(curNode);
487 
488  const NodeEdgesType &nodeEdges = nodeEdgeList.at(curNode);
489  for (typename NodeEdgesType::const_iterator it=nodeEdges.begin();it!=nodeEdges.end();it++)
490  pq.push(edges[*it]);
491 
492  while(!pq.empty())
493  {
494  EdgeType edge = pq.top();
495  pq.pop();
496 
497  if(visitedNodes.find(edge.source) == visitedNodes.end())
498  curNode = edge.source;
499  else if (visitedNodes.find(edge.target) == visitedNodes.end())
500  curNode = edge.target;
501  else continue;
502 
503  mst.addEdge(edge, false);
504  visitedNodes.insert(curNode);
505  NodeEdgesType const& nodeEdges = nodeEdgeList.at(curNode);
506  for (typename NodeEdgesType::const_iterator it=nodeEdges.begin();it!=nodeEdges.end();it++)
507  pq.push(edges[*it]);
508  }
509  // Copy node values
510  mst.getNodeValues() = graph.getNodeValues();
511 
512  return mst;
513  }
514 
515 } // namespace smil
516 
517 #endif // _D_GRAPH_HPP
518 
GraphType computeMST()
Compute the Minimum Spanning Tree graph.
Definition: DGraph.hpp:413
Graph()
Default constructor.
Definition: DGraph.hpp:169
Definition: DColorConvert.h:38
Non-oriented edge.
Definition: DGraph.hpp:52
Graph(const Graph &rhs)
Copy constructor.
Definition: DGraph.hpp:175
Non-oriented graph.
Definition: DGraph.hpp:144
void removeEdge(const size_t index)
Remove an edge.
Definition: DGraph.hpp:336
void addEdge(const NodeT src, const NodeT targ, WeightT weight=0, bool checkIfExists=true)
Add an edge to the graph given two nodes src and targ and an optional weight If checkIfExists is true...
Definition: DGraph.hpp:258
NodeT target
Target node.
Definition: DGraph.hpp:87
Base Smil Object.
Definition: DBaseObject.h:53
void removeNodeEdges(const NodeT node)
Remove all edges linked to the node nodeIndex.
Definition: DGraph.hpp:317
void clear()
Clear graph content.
Definition: DGraph.hpp:198
map< NodeT, NodeT > labelizeNodes() const
Labelize the nodes. Give a different label to each group of connected nodes. Return a map [ node...
Definition: DGraph.hpp:433
Edge(NodeT a, NodeT b, WeightT w=1)
Constructor using two nodes and an optional weight (default 1).
Definition: DGraph.hpp:62
EdgeListType & getEdges()
Get a vector containing the graph edges.
Definition: DGraph.hpp:398
Edge(const Edge &rhs)
Copy constructor.
Definition: DGraph.hpp:67
WeightT weight
Edge weight/value.
Definition: DGraph.hpp:89
void addEdge(const EdgeType &e, bool checkIfExists=true)
Add an edge to the graph.
Definition: DGraph.hpp:237
Edge()
Default constructor.
Definition: DGraph.hpp:57
RES_T clone(const Image< T > &imIn, Image< T > &imOut)
Clone an image.
Definition: DImageArith.hpp:227
void addNode(const NodeT &ind)
Add a node given its index and its optional value.
Definition: DGraph.hpp:208
NodeEdgesType getNodeEdges(const size_t &node)
Get a map containing the edges linked to a given node.
Definition: DGraph.hpp:403
void removeEdge(const NodeT src, const NodeT targ)
Find and remove an edge linking src to targ.
Definition: DGraph.hpp:348
NodeT source
Source node.
Definition: DGraph.hpp:85