COIN-OR::LEMON - Graph Library

Changeset 2539:c25f62a6452d in lemon-0.x for lemon


Ignore:
Timestamp:
12/11/07 18:37:08 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3416
Message:

DynEdgeLookUp? implementation based on splay trees
In general case it is slower than the static version, but it should not
refreshed on the change of the graph

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r2534 r2539  
    383383  ///\sa EdgeLookUp
    384384  ///\sa AllEdgeLookUp
     385  ///\sa DynEdgeLookUp
    385386  ///\sa ConEdgeIt
    386387  template <typename Graph>
     
    405406  ///\sa EdgeLookUp
    406407  ///\sa AllEdgeLookUp
     408  ///\sa DynEdgeLookUp
    407409  ///
    408410  /// \author Balazs Dezso
     
    22972299        }
    22982300      }
     2301
     2302      virtual void build() {
     2303        Parent::build();
     2304        Key it;
     2305        typename Parent::Notifier* nf = Parent::notifier();
     2306        for (nf->first(it); it != INVALID; nf->next(it)) {
     2307          Parent::set(it, 0);
     2308        }
     2309      }
    22992310    };
    23002311
     
    24092420        }
    24102421      }
     2422      virtual void build() {
     2423        Parent::build();
     2424        Key it;
     2425        typename Parent::Notifier* nf = Parent::notifier();
     2426        for (nf->first(it); it != INVALID; nf->next(it)) {
     2427          Parent::set(it, 0);
     2428        }
     2429      }
    24112430    };
    24122431
     
    24712490
    24722491
     2492  ///Dynamic edge look up between given endpoints.
     2493 
     2494  ///\ingroup gutils
     2495  ///Using this class, you can find an edge in a graph from a given
     2496  ///source to a given target in amortized time <em>O(log d)</em>,
     2497  ///where <em>d</em> is the out-degree of the source node.
     2498  ///
     2499  ///It is possible to find \e all parallel edges between two nodes with
     2500  ///the \c findFirst() and \c findNext() members.
     2501  ///
     2502  ///See the \ref EdgeLookUp and \ref AllEdgeLookUp classes if your
     2503  ///graph do not changed so frequently.
     2504  ///
     2505  ///This class uses a self-adjusting binary search tree, Sleator's
     2506  ///and Tarjan's Splay tree for guarantee the logarithmic amortized
     2507  ///time bound for edge lookups. This class also guarantees the
     2508  ///optimal time bound in a constant factor for any distribution of
     2509  ///queries.
     2510  ///
     2511  ///\param G The type of the underlying graph. 
     2512  ///
     2513  ///\sa EdgeLookUp 
     2514  ///\sa AllEdgeLookUp 
     2515  template<class G>
     2516  class DynEdgeLookUp
     2517    : protected ItemSetTraits<G, typename G::Edge>::ItemNotifier::ObserverBase
     2518  {
     2519  public:
     2520    typedef typename ItemSetTraits<G, typename G::Edge>
     2521    ::ItemNotifier::ObserverBase Parent;
     2522
     2523    GRAPH_TYPEDEFS(typename G);
     2524    typedef G Graph;
     2525
     2526  protected:
     2527
     2528    class AutoNodeMap : public DefaultMap<Graph, Node, Edge> {
     2529    public:
     2530
     2531      typedef DefaultMap<Graph, Node, Edge> Parent;
     2532
     2533      AutoNodeMap(const Graph& graph) : Parent(graph, INVALID) {}
     2534     
     2535      virtual void add(const Node& node) {
     2536        Parent::add(node);
     2537        Parent::set(node, INVALID);
     2538      }
     2539
     2540      virtual void add(const std::vector<Node>& nodes) {
     2541        Parent::add(nodes);
     2542        for (int i = 0; i < int(nodes.size()); ++i) {
     2543          Parent::set(nodes[i], INVALID);
     2544        }
     2545      }
     2546
     2547      virtual void build() {
     2548        Parent::build();
     2549        Node it;
     2550        typename Parent::Notifier* nf = Parent::notifier();
     2551        for (nf->first(it); it != INVALID; nf->next(it)) {
     2552          Parent::set(it, INVALID);
     2553        }
     2554      }
     2555    };
     2556
     2557    const Graph &_g;
     2558    AutoNodeMap _head;
     2559    typename Graph::template EdgeMap<Edge> _parent;
     2560    typename Graph::template EdgeMap<Edge> _left;
     2561    typename Graph::template EdgeMap<Edge> _right;
     2562   
     2563    class EdgeLess {
     2564      const Graph &g;
     2565    public:
     2566      EdgeLess(const Graph &_g) : g(_g) {}
     2567      bool operator()(Edge a,Edge b) const
     2568      {
     2569        return g.target(a)<g.target(b);
     2570      }
     2571    };
     2572   
     2573  public:
     2574   
     2575    ///Constructor
     2576
     2577    ///Constructor.
     2578    ///
     2579    ///It builds up the search database.
     2580    DynEdgeLookUp(const Graph &g)
     2581      : _g(g),_head(g),_parent(g),_left(g),_right(g)
     2582    {
     2583      Parent::attach(_g.notifier(typename Graph::Edge()));
     2584      refresh();
     2585    }
     2586   
     2587  protected:
     2588
     2589    virtual void add(const Edge& edge) {
     2590      insert(edge);
     2591    }
     2592
     2593    virtual void add(const std::vector<Edge>& edges) {
     2594      for (int i = 0; i < int(edges.size()); ++i) {
     2595        insert(edges[i]);
     2596      }
     2597    }
     2598
     2599    virtual void erase(const Edge& edge) {
     2600      remove(edge);
     2601    }
     2602
     2603    virtual void erase(const std::vector<Edge>& edges) {
     2604      for (int i = 0; i < int(edges.size()); ++i) {
     2605        remove(edges[i]);
     2606      }     
     2607    }
     2608
     2609    virtual void build() {
     2610      refresh();
     2611    }
     2612
     2613    virtual void clear() {
     2614      for(NodeIt n(_g);n!=INVALID;++n) {
     2615        _head.set(n, INVALID);
     2616      }
     2617    }
     2618
     2619    void insert(Edge edge) {
     2620      Node s = _g.source(edge);
     2621      Node t = _g.target(edge);
     2622      _left.set(edge, INVALID);
     2623      _right.set(edge, INVALID);
     2624     
     2625      Edge e = _head[s];
     2626      if (e == INVALID) {
     2627        _head.set(s, edge);
     2628        _parent.set(edge, INVALID);
     2629        return;
     2630      }
     2631      while (true) {
     2632        if (t < _g.target(e)) {
     2633          if (_left[e] == INVALID) {
     2634            _left.set(e, edge);
     2635            _parent.set(edge, e);
     2636            splay(edge);
     2637            return;
     2638          } else {
     2639            e = _left[e];
     2640          }
     2641        } else {
     2642          if (_right[e] == INVALID) {
     2643            _right.set(e, edge);
     2644            _parent.set(edge, e);
     2645            splay(edge);
     2646            return;
     2647          } else {
     2648            e = _right[e];
     2649          }
     2650        }
     2651      }
     2652    }
     2653
     2654    void remove(Edge edge) {
     2655      if (_left[edge] == INVALID) {
     2656        if (_right[edge] != INVALID) {
     2657          _parent.set(_right[edge], _parent[edge]);
     2658        }
     2659        if (_parent[edge] != INVALID) {
     2660          if (_left[_parent[edge]] == edge) {
     2661            _left.set(_parent[edge], _right[edge]);
     2662          } else {
     2663            _right.set(_parent[edge], _right[edge]);
     2664          }
     2665        } else {
     2666          _head.set(_g.source(edge), _right[edge]);
     2667        }
     2668      } else if (_right[edge] == INVALID) {
     2669        _parent.set(_left[edge], _parent[edge]);
     2670        if (_parent[edge] != INVALID) {
     2671          if (_left[_parent[edge]] == edge) {
     2672            _left.set(_parent[edge], _left[edge]);
     2673          } else {
     2674            _right.set(_parent[edge], _left[edge]);
     2675          }
     2676        } else {
     2677          _head.set(_g.source(edge), _left[edge]);
     2678        }
     2679      } else {
     2680        Edge e = _left[edge];
     2681        if (_right[e] != INVALID) {
     2682          e = _right[e];         
     2683          while (_right[e] != INVALID) {
     2684            e = _right[e];
     2685          }
     2686          Edge s = _parent[e];
     2687          _right.set(_parent[e], _left[e]);
     2688          if (_left[e] != INVALID) {
     2689            _parent.set(_left[e], _parent[e]);
     2690          }
     2691         
     2692          _left.set(e, _left[edge]);
     2693          _parent.set(_left[edge], e);
     2694          _right.set(e, _right[edge]);
     2695          _parent.set(_right[edge], e);
     2696
     2697          _parent.set(e, _parent[edge]);
     2698          if (_parent[edge] != INVALID) {
     2699            if (_left[_parent[edge]] == edge) {
     2700              _left.set(_parent[edge], e);
     2701            } else {
     2702              _right.set(_parent[edge], e);
     2703            }
     2704          }
     2705          splay(s);
     2706        } else {
     2707          _right.set(e, _right[edge]);
     2708          _parent.set(_right[edge], e);
     2709
     2710          if (_parent[edge] != INVALID) {
     2711            if (_left[_parent[edge]] == edge) {
     2712              _left.set(_parent[edge], e);
     2713            } else {
     2714              _right.set(_parent[edge], e);
     2715            }
     2716          } else {
     2717            _head.set(_g.source(edge), e);
     2718          }
     2719        }
     2720      }
     2721    }
     2722
     2723    Edge refreshRec(std::vector<Edge> &v,int a,int b)
     2724    {
     2725      int m=(a+b)/2;
     2726      Edge me=v[m];
     2727      if (a < m) {
     2728        Edge left = refreshRec(v,a,m-1);
     2729        _left.set(me, left);
     2730        _parent.set(left, me);
     2731      } else {
     2732        _left.set(me, INVALID);
     2733      }
     2734      if (m < b) {
     2735        Edge right = refreshRec(v,m+1,b);
     2736        _right.set(me, right);
     2737        _parent.set(right, me);
     2738      } else {
     2739        _right.set(me, INVALID);
     2740      }
     2741      return me;
     2742    }
     2743
     2744    void refresh() {
     2745      for(NodeIt n(_g);n!=INVALID;++n) {
     2746        std::vector<Edge> v;
     2747        for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
     2748        if(v.size()) {
     2749          std::sort(v.begin(),v.end(),EdgeLess(_g));
     2750          Edge head = refreshRec(v,0,v.size()-1);
     2751          _head.set(n, head);
     2752          _parent.set(head, INVALID);
     2753        }
     2754        else _head.set(n, INVALID);
     2755      }
     2756    }
     2757
     2758    void zig(Edge v) {       
     2759      Edge w = _parent[v];
     2760      _parent.set(v, _parent[w]);
     2761      _parent.set(w, v);
     2762      _left.set(w, _right[v]);
     2763      _right.set(v, w);
     2764      if (_parent[v] != INVALID) {
     2765        if (_right[_parent[v]] == w) {
     2766          _right.set(_parent[v], v);
     2767        } else {
     2768          _left.set(_parent[v], v);
     2769        }
     2770      }
     2771      if (_left[w] != INVALID){
     2772        _parent.set(_left[w], w);
     2773      }
     2774    }
     2775
     2776    void zag(Edge v) {       
     2777      Edge w = _parent[v];
     2778      _parent.set(v, _parent[w]);
     2779      _parent.set(w, v);
     2780      _right.set(w, _left[v]);
     2781      _left.set(v, w);
     2782      if (_parent[v] != INVALID){
     2783        if (_left[_parent[v]] == w) {
     2784          _left.set(_parent[v], v);
     2785        } else {
     2786          _right.set(_parent[v], v);
     2787        }
     2788      }
     2789      if (_right[w] != INVALID){
     2790        _parent.set(_right[w], w);
     2791      }
     2792    }
     2793
     2794    void splay(Edge v) {
     2795      while (_parent[v] != INVALID) {
     2796        if (v == _left[_parent[v]]) {
     2797          if (_parent[_parent[v]] == INVALID) {
     2798            zig(v);
     2799          } else {
     2800            if (_parent[v] == _left[_parent[_parent[v]]]) {
     2801              zig(_parent[v]);
     2802              zig(v);
     2803            } else {
     2804              zig(v);
     2805              zag(v);
     2806            }
     2807          }
     2808        } else {
     2809          if (_parent[_parent[v]] == INVALID) {
     2810            zag(v);
     2811          } else {
     2812            if (_parent[v] == _left[_parent[_parent[v]]]) {
     2813              zag(v);
     2814              zig(v);
     2815            } else {
     2816              zag(_parent[v]);
     2817              zag(v);
     2818            }
     2819          }
     2820        }
     2821      }
     2822      _head[_g.source(v)] = v;
     2823    }
     2824
     2825
     2826  public:
     2827   
     2828    ///Find an edge between two nodes.
     2829   
     2830    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
     2831    /// <em>d</em> is the number of outgoing edges of \c s.
     2832    ///\param s The source node
     2833    ///\param t The target node
     2834    ///\return An edge from \c s to \c t if there exists,
     2835    ///\ref INVALID otherwise.
     2836    Edge operator()(Node s, Node t) const
     2837    {
     2838      Edge e = _head[s];
     2839      while (true) {
     2840        if (_g.target(e) == t) {
     2841          const_cast<DynEdgeLookUp&>(*this).splay(e);
     2842          return e;
     2843        } else if (t < _g.target(e)) {
     2844          if (_left[e] == INVALID) {
     2845            const_cast<DynEdgeLookUp&>(*this).splay(e);
     2846            return INVALID;
     2847          } else {
     2848            e = _left[e];
     2849          }
     2850        } else  {
     2851          if (_right[e] == INVALID) {
     2852            const_cast<DynEdgeLookUp&>(*this).splay(e);
     2853            return INVALID;
     2854          } else {
     2855            e = _right[e];
     2856          }
     2857        }
     2858      }
     2859    }
     2860
     2861    ///Find the first edge between two nodes.
     2862   
     2863    ///Find the first edge between two nodes in time
     2864    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
     2865    /// outgoing edges of \c s. 
     2866    ///\param s The source node
     2867    ///\param t The target node
     2868    ///\return An edge from \c s to \c t if there exists, \ref INVALID
     2869    /// otherwise.
     2870    Edge findFirst(Node s, Node t) const
     2871    {
     2872      Edge e = _head[s];
     2873      Edge r = INVALID;
     2874      while (true) {
     2875        if (_g.target(e) < t) {
     2876          if (_right[e] == INVALID) {
     2877            const_cast<DynEdgeLookUp&>(*this).splay(e);
     2878            return r;
     2879          } else {
     2880            e = _right[e];
     2881          }
     2882        } else {
     2883          if (_g.target(e) == t) {
     2884            r = e;
     2885          }
     2886          if (_left[e] == INVALID) {
     2887            const_cast<DynEdgeLookUp&>(*this).splay(e);
     2888            return r;
     2889          } else {
     2890            e = _left[e];
     2891          }
     2892        }
     2893      }
     2894    }
     2895
     2896    ///Find the next edge between two nodes.
     2897   
     2898    ///Find the next edge between two nodes in time
     2899    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
     2900    /// outgoing edges of \c s. 
     2901    ///\param s The source node
     2902    ///\param t The target node
     2903    ///\return An edge from \c s to \c t if there exists, \ref INVALID
     2904    /// otherwise.
     2905
     2906    ///\note If \c e is not the result of the previous \c findFirst()
     2907    ///operation then the amorized time bound can not be guaranteed.
     2908#ifdef DOXYGEN
     2909    Edge findNext(Node s, Node t, Edge e) const
     2910#else
     2911    Edge findNext(Node, Node t, Edge e) const
     2912#endif
     2913    {
     2914      if (_right[e] != INVALID) {
     2915        e = _right[e];
     2916        while (_left[e] != INVALID) {
     2917          e = _left[e];
     2918        }
     2919        const_cast<DynEdgeLookUp&>(*this).splay(e);
     2920      } else {
     2921        while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
     2922          e = _parent[e];
     2923        }
     2924        if (_parent[e] == INVALID) {
     2925          return INVALID;
     2926        } else {
     2927          e = _parent[e];
     2928          const_cast<DynEdgeLookUp&>(*this).splay(e);
     2929        }
     2930      }
     2931      if (_g.target(e) == t) return e;
     2932      else return INVALID;   
     2933    }
     2934
     2935  };
     2936
    24732937  ///Fast edge look up between given endpoints.
    24742938 
     
    24882952  ///\param G The type of the underlying graph.
    24892953  ///
     2954  ///\sa DynEdgeLookUp
    24902955  ///\sa AllEdgeLookUp 
    24912956  template<class G>
     
    25232988   
    25242989  private:
    2525     Edge refresh_rec(std::vector<Edge> &v,int a,int b)
     2990    Edge refreshRec(std::vector<Edge> &v,int a,int b)
    25262991    {
    25272992      int m=(a+b)/2;
    25282993      Edge me=v[m];
    2529       _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
    2530       _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
     2994      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
     2995      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
    25312996      return me;
    25322997    }
     
    25443009      if(v.size()) {
    25453010        std::sort(v.begin(),v.end(),EdgeLess(_g));
    2546         _head[n]=refresh_rec(v,0,v.size()-1);
     3011        _head[n]=refreshRec(v,0,v.size()-1);
    25473012      }
    25483013      else _head[n]=INVALID;
     
    26003065  ///\param G The type of the underlying graph.
    26013066  ///
     3067  ///\sa DynEdgeLookUp
    26023068  ///\sa EdgeLookUp 
    26033069  template<class G>
Note: See TracChangeset for help on using the changeset viewer.