RhodeCode

This group contains the skeletons and concept checking classes of

graph structures.

///\brief FullDigraph and FullGraph classes.

  /// \brief A directed full graph class.

  /// FullDigraph is a simple and fast implmenetation of directed full

  /// (complete) graphs. It contains an arc from each node to each node

  /// (including a loop for each node), therefore the number of arcs

  /// is the square of the number of nodes.

  /// This class is completely static and it needs constant memory space.

  /// Thus you can neither add nor delete nodes or arcs, however

  /// the structure can be resized using resize().

  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  /// \note FullDigraph and FullGraph classes are very similar,

  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph

  /// conforms to the \ref concepts::Graph "Graph" concept,

  /// moreover FullGraph does not contain a loop for each

  /// node as this class does.

    /// \brief Default constructor.

    ///

    /// Default constructor. The number of nodes and arcs will be zero.

    /// This function resizes the digraph. It fully destroys and

    /// rebuilds the structure, therefore the maps of the digraph will be

    /// Returns the node with the given index. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// Returns the index of the given node. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// \sa operator()()

    int index(Node node) const { return Parent::index(node); }

    Arc arc(Node u, Node v) const {

  /// FullGraph is a simple and fast implmenetation of undirected full

  /// (complete) graphs. It contains an edge between every distinct pair

  /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.

  /// This class is completely static and it needs constant memory space.

  /// Thus you can neither add nor delete nodes or edges, however

  /// the structure can be resized using resize().

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  /// \note FullDigraph and FullGraph classes are very similar,

  /// but there are two differences. While FullDigraph

  /// moreover this class does not contain a loop for each

  /// node as FullDigraph does.

    /// \brief Default constructor.

    ///

    /// Default constructor. The number of nodes and edges will be zero.

    /// This function resizes the graph. It fully destroys and

    /// rebuilds the structure, therefore the maps of the graph will be

    /// Returns the node with the given index. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// Returns the index of the given node. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// \sa operator()()

    int index(Node node) const { return Parent::index(node); }

    Arc arc(Node s, Node t) const {

    /// \brief Returns the edge connecting the given nodes.

    /// Returns the edge connecting the given nodes.

    Edge edge(Node u, Node v) const {

  /// GridGraph implements a special graph type. The nodes of the

  /// graph can be indexed by two integer values \c (i,j) where \c i is

  /// in the range <tt>[0..width()-1]</tt> and j is in the range

  /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if

  /// the indices differ exactly on one position and the difference is

  /// also exactly one. The nodes of the graph can be obtained by position

  /// using the \c operator()() function and the indices of the nodes can

  /// be obtained using \c pos(), \c col() and \c row() members. The outgoing

  /// This class is completely static and it needs constant memory space.

  /// Thus you can neither add nor delete nodes or edges, however

  /// the structure can be resized using resize().

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

    /// \brief Map to get the indices of the nodes as \ref dim2::Point

    /// "dim2::Point<int>".

    /// Map to get the indices of the nodes as \ref dim2::Point

    /// "dim2::Point<int>".

    /// Construct a grid graph with the given size.

    /// \brief Resizes the graph

    /// This function resizes the graph. It fully destroys and

    /// rebuilds the structure, therefore the maps of the graph will be

    /// reallocated automatically and the previous values will be lost.

    /// \brief The column index of the node.

    /// \brief The row index of the node.

    /// \brief The position of the node.

    /// \brief The number of the columns.

    /// \brief The number of the rows.

    /// \brief The arc goes right from the node.

    /// \brief The arc goes left from the node.

    /// \brief The arc goes up from the node.

    /// \brief The arc goes down from the node.

  /// HypercubeGraph implements a special graph type. The nodes of the

  /// graph are indexed with integers having at most \c dim binary digits.

  /// This class is completely static and it needs constant memory space.

  /// Thus you can neither add nor delete nodes or edges.

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

    /// It is in the range <tt>[0..dim-1]</tt>.

    /// It is in the range <tt>[0..dim-1]</tt>.

///\brief ListDigraph and ListGraph classes.

  ///\ref ListDigraph is a versatile and fast directed graph

  ///implementation based on linked lists that are stored in

  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"

  ///and it also provides several useful additional functionalities.

  ///Most of its member functions and nested classes are documented

  ///\sa ListGraph

    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.

    /// \brief Assignment of a digraph to another one is \e not allowed.

    /// Use DigraphCopy instead.

    ///This function adds a new node to the digraph.

    ///This function adds a new arc to the digraph with source node \c s

    Arc addArc(Node s, Node t) {

    ///This function erases the given node from the digraph.

    void erase(Node n) { Parent::erase(n); }

    ///This function erases the given arc from the digraph.

    void erase(Arc a) { Parent::erase(a); }

    /// This function gives back \c true if the given node is valid,

    /// i.e. it is a real node of the digraph.

    /// \warning A removed node could become valid again if new nodes are

    /// added to the digraph.

    /// This function gives back \c true if the given arc is valid,

    /// i.e. it is a real arc of the digraph.

    /// \warning A removed arc could become valid again if new arcs are

    /// added to the digraph.

    /// Change the target node of an arc

    /// This function changes the target node of the given arc \c a to \c n.

    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed

    ///arc remain valid, however \c InArcIt iterators are invalidated.

    /// Change the source node of an arc

    /// This function changes the source node of the given arc \c a to \c n.

    ///\note \c InArcIt iterators referencing the changed arc remain

    ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.

    /// Reverse the direction of an arc.

    /// This function reverses the direction of the given arc.

    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing

    ///the changed arc are invalidated.

    void reverseArc(Arc a) {

      Node t=target(a);

      changeTarget(a,source(a));

      changeSource(a,t);

    ///This function contracts the given two nodes.

    ///Node \c v is removed, but instead of deleting its

    ///incident arcs, they are joined to node \c u.

    ///If the last parameter \c r is \c true (this is the default value),

    ///then the newly created loops are removed.

    ///\note The moved arcs are joined to node \c u using changeSource()

    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are

    ///invalidated for the outgoing arcs of node \c v and \c InArcIt

    ///iterators are invalidated for the incomming arcs of \c v.

    ///Moreover all iterators referencing node \c v or the removed 

    ///loops are also invalidated. Other iterators remain valid.

    void contract(Node u, Node v, bool r = true)

      for(OutArcIt e(*this,v);e!=INVALID;) {

        if(r && target(e)==u) erase(e);

        else changeSource(e,u);

      for(InArcIt e(*this,v);e!=INVALID;) {

        if(r && source(e)==u) erase(e);

        else changeTarget(e,u);

      erase(v);

    ///This function splits the given node. First, a new node is added

    ///to the digraph, then the source of each outgoing arc of node \c n

    ///is moved to this new node.

    ///If the second parameter \c connect is \c true (this is the default

    ///value), then a new arc from node \c n to the newly created node

    ///is also added.

    ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing

    ///arcs of node \c n are invalidated. Other iterators remain valid.

    ///\warning This functionality cannot be used together with the

    ///This function splits the given arc. First, a new node \c v is

    ///added to the digraph, then the target node of the original arc

    ///is set to \c v. Finally, an arc from \c v to the original target

    ///is added.

    ///\return The newly created node.

    ///\note \c InArcIt iterators referencing the original arc are

    ///invalidated. Other iterators remain valid.

    Node split(Arc a) {

      Node v = addNode();

      addArc(v,target(a));

      changeTarget(a,v);

      return v;

    ///Clear the digraph.

    ///This function erases all nodes and arcs from the digraph.

    ///

    void clear() {

      Parent::clear();

    }

    /// Reserve memory for nodes.

    /// Using this function, it is possible to avoid superfluous memory

    /// allocation: if you know that the digraph you want to build will

    /// be large (e.g. it will contain millions of nodes and/or arcs),

    /// then it is worth reserving space for this amount before starting

    /// to build the digraph.

    /// \sa reserveArc()

    void reserveNode(int n) { nodes.reserve(n); };

    /// Reserve memory for arcs.

    /// Using this function, it is possible to avoid superfluous memory

    /// allocation: if you know that the digraph you want to build will

    /// be large (e.g. it will contain millions of nodes and/or arcs),

    /// then it is worth reserving space for this amount before starting

    /// to build the digraph.

    /// \sa reserveNode()

    void reserveArc(int m) { arcs.reserve(m); };

    /// \note After a state is restored, you cannot restore a later state, 

    /// i.e. you cannot add the removed nodes and arcs again using

    /// another Snapshot instance.

    ///

    /// \warning Node and arc deletions and other modifications (e.g.

    /// reversing, contracting, splitting arcs or nodes) cannot be

    /// However the arcs and nodes that were added to the digraph after

    /// making the current snapshot can be removed without invalidating it.

      /// You have to call save() to actually make a snapshot.

      /// This constructor immediately makes a snapshot of the given digraph.

      Snapshot(ListDigraph &gr)

        attach(gr);

      /// This function makes a snapshot of the given digraph.

      /// It can be called more than once. In case of a repeated

      void save(ListDigraph &gr) {

        attach(gr);

      ///

      /// This function undos the changes until the last snapshot

      /// created by save() or Snapshot(ListDigraph&).

      /// \brief Returns \c true if the snapshot is valid.

      /// This function returns \c true if the snapshot is valid.

  ///\ref ListGraph is a versatile and fast undirected graph

  ///implementation based on linked lists that are stored in

  ///This type fully conforms to the \ref concepts::Graph "Graph concept"

  ///and it also provides several useful additional functionalities.

  ///Most of its member functions and nested classes are documented

  ///\sa ListDigraph

    /// Graphs are \e not copy constructible. Use GraphCopy instead.

    /// \brief Assignment of a graph to another one is \e not allowed.

    /// Use GraphCopy instead.

    /// This function adds a new node to the graph.

    /// This function adds a new edge to the graph between nodes

    /// \c u and \c v with inherent orientation from node \c u to

    /// node \c v.

    Edge addEdge(Node u, Node v) {

      return Parent::addEdge(u, v);

    ///\brief Erase a node from the graph.

    /// This function erases the given node from the graph.

    void erase(Node n) { Parent::erase(n); }

    ///\brief Erase an edge from the graph.

    /// This function erases the given edge from the graph.

    void erase(Edge e) { Parent::erase(e); }

    /// This function gives back \c true if the given node is valid,

    /// i.e. it is a real node of the graph.

    /// \warning A removed node could become valid again if new nodes are

    /// Edge validity check

    /// This function gives back \c true if the given edge is valid,

    /// i.e. it is a real edge of the graph.

    ///

    /// \warning A removed edge could become valid again if new edges are

    /// added to the graph.

    bool valid(Edge e) const { return Parent::valid(e); }

    /// This function gives back \c true if the given arc is valid,

    /// i.e. it is a real arc of the graph.

    /// \warning A removed arc could become valid again if new edges are

    /// \brief Change the first node of an edge.

    /// This function changes the first node of the given edge \c e to \c n.

    ///\note \c EdgeIt and \c ArcIt iterators referencing the

    ///changed edge are invalidated and all other iterators whose

    ///base node is the changed node are also invalidated.

    /// \brief Change the second node of an edge.

    /// This function changes the second node of the given edge \c e to \c n.

    ///\note \c EdgeIt iterators referencing the changed edge remain

    ///valid, however \c ArcIt iterators referencing the changed edge and

    ///all other iterators whose base node is the changed node are also

    ///invalidated.

    /// This function contracts the given two nodes.

    /// Node \c b is removed, but instead of deleting

    /// its incident edges, they are joined to node \c a.

    /// If the last parameter \c r is \c true (this is the default value),

    /// then the newly created loops are removed.

    /// \note The moved edges are joined to node \c a using changeU()

    /// or changeV(), thus all edge and arc iterators whose base node is

    /// \c b are invalidated.

    /// Moreover all iterators referencing node \c b or the removed 

    /// loops are also invalidated. Other iterators remain valid.

    ///Clear the graph.

    ///This function erases all nodes and arcs from the graph.

    ///

    void clear() {

      Parent::clear();

    }

    /// \note After a state is restored, you cannot restore a later state, 

    /// i.e. you cannot add the removed nodes and edges again using

    /// another Snapshot instance.

    ///

    /// \warning Node and edge deletions and other modifications

    /// (e.g. changing the end-nodes of edges or contracting nodes)

    /// cannot be restored. These events invalidate the snapshot.

    /// However the edges and nodes that were added to the graph after

    /// making the current snapshot can be removed without invalidating it.

      /// You have to call save() to actually make a snapshot.

      /// This constructor immediately makes a snapshot of the given graph.

      Snapshot(ListGraph &gr)

        attach(gr);

      /// This function makes a snapshot of the given graph.

      /// It can be called more than once. In case of a repeated

      void save(ListGraph &gr) {

        attach(gr);

      ///

      /// This function undos the changes until the last snapshot

      /// created by save() or Snapshot(ListGraph&).

      /// \brief Returns \c true if the snapshot is valid.

      /// This function returns \c true if the snapshot is valid.

  ///\ref SmartDigraph is a simple and fast digraph implementation.

  ///It is also quite memory efficient but at the price

  ///that it does not support node and arc deletion 

  ///(except for the Snapshot feature).

  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"

  ///and it also provides some additional functionalities.

  ///Most of its member functions and nested classes are documented

  ///only in the concept class.

  ///

  ///\sa concepts::Digraph

  ///\sa SmartGraph

    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.

    /// \brief Assignment of a digraph to another one is \e not allowed.

    /// Use DigraphCopy instead.

    ///This function adds a new node to the digraph.

    ///\return The new node.

    ///This function adds a new arc to the digraph with source node \c s

    Arc addArc(Node s, Node t) {