# Changeset 2111:ea1fa1bc3f6d in lemon-0.x

Ignore:
Timestamp:
06/28/06 17:06:24 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2817
Message:

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

Files:
30 edited

Unmodified
Removed
• ## doc/graphs.dox

 r1638 \page graphs Graphs \todo Write a new Graphs page. I think it should be contain the Graph, UGraph and BpUGraph concept. It should be describe the iterators and the basic functions and the differences of the implementations. The primary data structures of LEMON are the graph classes. They all as  incoming and outgoing edges of a given node. Each graph should meet the \ref lemon::concept::Graph "Graph" concept. This concept does not make it possible to change the graph (i.e. it is not possible to add or delete edges or nodes). Most of the graph algorithms will run on these graphs. Each graph should meet the \ref lemon::concept::StaticGraph "StaticGraph" concept. This concept does not make it possible to change the graph (i.e. it is not possible to add or delete edges or nodes). Most of the graph algorithms will run on these graphs. The graphs meeting the \ref lemon::concept::ExtendableGraph "ExtendableGraph" concept allow node and edge addition. You can also "clear" such a graph (i.e. erase all edges and nodes ). In case of graphs meeting the full feature \li \ref lemon::FullGraph "FullGraph" implements a complete graph. It is a \ref lemon::concept::StaticGraph "StaticGraph", so you cannot \ref lemon::concept::Graph "Graph", so you cannot change the number of nodes once it is constructed. It is extremely memory efficient: it uses constant amount of memory independently from the number of
• ## lemon/bellman_ford.h

 r2074 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. /// \param _LengthMap This read-only EdgeMap determines the lengths of the /// edges. The default map type is \ref concept::StaticGraph::EdgeMap /// edges. The default map type is \ref concept::Graph::EdgeMap /// "Graph::EdgeMap".  The value of _LengthMap is not used directly /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
• ## lemon/concept/bpugraph.h

 r1993 }; /// \brief An empty non-static undirected graph class. /// /// This class provides everything that \ref BpUGraph does. /// Additionally it enables building graphs from scratch. class ExtendableBpUGraph : public BpUGraph { public: /// \brief Add a new ANode to the graph. /// /// Add a new ANode to the graph. /// \return the new node. Node addANode(); /// \brief Add a new ANode to the graph. /// /// Add a new ANode to the graph. /// \return the new node. Node addBNode(); /// \brief Add a new undirected edge to the graph. /// /// Add a new undirected edge to the graph. One of the nodes /// should be ANode and the other should be BNode. /// \pre The nodes are not in the same nodeset. /// \return the new edge. UEdge addEdge(const Node& from, const Node& to); /// \brief Resets the graph. /// /// This function deletes all undirected edges and nodes of the graph. /// It also frees the memory allocated to store them. void clear() { } template struct Constraints { void constraints() {} }; }; /// \brief An empty erasable undirected graph class. /// /// This class is an extension of \ref ExtendableBpUGraph. It makes it /// possible to erase undirected edges or nodes. class ErasableBpUGraph : public ExtendableBpUGraph { public: /// \brief Deletes a node. /// /// Deletes a node. /// void erase(Node) { } /// \brief Deletes an undirected edge. /// /// Deletes an undirected edge. /// void erase(UEdge) { } template struct Constraints { void constraints() {} }; }; /// @}
