COIN-OR::LEMON - Graph Library

Changeset 824:5764dd9b6e18 in lemon


Ignore:
Timestamp:
09/29/09 12:03:02 (14 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add a new build() function to StaticDigraph? (#68)

This function builds the digraph from an arc list that
contains pairs of integer indices from the range [0..n-1].
It is useful in the cases when you would like to build a
StaticDigraph? from scratch, i.e. you do not want to build
another digraph that can be copied using the other build()
function.

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/static_graph.h

    r823 r824  
    196196        }
    197197      }
     198      node_first_out[node_num] = arc_num;
     199    }
     200   
     201    template <typename ArcListIterator>
     202    void build(int n, ArcListIterator first, ArcListIterator last) {
     203      built = true;
     204
     205      node_num = n;
     206      arc_num = std::distance(first, last);
     207
     208      node_first_out = new int[node_num + 1];
     209      node_first_in = new int[node_num];
     210
     211      arc_source = new int[arc_num];
     212      arc_target = new int[arc_num];
     213      arc_next_out = new int[arc_num];
     214      arc_next_in = new int[arc_num];
     215     
     216      for (int i = 0; i != node_num; ++i) {
     217        node_first_in[i] = -1;
     218      }     
     219     
     220      int arc_index = 0;
     221      for (int i = 0; i != node_num; ++i) {
     222        node_first_out[i] = arc_index;
     223        for ( ; first != last && (*first).first == i; ++first) {
     224          int j = (*first).second;
     225          LEMON_ASSERT(j >= 0 && j < node_num,
     226            "Wrong arc list for StaticDigraph::build()");
     227          arc_source[arc_index] = i;
     228          arc_target[arc_index] = j;
     229          arc_next_in[arc_index] = node_first_in[j];
     230          node_first_in[j] = arc_index;
     231          arc_next_out[arc_index] = arc_index + 1;
     232          ++arc_index;
     233        }
     234        if (arc_index > node_first_out[i])
     235          arc_next_out[arc_index - 1] = -1;
     236      }
     237      LEMON_ASSERT(first == last,
     238        "Wrong arc list for StaticDigraph::build()");
    198239      node_first_out[node_num] = arc_num;
    199240    }
     
    329370    }
    330371 
     372    /// \brief Build the digraph from an arc list.
     373    ///
     374    /// This function builds the digraph from the given arc list.
     375    /// It can be called more than once, but in such case, the whole
     376    /// structure and all maps will be cleared and rebuilt.
     377    ///
     378    /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
     379    /// specified by STL compatible itartors whose \c value_type must be
     380    /// <tt>std::pair<int,int></tt>.
     381    /// Each arc must be specified by a pair of integer indices
     382    /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
     383    /// non-decreasing order with respect to their first values.</i>
     384    /// If the k-th pair in the list is <tt>(i,j)</tt>, then
     385    /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
     386    ///
     387    /// \param n The number of nodes.
     388    /// \param begin An iterator pointing to the beginning of the arc list.
     389    /// \param end An iterator pointing to the end of the arc list.
     390    ///
     391    /// For example, a simple digraph can be constructed like this.
     392    /// \code
     393    ///   std::vector<std::pair<int,int> > arcs;
     394    ///   arcs.push_back(std::make_pair(0,1));
     395    ///   arcs.push_back(std::make_pair(0,2));
     396    ///   arcs.push_back(std::make_pair(1,3));
     397    ///   arcs.push_back(std::make_pair(1,2));
     398    ///   arcs.push_back(std::make_pair(3,0));
     399    ///   StaticDigraph gr;
     400    ///   gr.build(4, arcs.begin(), arcs.end());
     401    /// \endcode
     402    template <typename ArcListIterator>
     403    void build(int n, ArcListIterator begin, ArcListIterator end) {
     404      if (built) Parent::clear();
     405      StaticDigraphBase::build(n, begin, end);
     406      notifier(Node()).build();
     407      notifier(Arc()).build();
     408    }
     409
    331410    /// \brief Clear the digraph.
    332411    ///
  • test/digraph_test.cc

    r823 r824  
    442442  checkGraphConArcList(G, 4);
    443443
     444  std::vector<std::pair<int,int> > arcs;
     445  arcs.push_back(std::make_pair(0,1));
     446  arcs.push_back(std::make_pair(0,2));
     447  arcs.push_back(std::make_pair(1,3));
     448  arcs.push_back(std::make_pair(1,2));
     449  arcs.push_back(std::make_pair(3,0));
     450  arcs.push_back(std::make_pair(3,3));
     451  arcs.push_back(std::make_pair(4,2));
     452  arcs.push_back(std::make_pair(4,3));
     453  arcs.push_back(std::make_pair(4,1));
     454
     455  G.build(6, arcs.begin(), arcs.end());
     456 
     457  checkGraphNodeList(G, 6);
     458  checkGraphArcList(G, 9);
     459
     460  checkGraphOutArcList(G, G.node(0), 2);
     461  checkGraphOutArcList(G, G.node(1), 2);
     462  checkGraphOutArcList(G, G.node(2), 0);
     463  checkGraphOutArcList(G, G.node(3), 2);
     464  checkGraphOutArcList(G, G.node(4), 3);
     465  checkGraphOutArcList(G, G.node(5), 0);
     466
     467  checkGraphInArcList(G, G.node(0), 1);
     468  checkGraphInArcList(G, G.node(1), 2);
     469  checkGraphInArcList(G, G.node(2), 3);
     470  checkGraphInArcList(G, G.node(3), 3);
     471  checkGraphInArcList(G, G.node(4), 0);
     472  checkGraphInArcList(G, G.node(5), 0);
     473
     474  checkGraphConArcList(G, 9);
     475
    444476  checkNodeIds(G);
    445477  checkArcIds(G);
Note: See TracChangeset for help on using the changeset viewer.