Changeset ba56eb

Timestamp:

02/06/09 00:18:33 (4 years ago)

Author:

Tiago de Paula Peixoto <tiago@…>

Branches:

master, python3

Children:

0c87c4

Parents:

d6422b

git-author:

Tiago de Paula Peixoto <tiago@…> (02/01/09 14:35:18)

git-committer:

Tiago de Paula Peixoto <tiago@…> (02/06/09 00:18:33)

Message:

Fix edge index housekeeping

Location:

src/graph

Files:

• graph.cc (modified) (1 diff)
• graph.hh (modified) (3 diffs)
• graph_filtering.cc (modified) (5 diffs)
• graph_python_interface.cc (modified) (4 diffs)

src/graph/graph.cc

@@ -41 +41 @@
      _vertex_index(get(vertex_index,_mg)),
      _edge_index(get(edge_index_t(),_mg)),
+     _max_edge_index(0),
+     _nedges(0),
      _graph_index(0),
      _vertex_filter_map(_vertex_index),

src/graph/graph.hh

@@ -18 +18 @@
 #ifndef GRAPH_HH
 #define GRAPH_HH
+
+#include <deque>
 
 #include <boost/graph/graph_traits.hpp>
@@ -154 +156 @@
     graph_index_map_t  GetGraphIndex()  {return graph_index_map_t(0);}
 
+    void           AddEdgeIndex(const edge_t& e);
+    void           RemoveEdgeIndex(const edge_t& e);
+
 private:
     // Gets the encapsulated graph view. See graph_filtering.cc for details
@@ -192 +197 @@
     // edge index map
     edge_index_map_t _edge_index;
-    vector<size_t> _free_indexes; // indexes of deleted edges to be used up for
-                                  // new edges to avoid needless fragmentation
-    size_t _max_edge_index; // needed for property map bounds
+    deque<size_t> _free_indexes; // indexes of deleted edges to be used up for
+                                 // new edges to avoid very large indexes, and
+                                 // property map memory usage
+    size_t _max_edge_index;
 
     // graph index map

src/graph/graph_filtering.cc

@@ -132 +132 @@
 {
 #ifndef NO_GRAPH_FILTERING
-    edge_filter.reserve(max_eindex);
-    vertex_filter.reserve(num_vertices(g));
     MaskFilter<EdgeFilter> e_filter(edge_filter, e_invert);
     MaskFilter<VertexFilter> v_filter(vertex_filter, v_invert);
@@ -139 +137 @@
     if (e_active)
     {
+        if (max_eindex > 0)
+            edge_filter.reserve(max_eindex+1);
         if (v_active)
         {
+            if (num_vertices(g) > 0)
+                vertex_filter.reserve(num_vertices(g));
             typedef filtered_graph<Graph, MaskFilter<EdgeFilter>,
                                    MaskFilter<VertexFilter> > fg_t;
@@ -163 +165 @@
         if (v_active)
         {
+            if (num_vertices(g) > 0)
+                vertex_filter.reserve(num_vertices(g));
             typedef filtered_graph<Graph, keep_all,
                                    MaskFilter<VertexFilter> > fg_t;
@@ -212 +216 @@
         for (tie(e, e_end) = out_edges(*v, _mg); e != e_end; ++e)
             _edge_index[*e] = index++;
+    _max_edge_index =  (index > 0) ? index - 1 : 0;
+    _nedges = index;
+    _free_indexes.clear();
 }
 
@@ -232 +239 @@
         for (typeof(deleted_edges.begin()) iter = deleted_edges.begin();
              iter != deleted_edges.end(); ++iter)
-            remove_edge(*iter, _mg);
+            RemoveEdgeIndex(*iter);
         deleted_edges.clear();
     }
-    ReIndexEdges();
 }
 

src/graph/graph_python_interface.cc

@@ -161 +161 @@
 {
     template <class Graph, class EdgeIndexMap>
-    void operator()(Graph* gp, const GraphInterface& gi, const PythonVertex& s,
+    void operator()(Graph* gp, GraphInterface& gi, const PythonVertex& s,
                     const PythonVertex& t, EdgeIndexMap edge_index,
-                    size_t new_index, python::object& new_e) const
+                    python::object& new_e) const
     {
         Graph& g = *gp;
@@ -169 +169 @@
             add_edge(s.GetDescriptor(), t.GetDescriptor(), g).first;
         new_e = python::object(PythonEdge<Graph>(gi, e));
-        edge_index[e] = new_index;
-    }
-};
+        gi.AddEdgeIndex(e);
+    }
+};
+
+void GraphInterface::AddEdgeIndex(const edge_t& e)
+{
+    if (!_free_indexes.empty())
+    {
+        _edge_index[e] = _free_indexes.front();
+        _free_indexes.pop_front();
+    }
+    else
+    {
+        _edge_index[e] = _nedges;
+        _max_edge_index = _nedges;
+    }
+    _nedges++;
+}
 
 python::object GraphInterface::AddEdge(const python::object& s,
@@ -180 +195 @@
     src.CheckValid();
     tgt.CheckValid();
-    size_t new_index;
-    if (_free_indexes.empty())
-    {
-        new_index = num_edges(_mg);
-    }
-    else
-    {
-        new_index = _free_indexes.back();
-        _free_indexes.pop_back();
-    }
     python::object new_e;
     run_action<>()(*this, lambda::bind<void>(add_new_edge(), lambda::_1,
                                              lambda::var(*this), src, tgt,
-                                             _edge_index, new_index,
+                                             _edge_index,
                                              lambda::var(new_e)))();
-    _nedges++;
-    _max_edge_index = max(_max_edge_index, new_index);
     return new_e;
 }
@@ -226 +229 @@
     if (!found)
         throw GraphException("invalid edge descriptor");
-    if (_edge_index[de] != _nedges - 1)
-        _free_indexes.push_back(_edge_index[de]);
+    RemoveEdgeIndex(de);
+}
+
+void GraphInterface::RemoveEdgeIndex(const edge_t& e)
+{
+    size_t index = _edge_index[e];
+    if (index == _max_edge_index)
+    {
+        if (_max_edge_index - 1 == _free_indexes.back())
+        {
+            if (_max_edge_index > 0)
+                _max_edge_index--;
+            while (_max_edge_index == _free_indexes.back())
+            {
+                _free_indexes.pop_back();
+                if (_max_edge_index > 0)
+                    _max_edge_index--;
+            }
+        }
+        else
+        {
+            if (_max_edge_index > 0)
+                _max_edge_index--;
+        }
+    }
     else
-        _max_edge_index = (_nedges > 1) ? _nedges - 2 : 0;
-    remove_edge(de, _mg);
+    {
+        typeof(_free_indexes.begin()) pos =
+                lower_bound(_free_indexes.begin(), _free_indexes.end(), index);
+        _free_indexes.insert(pos, index);
+    }
     _nedges--;
+    remove_edge(e, _mg);
 }