• ## lemon/concept/graph.h

 r2090 // \brief Modular static graph class. // // It should be the same as the \c StaticGraph class. class _StaticGraph // It should be the same as the \c Graph class. class _Graph :  virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { }; // \brief Modular extendable graph class. // // It should be the same as the \c ExtendableGraph class. class _ExtendableGraph :  virtual public BaseGraphComponent, public _StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { public: typedef BaseGraphComponent::Node Node; typedef BaseGraphComponent::Edge Edge; template struct Constraints { void constraints() { checkConcept<_StaticGraph, _Graph >(); checkConcept(); checkConcept(); } }; }; // \brief Modular erasable graph class. // // It should be the same as the \c ErasableGraph class. class _ErasableGraph :  virtual public BaseGraphComponent, public _ExtendableGraph, public ErasableGraphComponent { public: typedef BaseGraphComponent::Node Node; typedef BaseGraphComponent::Edge Edge; template struct Constraints { void constraints() { checkConcept<_ExtendableGraph, _Graph >(); checkConcept(); } }; }; /// \addtogroup graph_concepts /// @{ /// An empty static graph class. /// An empty graph class. /// This class provides all the common features of a graph structure, /// \todo A pages describing the concept of concept description would /// be nice. class StaticGraph { //      ///Copy consructor. //       ///\todo It is not clear, what we expect from a copy constructor. //       ///E.g. How to assign the nodes/edges to each other? What about maps? //       StaticGraph(const StaticGraph& g) { } class Graph { public: ///\e /// Defalult constructor. /// StaticGraph() { } Graph() { } /// The base type of node iterators, /// Sets the iterator to the first node of \c g. /// NodeIt(const StaticGraph&) { } NodeIt(const Graph&) { } /// Node -> NodeIt conversion. /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. NodeIt(const StaticGraph&, const Node&) { } NodeIt(const Graph&, const Node&) { } /// Next node. /// This constructor sets the iterator to the first outgoing edge of /// the node. OutEdgeIt(const StaticGraph&, const Node&) { } OutEdgeIt(const Graph&, const Node&) { } /// Edge -> OutEdgeIt conversion /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. OutEdgeIt(const StaticGraph&, const Edge&) { } OutEdgeIt(const Graph&, const Edge&) { } ///Next outgoing edge /// This constructor set the iterator to the first incoming edge of /// the node. InEdgeIt(const StaticGraph&, const Node&) { } InEdgeIt(const Graph&, const Node&) { } /// Edge -> InEdgeIt conversion /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. InEdgeIt(const StaticGraph&, const Edge&) { } InEdgeIt(const Graph&, const Edge&) { } /// Next incoming edge /// This constructor sets the iterator to the first edge of \c g. ///@param g the graph EdgeIt(const StaticGraph& g) { ignore_unused_variable_warning(g); } EdgeIt(const Graph& g) { ignore_unused_variable_warning(g); } /// Edge -> EdgeIt conversion /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the same. EdgeIt(const StaticGraph&, const Edge&) { } EdgeIt(const Graph&, const Edge&) { } ///Next edge Node source(Edge) const { return INVALID; } //       /// Gives back the first Node in the iterating order. //       /// Gives back the first Node in the iterating order. //       /// void first(Node&) const {} //       /// Gives back the next Node in the iterating order. //       /// Gives back the next Node in the iterating order. //       /// void next(Node&) const {} //       /// Gives back the first Edge in the iterating order. //       /// Gives back the first Edge in the iterating order. //       /// void first(Edge&) const {} //       /// Gives back the next Edge in the iterating order. //       /// Gives back the next Edge in the iterating order. //       /// void next(Edge&) const {} //       /// Gives back the first of the Edges point to the given Node. //       /// Gives back the first of the Edges point to the given Node. //       /// void firstIn(Edge&, const Node&) const {} //       /// Gives back the next of the Edges points to the given Node. //       /// Gives back the next of the Edges points to the given Node. //       /// void nextIn(Edge&) const {} //       /// Gives back the first of the Edges start from the given Node. //       /// Gives back the first of the Edges start from the given Node. //       /// void firstOut(Edge&, const Node&) const {} //       /// Gives back the next of the Edges start from the given Node. //       /// Gives back the next of the Edges start from the given Node. //       /// void nextOut(Edge&) const {} ///\e NodeMap(const StaticGraph&) { } NodeMap(const Graph&) { } ///\e NodeMap(const StaticGraph&, T) { } NodeMap(const Graph&, T) { } ///Copy constructor ///\e EdgeMap(const StaticGraph&) { } EdgeMap(const Graph&) { } ///\e EdgeMap(const StaticGraph&, T) { } EdgeMap(const Graph&, T) { } ///Copy constructor EdgeMap(const EdgeMap& em) : ReadWriteMap(em) { } }; template struct Constraints : public _StaticGraph::Constraints<_Graph> {}; }; /// An empty non-static graph class. /// This class provides everything that \ref StaticGraph does. /// Additionally it enables building graphs from scratch. class ExtendableGraph : public StaticGraph { public: /// Defalult constructor. /// Defalult constructor. /// ExtendableGraph() { } ///Add a new node to the graph. /// \return the new node. /// Node addNode() { return INVALID; } ///Add a new edge to the graph. ///Add a new edge to the graph with source node \c s ///and target node \c t. ///\return the new edge. Edge addEdge(Node, Node) { return INVALID; } /// Resets the graph. /// This function deletes all edges and nodes of the graph. /// It also frees the memory allocated to store them. /// \todo It might belong to \ref ErasableGraph. void clear() { } template struct Constraints : public _ExtendableGraph::Constraints<_Graph> {}; }; /// An empty erasable graph class. /// This class is an extension of \ref ExtendableGraph. It makes it /// possible to erase edges or nodes. class ErasableGraph : public ExtendableGraph { public: /// Defalult constructor. /// Defalult constructor. /// ErasableGraph() { } /// Deletes a node. /// Deletes node \c n node. /// void erase(Node) { } /// Deletes an edge. /// Deletes edge \c e edge. /// void erase(Edge) { } template struct Constraints : public _ErasableGraph::Constraints<_Graph> {}; template struct Constraints : public _Graph::Constraints {}; };
