1.1 --- a/lemon/static_graph.h	Tue Sep 29 10:39:20 2009 +0200
     1.2 +++ b/lemon/static_graph.h	Tue Sep 29 12:03:02 2009 +0200
     1.3 @@ -197,6 +197,47 @@
     1.4        }
     1.5        node_first_out[node_num] = arc_num;
     1.6      }
     1.7 +    
     1.8 +    template <typename ArcListIterator>
     1.9 +    void build(int n, ArcListIterator first, ArcListIterator last) {
    1.10 +      built = true;
    1.11 +
    1.12 +      node_num = n;
    1.13 +      arc_num = std::distance(first, last);
    1.14 +
    1.15 +      node_first_out = new int[node_num + 1];
    1.16 +      node_first_in = new int[node_num];
    1.17 +
    1.18 +      arc_source = new int[arc_num];
    1.19 +      arc_target = new int[arc_num];
    1.20 +      arc_next_out = new int[arc_num];
    1.21 +      arc_next_in = new int[arc_num];
    1.22 +      
    1.23 +      for (int i = 0; i != node_num; ++i) {
    1.24 +        node_first_in[i] = -1;
    1.25 +      }      
    1.26 +      
    1.27 +      int arc_index = 0;
    1.28 +      for (int i = 0; i != node_num; ++i) {
    1.29 +        node_first_out[i] = arc_index;
    1.30 +        for ( ; first != last && (*first).first == i; ++first) {
    1.31 +          int j = (*first).second;
    1.32 +          LEMON_ASSERT(j >= 0 && j < node_num,
    1.33 +            "Wrong arc list for StaticDigraph::build()");
    1.34 +          arc_source[arc_index] = i;
    1.35 +          arc_target[arc_index] = j;
    1.36 +          arc_next_in[arc_index] = node_first_in[j];
    1.37 +          node_first_in[j] = arc_index;
    1.38 +          arc_next_out[arc_index] = arc_index + 1;
    1.39 +          ++arc_index;
    1.40 +        }
    1.41 +        if (arc_index > node_first_out[i])
    1.42 +          arc_next_out[arc_index - 1] = -1;
    1.43 +      }
    1.44 +      LEMON_ASSERT(first == last,
    1.45 +        "Wrong arc list for StaticDigraph::build()");
    1.46 +      node_first_out[node_num] = arc_num;
    1.47 +    }
    1.48  
    1.49    protected:
    1.50  
    1.51 @@ -328,6 +369,44 @@
    1.52        Parent::build(digraph, nodeRef, arcRef);
    1.53      }
    1.54    
    1.55 +    /// \brief Build the digraph from an arc list.
    1.56 +    ///
    1.57 +    /// This function builds the digraph from the given arc list.
    1.58 +    /// It can be called more than once, but in such case, the whole
    1.59 +    /// structure and all maps will be cleared and rebuilt.
    1.60 +    ///
    1.61 +    /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
    1.62 +    /// specified by STL compatible itartors whose \c value_type must be
    1.63 +    /// <tt>std::pair<int,int></tt>.
    1.64 +    /// Each arc must be specified by a pair of integer indices
    1.65 +    /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
    1.66 +    /// non-decreasing order with respect to their first values.</i>
    1.67 +    /// If the k-th pair in the list is <tt>(i,j)</tt>, then
    1.68 +    /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
    1.69 +    ///
    1.70 +    /// \param n The number of nodes.
    1.71 +    /// \param begin An iterator pointing to the beginning of the arc list.
    1.72 +    /// \param end An iterator pointing to the end of the arc list.
    1.73 +    ///
    1.74 +    /// For example, a simple digraph can be constructed like this.
    1.75 +    /// \code
    1.76 +    ///   std::vector<std::pair<int,int> > arcs;
    1.77 +    ///   arcs.push_back(std::make_pair(0,1));
    1.78 +    ///   arcs.push_back(std::make_pair(0,2));
    1.79 +    ///   arcs.push_back(std::make_pair(1,3));
    1.80 +    ///   arcs.push_back(std::make_pair(1,2));
    1.81 +    ///   arcs.push_back(std::make_pair(3,0));
    1.82 +    ///   StaticDigraph gr;
    1.83 +    ///   gr.build(4, arcs.begin(), arcs.end());
    1.84 +    /// \endcode
    1.85 +    template <typename ArcListIterator>
    1.86 +    void build(int n, ArcListIterator begin, ArcListIterator end) {
    1.87 +      if (built) Parent::clear();
    1.88 +      StaticDigraphBase::build(n, begin, end);
    1.89 +      notifier(Node()).build();
    1.90 +      notifier(Arc()).build();
    1.91 +    }
    1.92 +
    1.93      /// \brief Clear the digraph.
    1.94      ///
    1.95      /// This function erases all nodes and arcs from the digraph.

     2.1 --- a/test/digraph_test.cc	Tue Sep 29 10:39:20 2009 +0200
     2.2 +++ b/test/digraph_test.cc	Tue Sep 29 12:03:02 2009 +0200
     2.3 @@ -441,6 +441,38 @@
     2.4  
     2.5    checkGraphConArcList(G, 4);
     2.6  
     2.7 +  std::vector<std::pair<int,int> > arcs;
     2.8 +  arcs.push_back(std::make_pair(0,1));
     2.9 +  arcs.push_back(std::make_pair(0,2));
    2.10 +  arcs.push_back(std::make_pair(1,3));
    2.11 +  arcs.push_back(std::make_pair(1,2));
    2.12 +  arcs.push_back(std::make_pair(3,0));
    2.13 +  arcs.push_back(std::make_pair(3,3));
    2.14 +  arcs.push_back(std::make_pair(4,2));
    2.15 +  arcs.push_back(std::make_pair(4,3));
    2.16 +  arcs.push_back(std::make_pair(4,1));
    2.17 +
    2.18 +  G.build(6, arcs.begin(), arcs.end());
    2.19 +  
    2.20 +  checkGraphNodeList(G, 6);
    2.21 +  checkGraphArcList(G, 9);
    2.22 +
    2.23 +  checkGraphOutArcList(G, G.node(0), 2);
    2.24 +  checkGraphOutArcList(G, G.node(1), 2);
    2.25 +  checkGraphOutArcList(G, G.node(2), 0);
    2.26 +  checkGraphOutArcList(G, G.node(3), 2);
    2.27 +  checkGraphOutArcList(G, G.node(4), 3);
    2.28 +  checkGraphOutArcList(G, G.node(5), 0);
    2.29 +
    2.30 +  checkGraphInArcList(G, G.node(0), 1);
    2.31 +  checkGraphInArcList(G, G.node(1), 2);
    2.32 +  checkGraphInArcList(G, G.node(2), 3);
    2.33 +  checkGraphInArcList(G, G.node(3), 3);
    2.34 +  checkGraphInArcList(G, G.node(4), 0);
    2.35 +  checkGraphInArcList(G, G.node(5), 0);
    2.36 +
    2.37 +  checkGraphConArcList(G, 9);
    2.38 +
    2.39    checkNodeIds(G);
    2.40    checkArcIds(G);
    2.41    checkGraphNodeMap(G);