# Changeset 1620:09feafe81053 in lemon-0.x

Ignore:
Timestamp:
08/11/05 15:07:54 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2128
Message:

Start working on UndirGraph? concept clarification and its harmonization with
the directed graph concept.
Not yet done!!!

Location:
lemon/concept
Files:
3 edited

Unmodified
Added
Removed
• ## lemon/concept/graph.h

 r1563 /// \addtogroup graph_concepts /// @{ /**************** The full-featured graph concepts ****************/ }; }; /// \addtogroup graph_concepts /// @{ /// An empty static graph class. /// Inequality operator /// \sa operator==(Node n) /// \sa operator==(Edge n) /// bool operator!=(Edge) const { return true; }
• ## lemon/concept/graph_component.h

 r1563 namespace lemon { namespace concept { /// \addtogroup graph_concepts /// @{ /****************   Graph iterator concepts   ****************/ }; /// @} }
• ## lemon/concept/undir_graph.h

 r1448 #include #include #include namespace lemon { namespace concept { /// \addtogroup graph_concepts /// @{ /// Skeleton class which describes an edge with direction in \ref checkConcept(); checkConcept, UndirEdge>(); checkConcept, Edge>(); //checkConcept, Edge>(); graph.first(ue); }; /// \addtogroup graph_concepts /// @{ /// Class describing the concept of Undirected Graphs. /// a tutorial about undirected graphs. class UndirGraph { class UndirGraph : public StaticGraph { public: ///\e typedef True UndirTag; /// Type describing a node in the graph typedef GraphNode Node; /// Type describing an undirected edge typedef GraphItem<'u'> UndirEdge; /// Type describing an UndirEdge with direction #ifndef DOXYGEN typedef UndirGraphEdge Edge; #else typedef UndirGraphEdge Edge; #endif /// Iterator type which iterates over all nodes #ifndef DOXYGEN typedef GraphIterator NodeIt; #else typedef GraphIterator NodeIt; #endif /// Iterator type which iterates over all undirected edges #ifndef DOXYGEN typedef GraphIterator UndirEdgeIt; #else typedef GraphIterator UndirEdgeIt; #endif /// Iterator type which iterates over all directed edges. /// Iterator type which iterates over all edges (each undirected /// edge occurs twice with both directions. #ifndef DOXYGEN typedef GraphIterator EdgeIt; #else typedef GraphIterator EdgeIt; #endif /// Iterator of undirected edges incident to a node #ifndef DOXYGEN typedef GraphIncIterator IncEdgeIt; #else typedef GraphIncIterator IncEdgeIt; #endif /// Iterator of edges incoming to a node #ifndef DOXYGEN typedef GraphIncIterator InEdgeIt; #else typedef GraphIncIterator InEdgeIt; #endif /// Iterator of edges outgoing from a node #ifndef DOXYGEN typedef GraphIncIterator OutEdgeIt; #else typedef GraphIncIterator OutEdgeIt; #endif /// NodeMap template #ifdef DOXYGEN typedef GraphMap NodeMap; #endif /// UndirEdgeMap template #ifdef DOXYGEN typedef GraphMap UndirEdgeMap; #endif /// EdgeMap template #ifdef DOXYGEN typedef GraphMap EdgeMap; #endif template class NodeMap : public GraphMap { typedef GraphMap Parent; /// The base type of the undirected edge iterators. /// The base type of the undirected edge iterators. /// class UndirEdge { public: explicit NodeMap(const UndirGraph &g) : Parent(g) {} NodeMap(const UndirGraph &g, T t) : Parent(g, t) {} }; template class UndirEdgeMap : public GraphMap { typedef GraphMap Parent; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. UndirEdge() { } /// Copy constructor. /// Copy constructor. /// UndirEdge(const UndirEdge&) { } /// Edge -> UndirEdge conversion /// Edge -> UndirEdge conversion /// UndirEdge(const Edge&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// UndirEdge(Invalid) { } /// Equality operator /// Two iterators are equal if and only if they point to the /// same object or both are invalid. bool operator==(UndirEdge) const { return true; } /// Inequality operator /// \sa operator==(UndirEdge n) /// bool operator!=(UndirEdge) const { return true; } ///\e ///\todo Do we need this? /// bool operator<(const UndirEdge &that) const { return true; } }; /// This iterator goes through each undirected edge. /// This iterator goes through each undirected edge of a graph. /// Its usage is quite simple, for example you can count the number /// of edges in a graph \c g of type \c Graph as follows: /// \code /// int count=0; /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count; /// \endcode class UndirEdgeIt : public UndirEdge { public: explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {} UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} }; template class EdgeMap : public GraphMap { typedef GraphMap Parent; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. UndirEdgeIt() { } /// Copy constructor. /// Copy constructor. /// UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// UndirEdgeIt(Invalid) { } /// This constructor sets the iterator to the first edge. /// This constructor sets the iterator to the first edge of \c g. ///@param g the graph UndirEdgeIt(const UndirGraph&) { } /// UndirEdge -> UndirEdgeIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. UndirEdgeIt(const UndirGraph&, const UndirEdge&) { } ///Next edge /// Assign the iterator to the next edge. UndirEdgeIt& operator++() { return *this; } }; /// This iterator goes trough the incident undirected edges of a node. /// This iterator goes trough the incident undirected edges /// of a certain node /// of a graph. /// Its usage is quite simple, for example you can compute the /// degree (i.e. count the number /// of incident edges of a node \c n /// in graph \c g of type \c Graph as follows. /// \code /// int count=0; /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; /// \endcode class IncEdgeIt : public UndirEdge { public: explicit EdgeMap(const UndirGraph &g) : Parent(g) {} EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. IncEdgeIt() { } /// Copy constructor. /// Copy constructor. /// IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// IncEdgeIt(Invalid) { } /// This constructor sets the iterator to first incident edge. /// This constructor set the iterator to the first incident edge of /// the node. ///@param n the node ///@param g the graph IncEdgeIt(const UndirGraph&, const Node&) { } /// UndirEdge -> IncEdgeIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. IncEdgeIt(const UndirGraph&, const UndirEdge&) { } /// Next incident edge /// Assign the iterator to the next incident edge /// of the corresponding node. IncEdgeIt& operator++() { return *this; } }; /// Read write map of the undirected edges to type \c T. /// Reference map of the edges to type \c T. /// \sa Reference /// \warning Making maps that can handle bool type (UndirEdgeMap) /// needs some extra attention! template class UndirEdgeMap : public ReadWriteMap { public: ///\e UndirEdgeMap(const UndirGraph&) { } ///\e UndirEdgeMap(const UndirGraph&, T) { } ///Copy constructor UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap(em) { } ///Assignment operator UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; } // \todo fix this concept };
Note: See TracChangeset for help on using the changeset viewer.