• ## lemon/concept/graph_component.h

 r1999 /// core clear functions for the graph structure. /// The most of the base graphs should be conform to this concept. class ClearableGraphComponent : virtual public BaseGraphComponent { class BaseClearableGraphComponent : virtual public BaseGraphComponent { public: /// This class provides beside the core graph features /// iterator based iterable interface for the graph structure. /// This concept is part of the StaticGraphConcept. /// This concept is part of the GraphConcept. class IterableGraphComponent : virtual public BaseGraphComponent { /// This class provides beside the core graph features /// map interface for the graph structure. /// This concept is part of the StaticGraphConcept. /// This concept is part of the GraphConcept. class MappableGraphComponent : virtual public BaseGraphComponent { public: }; /// \brief An empty extendable extended graph class. /// /// This class provides beside the core graph features /// item addition interface for the graph structure. /// The difference between this class and the /// \c BaseExtendableGraphComponent is that it should /// notify the item alteration observers. class ExtendableGraphComponent : virtual public BaseGraphComponent { public: typedef ExtendableGraphComponent Graph; typedef BaseGraphComponent::Node Node; typedef BaseGraphComponent::Edge Edge; /// \brief Add a node to the graph. /// /// Add a node to the graph and notify the observers. Node addNode() { return INVALID; //     /// Skeleton class which describes an edge with direction in \ref //     /// UGraph "undirected graph". template class UGraphEdge : public UGraph::UEdge { typedef typename UGraph::UEdge UEdge; typedef typename UGraph::Node Node; public: /// \e UGraphEdge() {} /// \e UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {} /// \e UGraphEdge(Invalid) {} /// \brief Directed edge from undirected edge and a source node. /// /// Constructs a directed edge from undirected edge and a source node. /// /// \note You have to specify the graph for this constructor. UGraphEdge(const UGraph &g, UEdge u_edge, Node n) { ignore_unused_variable_warning(u_edge); ignore_unused_variable_warning(g); ignore_unused_variable_warning(n); } /// \e UGraphEdge& operator=(UGraphEdge) { return *this; } /// \e bool operator==(UGraphEdge) const { return true; } /// \e bool operator!=(UGraphEdge) const { return false; } /// \e bool operator<(UGraphEdge) const { return false; } template struct Constraints { void constraints() { const_constraints(); } void const_constraints() const { /// \bug This should be is_base_and_derived ... UEdge ue = e; ue = e; Edge e_with_source(graph,ue,n); ignore_unused_variable_warning(e_with_source); } Edge e; UEdge ue; UGraph graph; Node n; }; }; /// \brief Add an edge to the graph. /// /// Add an edge to the graph and notify the observers. Edge addEdge(const Node&, const Node&) { return INVALID; } template struct Constraints { void constraints() { checkConcept(); typename _Graph::Node node_a, node_b; node_a = graph.addNode(); node_b = graph.addNode(); typename _Graph::Edge edge; edge = graph.addEdge(node_a, node_b); } _Graph& graph; }; }; /// \brief An empty erasable extended graph class. /// /// This class provides beside the core graph features /// item erase interface for the graph structure. /// The difference between this class and the /// \c BaseErasableGraphComponent is that it should /// notify the item alteration observers. class ErasableGraphComponent : virtual public BaseGraphComponent { public: typedef ErasableGraphComponent Graph; typedef BaseGraphComponent::Node Node; typedef BaseGraphComponent::Edge Edge; /// \brief Erase the Node and notify the node alteration observers. /// ///  Erase the Node and notify the node alteration observers. void erase(const Node&) {} /// \brief Erase the Edge and notify the edge alteration observers. /// ///  Erase the Edge and notify the edge alteration observers. void erase(const Edge&) {} template struct Constraints { void constraints() { checkConcept(); typename _Graph::Node node; graph.erase(node); typename _Graph::Edge edge; graph.erase(edge); } _Graph& graph; }; struct BaseIterableUGraphConcept { template struct Constraints { typedef typename Graph::UEdge UEdge; typedef typename Graph::Edge Edge; typedef typename Graph::Node Node; void constraints() { checkConcept(); checkConcept, UEdge>(); //checkConcept, Edge>(); graph.first(ue); graph.next(ue); const_constraints(); } void const_constraints() { Node n; n = graph.target(ue); n = graph.source(ue); n = graph.oppositeNode(n0, ue); bool b; b = graph.direction(e); Edge e = graph.direct(UEdge(), true); e = graph.direct(UEdge(), n); ignore_unused_variable_warning(b); } Graph graph; Edge e; Node n0; UEdge ue; }; }; struct IterableUGraphConcept { template struct Constraints { void constraints() { /// \todo we don't need the iterable component to be base iterable /// Don't we really??? //checkConcept< BaseIterableUGraphConcept, Graph > (); checkConcept (); typedef typename Graph::UEdge UEdge; typedef typename Graph::UEdgeIt UEdgeIt; typedef typename Graph::IncEdgeIt IncEdgeIt; checkConcept, UEdgeIt>(); checkConcept, IncEdgeIt>(); } }; }; struct MappableUGraphConcept { template struct Constraints { struct Dummy { int value; Dummy() : value(0) {} Dummy(int _v) : value(_v) {} }; void constraints() { checkConcept(); typedef typename Graph::template UEdgeMap IntMap; checkConcept, IntMap >(); typedef typename Graph::template UEdgeMap BoolMap; checkConcept, BoolMap >(); typedef typename Graph::template UEdgeMap DummyMap; checkConcept, DummyMap >(); } }; };
