Changeset 2539:c25f62a6452d in lemon0.x for lemon/graph_utils.h
 Timestamp:
 12/11/07 18:37:08 (12 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3416
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r2534 r2539 383 383 ///\sa EdgeLookUp 384 384 ///\sa AllEdgeLookUp 385 ///\sa DynEdgeLookUp 385 386 ///\sa ConEdgeIt 386 387 template <typename Graph> … … 405 406 ///\sa EdgeLookUp 406 407 ///\sa AllEdgeLookUp 408 ///\sa DynEdgeLookUp 407 409 /// 408 410 /// \author Balazs Dezso … … 2297 2299 } 2298 2300 } 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 } 2299 2310 }; 2300 2311 … … 2409 2420 } 2410 2421 } 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 } 2411 2430 }; 2412 2431 … … 2471 2490 2472 2491 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 outdegree 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 selfadjusting 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,m1); 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 2473 2937 ///Fast edge look up between given endpoints. 2474 2938 … … 2488 2952 ///\param G The type of the underlying graph. 2489 2953 /// 2954 ///\sa DynEdgeLookUp 2490 2955 ///\sa AllEdgeLookUp 2491 2956 template<class G> … … 2523 2988 2524 2989 private: 2525 Edge refresh _rec(std::vector<Edge> &v,int a,int b)2990 Edge refreshRec(std::vector<Edge> &v,int a,int b) 2526 2991 { 2527 2992 int m=(a+b)/2; 2528 2993 Edge me=v[m]; 2529 _left[me] = a<m?refresh _rec(v,a,m1):INVALID;2530 _right[me] = m<b?refresh _rec(v,m+1,b):INVALID;2994 _left[me] = a<m?refreshRec(v,a,m1):INVALID; 2995 _right[me] = m<b?refreshRec(v,m+1,b):INVALID; 2531 2996 return me; 2532 2997 } … … 2544 3009 if(v.size()) { 2545 3010 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); 2547 3012 } 2548 3013 else _head[n]=INVALID; … … 2600 3065 ///\param G The type of the underlying graph. 2601 3066 /// 3067 ///\sa DynEdgeLookUp 2602 3068 ///\sa EdgeLookUp 2603 3069 template<class G>
Note: See TracChangeset
for help on using the changeset viewer.