graph.h

Go to the documentation of this file.

/* This software and supporting documentation are distributed by
 *     Institut Federatif de Recherche 49
 *     CEA/NeuroSpin, Batiment 145,
 *     91191 Gif-sur-Yvette cedex
 *     France
 *
 * This software is governed by the CeCILL-B license under
 * French law and abiding by the rules of distribution of free software.
 * You can  use, modify and/or redistribute the software under the
 * terms of the CeCILL-B license as circulated by CEA, CNRS
 * and INRIA at the following URL "http://www.cecill.info".
 *
 * As a counterpart to the access to the source code and  rights to copy,
 * modify and redistribute granted by the license, users are provided only
 * with a limited warranty  and the software's author,  the holder of the
 * economic rights,  and the successive licensors  have only  limited
 * liability.
 *
 * In this respect, the user's attention is drawn to the risks associated
 * with loading,  using,  modifying and/or developing or reproducing the
 * software by the user in light of its specific status of free software,
 * that may mean  that it is complicated to manipulate,  and  that  also
 * therefore means  that it is reserved for developers  and  experienced
 * professionals having in-depth computer knowledge. Users are therefore
 * encouraged to load and test the software's suitability as regards their
 * requirements in conditions enabling the security of their systems and/or
 * data to be ensured and,  more generally, to use and operate it in the
 * same conditions as regards security.
 *
 * The fact that you are presently reading this means that you have had
 * knowledge of the CeCILL-B license and that you accept its terms.
 */

#ifndef GRAPH_GRAPH_GRAPH_H
#define GRAPH_GRAPH_GRAPH_H


//=============================================================================
//    H E A D E R  F I L E S
//=============================================================================

#include <graph/config/graph_config.h>
#ifndef GRAPH_GRAPH_GRAPHOBJECT_H
#include <graph/graph/graphobject.h>
#endif
#ifndef GRAPH_GRAPH_VERTEX_H
#include <graph/graph/vertex.h>
#endif
#ifndef GRAPH_GRAPH_EDGE_H
#include <graph/graph/edge.h>
#endif
#ifndef GRAPH_GRAPH_GFACTORY_H
#include <graph/graph/gfactory.h>
#endif
#include <cartobase/smart/rcptr.h>
#include <cartobase/type/types.h>

#include <algorithm>
#include <functional>
#include <set>
#include <stdexcept>


//=============================================================================
//    C L A S S  D E C L A R A T I O N
//=============================================================================

class GRAPH_API Graph : public GraphObject
{

public:

    typedef std::set<Vertex*> VSet;
    typedef std::set<Edge*> ESet;

    typedef carto::rc_ptr<GraphFactory>   FactoryPtr;
    typedef VSet::value_type             value_type;
#ifndef _WIN32
    typedef VSet::pointer                pointer;
#endif
    typedef VSet::reference              reference;
    typedef VSet::const_reference        const_reference;
    typedef VSet::iterator               iterator;
    typedef VSet::const_iterator         const_iterator;
    typedef VSet::reverse_iterator       reverse_iterator;
    typedef VSet::const_reverse_iterator const_reverse_iterator;

    Graph(const std::string& s = "");

    Graph(const FactoryPtr factory, const std::string& s = "");

    virtual ~Graph();

    template <class InputIterator>
    void extract(Graph& graph, InputIterator iv1, InputIterator iv2);

    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    void clear();


    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    Vertex* addVertex(const std::string& s = "");

    Vertex* cloneVertex(const Vertex* vertex);

    bool hasVertex(const Vertex* vertex) const;

    void removeVertex(Vertex* vertex);

    Vertex* randomVertex() const;

    const std::set<Vertex*>& vertices() const;

    std::set<Vertex*> getVerticesWith(const std::string& s) const;

    template <class T>
    std::set<Vertex*> getVerticesWith(const std::string& s,
                      const T& t) const;


    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    Edge* addUndirectedEdge(Vertex* vertex1, Vertex* vertex2, std::
                string s);

    Edge* addEdge(Vertex* vertex1, Vertex* vertex2, std::string s = "");

    Edge* addDirectedEdge(Vertex* vertex1, Vertex* vertex2, std::string s);

    bool hasEdge(const Edge* edge) const;

    void removeEdge(Edge* edge);

    const std::set<Edge*>& edges() const;