• ## lemon/concept/ugraph.h

 r2021 ///\ingroup graph_concepts ///\file ///\brief Undirected graphs and components of. ///\brief The concept of the undirected graphs. namespace lemon { namespace concept { //     /// Skeleton class which describes an edge with direction in \ref //     /// UGraph "undirected graph". template class UGraphEdge : public UGraph::UEdge { typedef typename UGraph::UEdge UEdge; typedef typename UGraph::Node Node; public: /// \e UGraphEdge() {} /// \e UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {} /// \e UGraphEdge(Invalid) {} /// \brief Directed edge from undirected edge and a source node. /// /// Constructs a directed edge from undirected edge and a source node. /// /// \note You have to specify the graph for this constructor. UGraphEdge(const UGraph &g, UEdge u_edge, Node n) { ignore_unused_variable_warning(u_edge); ignore_unused_variable_warning(g); ignore_unused_variable_warning(n); } /// \e UGraphEdge& operator=(UGraphEdge) { return *this; } /// \e bool operator==(UGraphEdge) const { return true; } /// \e bool operator!=(UGraphEdge) const { return false; } /// \e bool operator<(UGraphEdge) const { return false; } template struct Constraints { void constraints() { const_constraints(); } void const_constraints() const { /// \bug This should be is_base_and_derived ... UEdge ue = e; ue = e; Edge e_with_source(graph,ue,n); ignore_unused_variable_warning(e_with_source); } Edge e; UEdge ue; UGraph graph; Node n; }; }; struct BaseIterableUGraphConcept { template struct Constraints { typedef typename Graph::UEdge UEdge; typedef typename Graph::Edge Edge; typedef typename Graph::Node Node; void constraints() { checkConcept(); checkConcept, UEdge>(); //checkConcept, Edge>(); graph.first(ue); graph.next(ue); const_constraints(); } void const_constraints() { Node n; n = graph.target(ue); n = graph.source(ue); n = graph.oppositeNode(n0, ue); bool b; b = graph.direction(e); Edge e = graph.direct(UEdge(), true); e = graph.direct(UEdge(), n); ignore_unused_variable_warning(b); } Graph graph; Edge e; Node n0; UEdge ue; }; }; struct IterableUGraphConcept { template struct Constraints { void constraints() { /// \todo we don't need the iterable component to be base iterable /// Don't we really??? //checkConcept< BaseIterableUGraphConcept, Graph > (); checkConcept (); typedef typename Graph::UEdge UEdge; typedef typename Graph::UEdgeIt UEdgeIt; typedef typename Graph::IncEdgeIt IncEdgeIt; checkConcept, UEdgeIt>(); checkConcept, IncEdgeIt>(); } }; }; struct MappableUGraphConcept { template struct Constraints { struct Dummy { int value; Dummy() : value(0) {} Dummy(int _v) : value(_v) {} }; void constraints() { checkConcept(); typedef typename Graph::template UEdgeMap IntMap; checkConcept, IntMap >(); typedef typename Graph::template UEdgeMap BoolMap; checkConcept, BoolMap >(); typedef typename Graph::template UEdgeMap DummyMap; checkConcept, DummyMap >(); } }; }; struct ExtendableUGraphConcept { template struct Constraints { void constraints() { node_a = graph.addNode(); uedge = graph.addEdge(node_a, node_b); } typename Graph::Node node_a, node_b; typename Graph::UEdge uedge; Graph graph; }; }; struct ErasableUGraphConcept { template struct Constraints { void constraints() { graph.erase(n); graph.erase(e); } Graph graph; typename Graph::Node n; typename Graph::UEdge e; }; }; /// \addtogroup graph_concepts /// /// In LEMON undirected graphs also fulfill the concept of directed /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For /// explanation of this and more see also the page \ref ugraphs, /// a tutorial about undirected graphs. /// graphs (\ref lemon::concept::Graph "Graph Concept"). For /// explanation of this and more see also the page \ref graphs, /// a tutorial about graphs. /// /// You can assume that all undirected graph can be handled /// as a static directed graph. This way it is fully conform /// to the StaticGraph concept. /// as a directed graph. This way it is fully conform /// to the Graph concept. class UGraph { Node target(Edge) const { return INVALID; } //       /// \brief First node of the graph //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void first(Node&) const {} //       /// \brief Next node of the graph //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void next(Node&) const {} //       /// \brief First undirected edge of the graph //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void first(UEdge&) const {} //       /// \brief Next undirected edge of the graph //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void next(UEdge&) const {} //       /// \brief First directed edge of the graph //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void first(Edge&) const {} //       /// \brief Next directed edge of the graph //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void next(Edge&) const {} //       /// \brief First outgoing edge from a given node //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void firstOut(Edge&, Node) const {} //       /// \brief Next outgoing edge to a node //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void nextOut(Edge&) const {} //       /// \brief First incoming edge to a given node //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void firstIn(Edge&, Node) const {} //       /// \brief Next incoming edge to a node //       /// //       /// \note This method is part of so called \ref //       /// developpers_interface "Developpers' interface", so it shouldn't //       /// be used in an end-user program. void nextIn(Edge&) const {} void firstInc(UEdge &, bool &, const Node &) const {} void nextInc(UEdge &, bool &) const {} }; /// \brief An empty non-static undirected graph class. /// /// This class provides everything that \ref UGraph does. /// Additionally it enables building graphs from scratch. class ExtendableUGraph : public UGraph { public: /// \brief Add a new node to the graph. /// /// Add a new node to the graph. /// \return the new node. Node addNode(); /// \brief Add a new undirected edge to the graph. /// /// Add a new undirected edge to the graph. /// \return the new edge. UEdge addEdge(const Node& from, const Node& to); /// \brief Resets the graph. /// /// This function deletes all undirected edges and nodes of the graph. /// It also frees the memory allocated to store them. void clear() { } template struct Constraints { void constraints() { checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); } }; }; /// \brief An empty erasable undirected graph class. /// /// This class is an extension of \ref ExtendableUGraph. It makes it /// possible to erase undirected edges or nodes. class ErasableUGraph : public ExtendableUGraph { public: /// \brief Deletes a node. /// /// Deletes a node. /// void erase(Node) { } /// \brief Deletes an undirected edge. /// /// Deletes an undirected edge. /// void erase(UEdge) { } template struct Constraints { void constraints() { checkConcept(); checkConcept(); } }; }; /// @}
