Graph: Generic attributed relational graphs


graph.h
Go to the documentation of this file.
1 /* This software and supporting documentation are distributed by
2  * Institut Federatif de Recherche 49
3  * CEA/NeuroSpin, Batiment 145,
4  * 91191 Gif-sur-Yvette cedex
5  * France
6  *
7  * This software is governed by the CeCILL-B license under
8  * French law and abiding by the rules of distribution of free software.
9  * You can use, modify and/or redistribute the software under the
10  * terms of the CeCILL-B license as circulated by CEA, CNRS
11  * and INRIA at the following URL "http://www.cecill.info".
12  *
13  * As a counterpart to the access to the source code and rights to copy,
14  * modify and redistribute granted by the license, users are provided only
15  * with a limited warranty and the software's author, the holder of the
16  * economic rights, and the successive licensors have only limited
17  * liability.
18  *
19  * In this respect, the user's attention is drawn to the risks associated
20  * with loading, using, modifying and/or developing or reproducing the
21  * software by the user in light of its specific status of free software,
22  * that may mean that it is complicated to manipulate, and that also
23  * therefore means that it is reserved for developers and experienced
24  * professionals having in-depth computer knowledge. Users are therefore
25  * encouraged to load and test the software's suitability as regards their
26  * requirements in conditions enabling the security of their systems and/or
27  * data to be ensured and, more generally, to use and operate it in the
28  * same conditions as regards security.
29  *
30  * The fact that you are presently reading this means that you have had
31  * knowledge of the CeCILL-B license and that you accept its terms.
32  */
33 
34 #ifndef GRAPH_GRAPH_GRAPH_H
35 #define GRAPH_GRAPH_GRAPH_H
36 
37 
38 //=============================================================================
39 // H E A D E R F I L E S
40 //=============================================================================
41 
43 #ifndef GRAPH_GRAPH_GRAPHOBJECT_H
45 #endif
46 #ifndef GRAPH_GRAPH_VERTEX_H
47 #include <graph/graph/vertex.h>
48 #endif
49 #ifndef GRAPH_GRAPH_EDGE_H
50 #include <graph/graph/edge.h>
51 #endif
52 #ifndef GRAPH_GRAPH_GFACTORY_H
53 #include <graph/graph/gfactory.h>
54 #endif
55 #include <cartobase/smart/rcptr.h>
56 #include <cartobase/type/types.h>
57 
58 #include <algorithm>
59 #include <functional>
60 #include <set>
61 #include <stdexcept>
62 
63 
64 //=============================================================================
65 // C L A S S D E C L A R A T I O N
66 //=============================================================================
67 
71 class GRAPH_API Graph : public GraphObject
72 {
73 
74 public:
75 
76  typedef std::set<Vertex*> VSet;
77  typedef std::set<Edge*> ESet;
78 
80  typedef VSet::value_type value_type;
81 #ifndef _WIN32
82  typedef VSet::pointer pointer;
84 #endif
85  typedef VSet::reference reference;
86  typedef VSet::const_reference const_reference;
87  typedef VSet::iterator iterator;
88  typedef VSet::const_iterator const_iterator;
89  typedef VSet::reverse_iterator reverse_iterator;
90  typedef VSet::const_reverse_iterator const_reverse_iterator;
91 
94  Graph(const std::string& s = "");
95 
100  Graph(const FactoryPtr factory, const std::string& s = "");
101 
107  virtual ~Graph();
108 
115  template <class InputIterator>
116  void extract(Graph& graph, InputIterator iv1, InputIterator iv2)
117  throw(std::range_error);
118 
119  //---------------------------------------------------------------------
121  //---------------------------------------------------------------------
123 
126  void clear();
127 
129 
130  //---------------------------------------------------------------------
132  //---------------------------------------------------------------------
134 
143  Vertex* addVertex(const std::string& s = "");
144 
155  Vertex* cloneVertex(const Vertex* vertex);
156 
161  bool hasVertex(const Vertex* vertex) const;
162 
169  void removeVertex(Vertex* vertex) throw(std::range_error);
170 
174  Vertex* randomVertex() const;
175 
179  const std::set<Vertex*>& vertices() const;
180 
185  std::set<Vertex*> getVerticesWith(const std::string& s) const;
186 
193  template <class T>
194  std::set<Vertex*> getVerticesWith(const std::string& s,
195  const T& t) const;
196 
198 
199  //---------------------------------------------------------------------
201  //---------------------------------------------------------------------
203 
216  Edge* addUndirectedEdge(Vertex* vertex1, Vertex* vertex2, std::
217  string s)
218  throw(std::range_error);
219 
222  Edge* addEdge(Vertex* vertex1, Vertex* vertex2, std::string s = "")
223  throw(std::range_error);
224 
237  Edge* addDirectedEdge(Vertex* vertex1, Vertex* vertex2, std::string s)
238  throw(std::range_error);
239 
244  bool hasEdge(const Edge* edge) const;
245 
252  void removeEdge(Edge* edge) throw(std::range_error);
253 
257  const std::set<Edge*>& edges() const;
258 
264  std::set<Edge*> edges(const Vertex* vertex1,
265  const Vertex* vertex2) const;
266 
271  std::set<Edge*> getEdgesWith(const std::string& s) const;
272 
280  template <class T>
281  std::set<Edge*> getEdgesWith(const std::string& s, const T& t) const;
282 
284 
285  //---------------------------------------------------------------------
287  //---------------------------------------------------------------------
289 
294  iterator begin();
295 
300  iterator end();
301 
306  const_iterator begin() const;
307 
312  const_iterator end() const;
313 
319  reverse_iterator rbegin();
320 
326  reverse_iterator rend();
327 
333  const_reverse_iterator rbegin() const;
334 
340  const_reverse_iterator rend() const;
341 
343 
344  //---------------------------------------------------------------------
346  //---------------------------------------------------------------------
348 
352  size_t order() const;
353 
357  size_t size() const
358  __attribute__((__deprecated__("use edgeSize() for "
359  "the number of edges. In a future release, size() will return the "
360  "number properties as it does in GenericObject")));
364  size_t edgesSize() const;
365 
370  virtual bool isUndirected() const;
371 
376  virtual bool isDirected() const;
377 
383  virtual bool check(const carto::SyntaxSet& syntax,
384  std::set<std::string>& missing) const;
385 
387 
388 private:
389 
390  //---------------------------------------------------------------------
392  //---------------------------------------------------------------------
394 
400  void internalExtract(Graph& graph, const std::set<Vertex*>& vertices)
401  throw(std::range_error);
402 
404 
405  //---------------------------------------------------------------------
407  //---------------------------------------------------------------------
409 
412  Graph(const Graph&);
413 
416  Graph& operator=(const Graph&);
417 
419 
420  //---------------------------------------------------------------------
422  //---------------------------------------------------------------------
424 
427  std::set<Vertex*> _vertices;
428 
442  std::set<Edge*> _edges;
443 
445 
446 protected:
449  FactoryPtr _factory;
450 
451 };
452 
453 
454 #ifndef DOXYGEN_HIDE_INTERNAL_CLASSES
455 
456 namespace carto
457 {
458 
459  template <> class DataTypeCode< Graph >
460  {
461  public:
462  static std::string objectType()
463  { return "Graph"; }
464  static std::string dataType()
465  { return "VOID"; }
466  static std::string name()
467  {
468  return "Graph";
469  }
470  };
471 
472 }
473 
474 #endif // DOXYGEN_HIDE_INTERNAL_CLASSES
475 
476 
477 //=============================================================================
478 // I N L I N E M E T H O D S
479 //=============================================================================
480 
481 inline
482 const std::set<Vertex*>&
484 {
485  return _vertices;
486 }
487 
488 
489 template <class T>
490 inline
491 std::set<Vertex*>
492 Graph::getVerticesWith(const std::string& s, const T& t) const
493 {
494  std::set<Vertex*> vertices;
495 
496  for (VSet::const_iterator v = begin(); v != end(); ++v)
497  {
498  if ((*v)->hasProperty(s))
499  {
500  T tmp;
501  if ((*v)->getProperty(s, tmp) && tmp == t)
502  {
503  vertices.insert(*v);
504  }
505  }
506  }
507 
508  return vertices;
509 }
510 
511 
512 inline
513 Edge*
514 Graph::addEdge(Vertex* vertex1, Vertex* vertex2, std::string s)
515  throw(std::range_error)
516 {
517  return addUndirectedEdge(vertex1, vertex2, s);
518 }
519 
520 
521 inline
522 const std::set<Edge*>&
524 {
525  return _edges;
526 }
527 
528 
529 template <class T>
530 inline
531 std::set<Edge*>
532 Graph::getEdgesWith(const std::string& s, const T& t) const
533 {
534  std::set<Edge*> edges;
535 
536  for (ESet::iterator e = _edges.begin(); e != _edges.end(); ++e)
537  {
538  if ((*e)->hasProperty(s))
539  {
540  T tmp;
541  if ((*e)->getProperty(s, tmp) && tmp == t)
542  {
543  edges.insert(*e);
544  }
545  }
546  }
547 
548  return edges;
549 }
550 
551 
552 template <class InputIterator>
553 inline
554 void
555 Graph::extract(Graph& graph, InputIterator iv1, InputIterator iv2)
556  throw(std::range_error)
557 {
558  internalExtract(graph, std::set<Vertex*>(iv1, iv2));
559 }
560 
561 
562 inline
565 {
566  return _vertices.begin();
567 }
568 
569 
570 inline
573 {
574  return _vertices.end();
575 }
576 
577 
578 inline
581 {
582  return _vertices.begin();
583 }
584 
585 
586 inline
588 Graph::end() const
589 {
590  return _vertices.end();
591 }
592 
593 
594 inline
597 {
598  return _vertices.rbegin();
599 }
600 
601 
602 inline
605 {
606  return _vertices.rend();
607 }
608 
609 inline
612 {
613  return _vertices.rbegin();
614 }
615 
616 
617 inline
619 Graph::rend() const
620 {
621  return _vertices.rend();
622 }
623 
624 
625 namespace carto
626 {
627  DECLARE_GENERIC_OBJECT_TYPE( Graph * )
628 }
629 
630 #endif
#define DECLARE_GENERIC_OBJECT_TYPE(T)
VSet::pointer pointer
pointer is absent from MS Visual C++ / Intel Win32
Definition: graph.h:83
VSet::const_reference const_reference
Definition: graph.h:86
static std::string dataType()
Definition: graph.h:464
carto::rc_ptr< GraphFactory > FactoryPtr
Definition: graph.h:79
VSet::const_reverse_iterator const_reverse_iterator
Definition: graph.h:90
The base class for graphs.
Definition: graph.h:71
VSet::reference reference
Definition: graph.h:85
static std::string objectType()
Definition: graph.h:462
static std::string name()
Definition: graph.h:466
reverse_iterator rbegin()
Get the beginning of the reversed vertex collection of the graph.
Definition: graph.h:596
The abstract base class for all types of edges; edges are created and managed by Graphs.
Definition: edge.h:68
VSet::reverse_iterator reverse_iterator
Definition: graph.h:89
std::set< Vertex * > getVerticesWith(const std::string &s) const
Find the vertices which contain a given semantic attribute.
VSet::value_type value_type
Definition: graph.h:80
#define GRAPH_API
Definition: graph_config.h:46
std::map< std::string, Syntax > SyntaxSet
const std::set< Edge * > & edges() const
Return the edges of the graph.
Definition: graph.h:523
reverse_iterator rend()
Get the end of the reversed vertex collection of the graph.
Definition: graph.h:604
const std::set< Vertex * > & vertices() const
Return the vertices of the graph.
Definition: graph.h:483
Edge * addEdge(Vertex *vertex1, Vertex *vertex2, std::string s="")
A synonym of addUnDirectedEdge - see above.
Definition: graph.h:514
VSet::const_iterator const_iterator
Definition: graph.h:88
VSet::iterator iterator
Definition: graph.h:87
iterator begin()
Get the beginning of the vertex collection of the graph.
Definition: graph.h:564
std::set< Vertex * > VSet
Definition: graph.h:76
The abstract base class for graphs, vertices and edges.
Definition: graphobject.h:52
void extract(Graph &graph, InputIterator iv1, InputIterator iv2)
Extract a subgraph.
Definition: graph.h:555
std::set< Edge * > ESet
Definition: graph.h:77
Vertices are created and managed by Graphs.
Definition: vertex.h:63
std::set< Edge * > getEdgesWith(const std::string &s) const
Find the edges which contain a given semantic attribute.
iterator end()
Get the end of the vertex collection of the graph.
Definition: graph.h:572