    std::set<Edge*> edges(const Vertex* vertex1,
                  const Vertex* vertex2) const;

    std::set<Edge*> getEdgesWith(const std::string& s) const;

    template <class T>
    std::set<Edge*> getEdgesWith(const std::string& s, const T& t) const;


    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    iterator begin();

    iterator end();

    const_iterator begin() const;

    const_iterator end() const;

    reverse_iterator rbegin();

    reverse_iterator rend();

    const_reverse_iterator rbegin() const;

    const_reverse_iterator rend() const;


    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    size_t order() const;

    size_t size() const
#ifndef AIMS_GRAPH_SIZE_NO_DEPREC_WARNING
      __attribute__((__deprecated__("use edgeSize() for "
        "the number of edges. In a future release, size() will return the "
        "number properties as it does in GenericObject")))
#endif
        ;
    size_t edgesSize() const;

    virtual bool isUndirected() const;

    virtual bool isDirected() const;

    virtual bool check(const carto::SyntaxSet& syntax,
               std::set<std::string>& missing) const;


private:

    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    void internalExtract(Graph& graph, const std::set<Vertex*>& vertices);


    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    Graph(const Graph&);

    Graph& operator=(const Graph&);


    //---------------------------------------------------------------------
    //---------------------------------------------------------------------

    std::set<Vertex*> _vertices;

    std::set<Edge*> _edges;


protected:
    FactoryPtr _factory;

};


#ifndef DOXYGEN_HIDE_INTERNAL_CLASSES

namespace carto
{

  template <> class DataTypeCode< Graph >
  {
  public:
    static std::string objectType()
    { return "Graph"; }
    static std::string dataType()
    { return "VOID"; }
    static std::string name() 
    { 
      return "Graph"; 
    }
  };

}

#endif // DOXYGEN_HIDE_INTERNAL_CLASSES


//=============================================================================
//    I N L I N E  M E T H O D S
//=============================================================================

inline
const std::set<Vertex*>&
Graph::vertices() const
{
    return _vertices;
}


template <class T>
inline
std::set<Vertex*>
Graph::getVerticesWith(const std::string& s, const T& t) const
{
    std::set<Vertex*> vertices;

    for (VSet::const_iterator v = begin(); v != end(); ++v)
    {
        if ((*v)->hasProperty(s))
        {
            T tmp;
            if ((*v)->getProperty(s, tmp) && tmp == t)
            {
                vertices.insert(*v);
            }
        }
    }

    return vertices;
}


inline
Edge*
Graph::addEdge(Vertex* vertex1, Vertex* vertex2, std::string s) 
{
    return addUndirectedEdge(vertex1, vertex2, s);
}


inline
const std::set<Edge*>&
Graph::edges() const
{
    return _edges;
}


template <class T>
inline
std::set<Edge*>
Graph::getEdgesWith(const std::string& s, const T& t) const
{
    std::set<Edge*> edges;

    for (ESet::iterator e = _edges.begin(); e != _edges.end(); ++e)
    {
        if ((*e)->hasProperty(s))
        {
            T tmp;
            if ((*e)->getProperty(s, tmp) && tmp == t)
            {
                edges.insert(*e);
            }
        }
    }

    return edges;
}


template <class InputIterator>
inline
void
Graph::extract(Graph& graph, InputIterator iv1, InputIterator iv2)
{
    internalExtract(graph, std::set<Vertex*>(iv1, iv2));
}


inline
Graph::iterator
Graph::begin()
{
    return _vertices.begin();
}


inline
Graph::iterator
Graph::end()
{
    return _vertices.end();
}


inline
Graph::const_iterator
Graph::begin() const
{
    return _vertices.begin();
}


inline
Graph::const_iterator
Graph::end() const
{
    return _vertices.end();
}


inline
Graph::reverse_iterator
Graph::rbegin()
{
    return _vertices.rbegin();
}


inline
Graph::reverse_iterator
Graph::rend()
{
    return _vertices.rend();
}

inline
Graph::const_reverse_iterator
Graph::rbegin() const
{
    return _vertices.rbegin();
}


inline
Graph::const_reverse_iterator
Graph::rend() const
{
    return _vertices.rend();
}


namespace carto
{
  DECLARE_GENERIC_OBJECT_TYPE( Graph * )
}

#endif