• ## lemon/dag_shortest_path.h

 r1999 /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. /// \param _LengthMap This read-only EdgeMap determines the lengths of the /// edges. The default map type is \ref concept::StaticGraph::EdgeMap /// edges. The default map type is \ref concept::Graph::EdgeMap /// "Graph::EdgeMap".  The value of _LengthMap is not used directly /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
• ## lemon/dijkstra.h

 r2010 ///relatively time consuming process to compute the edge length if ///it is necessary. The default map type is \ref ///concept::StaticGraph::EdgeMap "Graph::EdgeMap".  The value ///concept::Graph::EdgeMap "Graph::EdgeMap".  The value ///of LM is not used directly by Dijkstra, it is only passed to \ref ///DijkstraDefaultTraits.  \param TR Traits class to set
• ## lemon/edge_set.h

 r2076 /// /// \param _Graph The type of the graph which shares its node set with /// this class. Its interface must conform to the \ref concept::StaticGraph /// "StaticGraph" concept. /// this class. Its interface must conform to the \ref concept::Graph /// "Graph" concept. /// /// In the edge extension and removing it conforms to the /// \ref concept::ErasableGraph "ErasableGraph" concept. /// \ref concept::Graph "Graph" concept. template class ListEdgeSet : public EdgeSetExtender > { /// /// \param _Graph The type of the graph which shares its node set with /// this class. Its interface must conform to the \ref concept::StaticGraph /// "StaticGraph" concept. /// this class. Its interface must conform to the \ref concept::Graph /// "Graph" concept. /// /// In the edge extension and removing it conforms to the /// \ref concept::ErasableUGraph "ErasableUGraph" concept. /// \ref concept::UGraph "UGraph" concept. template class ListUEdgeSet /// /// \param _Graph The type of the graph which shares its node set with /// this class. Its interface must conform to the \ref concept::StaticGraph /// "StaticGraph" concept. /// this class. Its interface must conform to the \ref concept::Graph /// "Graph" concept. /// /// In the edge extension and removing it conforms to the /// \ref concept::ExtendableGraph "ExtendableGraph" concept. /// \ref concept::Graph "Graph" concept. template class SmartEdgeSet : public EdgeSetExtender > { /// /// \param _Graph The type of the graph which shares its node set with /// this class. Its interface must conform to the \ref concept::StaticGraph /// "StaticGraph" concept. /// this class. Its interface must conform to the \ref concept::Graph /// "Graph" concept. /// /// In the edge extension and removing it conforms to the /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept. /// \ref concept::UGraph "UGraph" concept. template class SmartUEdgeSet
