Changeset 368:0beed7a49063 in lemon0.x
 Timestamp:
 04/21/04 22:48:00 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@496
 Location:
 src/work
 Files:

 1 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/list_graph.h
r354 r368 540 540 541 541 class UndirListGraph : public ListGraph { 542 public: 542 543 typedef SymEdgeIt OutEdgeIt; 543 544 typedef SymEdgeIt InEdgeIt; 
src/work/marci/graph_wrapper.h
r363 r368 4 4 5 5 #include <invalid.h> 6 #include <iter_map.h> 6 7 7 8 namespace hugo { … … 863 864 this>next(f); 864 865 first_out_edges>set(this>tail(e), f.e); 866 } 867 }; 868 869 /// A wrapper for composing a bipartite graph. 870 /// \c _graph have to be a reference to an undirected graph \c Graph 871 /// and 872 /// \c _s_false_t_true_map is an \c IterableBoolMap 873 /// reference containing the elements for the 874 /// color classes S and T. 875 /// It results in a directed graph such that the edges are oriented from 876 /// S to T. 877 template<typename Graph> 878 class BipartiteGraphWrapper : public GraphWrapper<Graph> { 879 typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap; 880 SFalseTTrueMap* s_false_t_true_map; 881 882 public: 883 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 884 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) { 885 } 886 typedef typename GraphWrapper<Graph>::Node Node; 887 //using GraphWrapper<Graph>::NodeIt; 888 typedef typename GraphWrapper<Graph>::Edge Edge; 889 //using GraphWrapper<Graph>::EdgeIt; 890 class SNodeIt { 891 Node n; 892 public: 893 SNodeIt() { } 894 SNodeIt(const Invalid& i) : n(i) { } 895 SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 896 _G.s_false_t_true_map>first(n, false); 897 } 898 operator Node() const { return n; } 899 }; 900 class TNodeIt { 901 Node n; 902 public: 903 TNodeIt() { } 904 TNodeIt(const Invalid& i) : n(i) { } 905 TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 906 _G.s_false_t_true_map>first(n, true); 907 } 908 operator Node() const { return n; } 909 }; 910 class OutEdgeIt { 911 public: 912 typename Graph::OutEdgeIt e; 913 public: 914 OutEdgeIt() { } 915 OutEdgeIt(const Invalid& i) : e(i) { } 916 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { 917 if (!(*(_G.s_false_t_true_map))[_n]) 918 e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); 919 else 920 e=INVALID; 921 } 922 operator Edge() const { return Edge(typename Graph::Edge(e)); } 923 }; 924 class InEdgeIt { 925 public: 926 typename Graph::InEdgeIt e; 927 public: 928 InEdgeIt() { } 929 InEdgeIt(const Invalid& i) : e(i) { } 930 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { 931 if ((*(_G.s_false_t_true_map))[_n]) 932 e=InEdgeIt(*(_G.graph), typename Graph::Node(_n)); 933 else 934 e=INVALID; 935 } 936 operator Edge() const { return Edge(typename Graph::Edge(e)); } 937 }; 938 939 using GraphWrapper<Graph>::first; 940 SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } 941 TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } 942 943 using GraphWrapper<Graph>::next; 944 SNodeIt& next(SNodeIt& n) const { 945 this>s_false_t_true_map>next(n); return n; 946 } 947 TNodeIt& next(TNodeIt& n) const { 948 this>s_false_t_true_map>next(n); return n; 949 } 950 951 Node tail(const Edge& e) { 952 if (!(*(this>s_false_t_true_map))[this>graph>tail(e)]) 953 return Node(this>graph>tail(e)); 954 else 955 return Node(this>graph>head(e)); 956 } 957 Node head(const Edge& e) { 958 if (!(*(this>s_false_t_true_map))[this>graph>tail(e)]) 959 return Node(this>graph>head(e)); 960 else 961 return Node(this>graph>tail(e)); 962 } 963 964 Node aNode(const OutEdgeIt& e) const { 965 return Node(this>graph>aNode(e.e)); 966 } 967 Node aNode(const InEdgeIt& e) const { 968 return Node(this>graph>aNode(e.e)); 969 } 970 Node bNode(const OutEdgeIt& e) const { 971 return Node(this>graph>bNode(e.e)); 972 } 973 Node bNode(const InEdgeIt& e) const { 974 return Node(this>graph>bNode(e.e)); 865 975 } 866 976 }; 
src/work/marci/makefile
r358 r368 1 #CXX3 = g++3.02 1 CXX2 = g++2.95 3 #CXX3.3 = g++4 2 CXX3 := $(shell type p g++3.3  type p g++3.2  type p g++3.0  type p g++3  echo g++) 5 3 CXX=$(CXX3) 6 4 CC=$(CXX) 7 #CXXFLAGS = W Wall ansi pedantic I. I.. I../alpar8 5 #LEDAROOT ?= /ledasrc/LEDA4.1 9 6 BOOSTROOT ?= /home/marci/boost … … 13 10 14 11 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo 15 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand 12 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test 16 13 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda 17 14
Note: See TracChangeset
for help on using the changeset viewer.