• ## lemon/floyd_warshall.h

 r2042 /// relatively time consuming process to compute the edge length if /// it is necessary. The default map type is \ref /// concept::StaticGraph::EdgeMap "Graph::EdgeMap".  The value /// concept::Graph::EdgeMap "Graph::EdgeMap".  The value /// of _LengthMap is not used directly by FloydWarshall, it is only passed /// to \ref FloydWarshallDefaultTraits.  \param _Traits Traits class to set
• ## lemon/full_graph.h

 r2076 /// edges or nodes. /// Thus it conforms to /// the \ref concept::StaticGraph "StaticGraph" concept /// \sa concept::StaticGraph. /// the \ref concept::Graph "Graph" concept /// \sa concept::Graph. /// /// \sa FullGraphBase

 r2084 /// /// This graph adaptor is fully conform to the /// \ref concept::StaticGraph "StaticGraph" concept and /// \ref concept::Graph "Graph" concept and /// contains some additional member functions and types. The /// documentation of some member functions may be found just in the
• ## lemon/hypercube_graph.h

 r1998 /// is 26. /// /// The graph type is fully conform to the \ref concept::StaticGraph /// The graph type is fully conform to the \ref concept::Graph /// concept but it does not conform to the \ref concept::UGraph. ///
• ## lemon/johnson.h

 r2042 /// relatively time consuming process to compute the edge length if /// it is necessary. The default map type is \ref /// concept::StaticGraph::EdgeMap "Graph::EdgeMap".  The value /// concept::Graph::EdgeMap "Graph::EdgeMap".  The value /// of _LengthMap is not used directly by Johnson, it is only passed /// to \ref JohnsonDefaultTraits.  \param _Traits Traits class to set
• ## lemon/kruskal.h

 r2084 /// /// \param g The graph the algorithm runs on. /// It can be either \ref concept::StaticGraph "directed" or /// It can be either \ref concept::Graph "directed" or /// \ref concept::UGraph "undirected". /// If the graph is directed, the algorithm consider it to be
• ## lemon/list_graph.h

 r2107 protected: void _changeTarget(Edge e, Node n) void changeTarget(Edge e, Node n) { if(edges[e.id].next_in != -1) nodes[n.id].first_in = e.id; } void _changeSource(Edge e, Node n) void changeSource(Edge e, Node n) { if(edges[e.id].next_out != -1) ///This is a simple and fast erasable graph implementation. /// ///It conforms to the ///\ref concept::ErasableGraph "ErasableGraph" concept and ///it also provides several additional useful extra functionalities. ///\sa concept::ErasableGraph. ///It conforms to the \ref concept::Graph "Graph" concept and it ///also provides several additional useful extra functionalities. ///The most of the member functions and nested classes are ///documented only in the concept class. ///\sa concept::Graph. class ListGraph : public ExtendedListGraphBase { typedef ExtendedListGraphBase Parent; ///Add a new node to the graph. /// \return the new node. /// Node addNode() { return Parent::addNode(); } ///Add a new edge to the graph. ///Add a new edge to the graph with source node \c s ///and target node \c t. ///\return the new edge. Edge addEdge(const Node& s, const Node& t) { return Parent::addEdge(s, t); } /// Changes the target of \c e to \c n ///valid. However InEdges are invalidated. void changeTarget(Edge e, Node n) { _changeTarget(e,n); Parent::changeTarget(e,n); } /// Changes the source of \c e to \c n ///valid. However OutEdges are invalidated. void changeSource(Edge e, Node n) { _changeSource(e,n); Parent::changeSource(e,n); } void reverseEdge(Edge e) { Node t=target(e); _changeTarget(e,source(e)); _changeSource(e,t); } ///Using this it is possible to avoid the superfluous memory ///allocation. changeTarget(e,source(e)); changeSource(e,t); } /// \brief Using this it is possible to avoid the superfluous memory /// allocation. ///Using this it is possible to avoid the superfluous memory void reserveNode(int n) { nodes.reserve(n); }; ///Using this it is possible to avoid the superfluous memory ///allocation. /// \brief Using this it is possible to avoid the superfluous memory /// allocation. ///Using this it is possible to avoid the superfluous memory public: typedef ExtendedListUGraphBase Parent; /// \brief Add a new node to the graph. /// /// \return the new node. /// Node addNode() { return Parent::addNode(); } /// \brief Add a new edge to the graph. /// /// Add a new edge to the graph with source node \c s /// and target node \c t. /// \return the new undirected edge. UEdge addEdge(const Node& s, const Node& t) { return Parent::addEdge(s, t); } /// \brief Changes the target of \c e to \c n /// /// valid. However InEdge's are invalidated. void changeTarget(UEdge e, Node n) { _changeTarget(e,n); Parent::changeTarget(e,n); } /// Changes the source of \c e to \c n ///valid. However OutEdge's are invalidated. void changeSource(UEdge e, Node n) { _changeSource(e,n); Parent::changeSource(e,n); } /// \brief Contract two nodes.
• ## lemon/min_cost_arborescence.h

 r2042 /// relatively time consuming process to compute the edge cost if /// it is necessary. The default map type is \ref /// concept::StaticGraph::EdgeMap "Graph::EdgeMap".  The value /// concept::Graph::EdgeMap "Graph::EdgeMap".  The value /// of _CostMap is not used directly by MinCostArborescence, /// it is only passed to \ref MinCostArborescenceDefaultTraits.
• ## lemon/min_cut.h

 r2094 /// relatively time consuming process to compute the edge capacity if /// it is necessary. The default map type is \ref /// concept::StaticGraph::EdgeMap "Graph::EdgeMap".  The value /// concept::Graph::EdgeMap "Graph::EdgeMap".  The value /// of CapacityMap is not used directly by search algorithm, it is only /// passed to \ref MaxCardinalitySearchDefaultTraits. typedef _Graph Graph; /// The AuxGraph type which is an ErasableGraph /// The AuxGraph type which is an Graph typedef ListUGraph AuxGraph;
• ## lemon/smart_graph.h

 r2076 ///node and edge deletions. ///It conforms to ///the \ref concept::ExtendableGraph "ExtendableGraph" concept. ///\sa concept::ExtendableGraph. ///the \ref concept::Graph "Graph" concept. ///\sa concept::Graph. /// ///\author Alpar Juttner
• ## lemon/topology.h

 r2082 template bool stronglyConnected(const Graph& graph) { checkConcept(); checkConcept(); typedef typename Graph::Node Node; template int countStronglyConnectedComponents(const Graph& graph) { checkConcept(); checkConcept(); using namespace _topology_bits; template int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { checkConcept(); checkConcept(); typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; template int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { checkConcept(); checkConcept(); typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; using namespace _topology_bits; checkConcept(); checkConcept(); checkConcept, NodeMap>(); using namespace _topology_bits; checkConcept(); checkConcept(); checkConcept, NodeMap>(); bool dag(const Graph& graph) { checkConcept(); checkConcept(); typedef typename Graph::Node Node;
• ## test/bfs_test.cc

 r1956 void check_Bfs_Compile() { typedef concept::StaticGraph Graph; typedef concept::Graph Graph; typedef Graph::Edge Edge; { typedef int VType; typedef concept::StaticGraph Graph; typedef concept::Graph Graph; typedef Graph::Edge Edge;
• ## test/dfs_test.cc

 r1956 void check_Dfs_SmartGraph_Compile() { typedef concept::StaticGraph Graph; typedef concept::Graph Graph; typedef Graph::Edge Edge; { typedef int VType; typedef concept::StaticGraph Graph; typedef concept::Graph Graph; typedef Graph::Edge Edge;
• ## test/dijkstra_test.cc

 r1956 { typedef int VType; typedef concept::StaticGraph Graph; typedef concept::Graph Graph; typedef Graph::Edge Edge; { typedef int VType; typedef concept::StaticGraph Graph; typedef concept::Graph Graph; typedef Graph::Edge Edge;
• ## test/edge_set_test.cc

 r1990 using namespace lemon::concept; typedef SmartGraph Graph; typedef SmartGraph RGraph; int main() { { // checking edge_sets checkConcept >(); checkConcept >(); checkConcept >(); checkConcept >(); checkConcept >(); checkConcept >(); checkConcept >(); checkConcept >(); }

 r1991 { { typedef StaticGraph Graph; checkConcept >(); typedef Graph Graph; checkConcept >(); checkConcept >(); checkConcept >(); checkConcept , Graph::EdgeMap > >(); checkConcept > >(); checkConcept > >(); checkConcept, Graph::EdgeMap > >(); checkConcept > >(); UGraph::UEdgeMap > >(); checkConcept > >(); }
• ## test/graph_factory_test.cc

 r1956 //Compile Graph template void lemon::concept::checkCompileStaticGraph (concept::StaticGraph &); template void lemon::concept::checkCompileGraph (concept::Graph &); template void lemon::concept::checkCompileExtendableGraph (concept::ExtendableGraph &); void lemon::concept::checkCompileGraph (concept::Graph &); template void lemon::concept::checkCompileErasableGraph (concept::ErasableGraph &); void lemon::concept::checkCompileGraph (concept::Graph &); //Compile SmartGraph template void lemon::concept::checkCompileExtendableGraph(SmartGraph &); void lemon::concept::checkCompileGraph(SmartGraph &); template void lemon::concept::checkCompileGraphFindEdge(SmartGraph &); //Compile ListGraph template void lemon::concept::checkCompileExtendableGraph(ListGraph &); void lemon::concept::checkCompileGraph(ListGraph &); template void lemon::concept::checkCompileErasableGraph(ListGraph &); void lemon::concept::checkCompileGraph(ListGraph &); template void lemon::concept::checkCompileGraphFindEdge(ListGraph &); //Compile SymListGraph //template void hugo::checkCompileGraph(SymListGraph &); //template void hugo::checkCompileErasableGraph(SymListGraph &); //template void hugo::checkCompileGraph(SymListGraph &); //template void hugo::checkCompileGraphFindEdge(SymListGraph &); //Compile FullGraph template void lemon::concept::checkCompileStaticGraph(FullGraph &); template void lemon::concept::checkCompileGraph(FullGraph &); template void lemon::concept::checkCompileGraphFindEdge(FullGraph &);
• ## test/graph_test.cc

 r1956 checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept(); } { // checking skeleton graphs checkConcept(); checkConcept(); checkConcept(); checkConcept(); } { // checking list graph checkConcept(); checkConcept(); checkGraph(); } { // checking smart graph checkConcept(); checkConcept(); checkGraph(); } { // checking full graph checkConcept(); checkConcept(); } { // checking full graph checkConcept(); checkConcept(); }
• ## test/kruskal_test.cc

 r1956 void checkCompileKruskal() { concept::WriteMap w; concept::WriteMap w; kruskal(concept::StaticGraph(), concept::ReadMap(), kruskal(concept::Graph(), concept::ReadMap(), w); }
• ## test/preflow_test.cc

 r2108 { typedef int VType; typedef concept::StaticGraph Graph; typedef concept::Graph Graph; typedef Graph::Node Node;
• ## test/ugraph_test.cc

 r1979 void check_concepts() { checkConcept(); checkConcept(); checkConcept(); checkConcept(); checkConcept();
Note: See TracChangeset for help on using the changeset viewer.