Interface to the cplex MIP solver: it is little, a bit sour but it is ours.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #include<lemon/bits/invalid.h>
20 #include<lemon/topology.h>
27 ///This file provides an Euler tour iterator and ways to check
28 ///if a graph is euler.
33 ///Euler iterator for directed graphs.
36 ///This iterator converts to the \c Edge type of the graph and using
37 ///operator ++ it provides an Euler tour of a \e directed
38 ///graph (if there exists).
41 ///if the given graph if Euler (i.e it has only one nontrivial component
42 ///and the in-degree is equal to the out-degree for all nodes),
43 ///the following code will put the edges of \c g
44 ///to the vector \c et according to an
45 ///Euler tour of \c g.
47 /// std::vector<ListGraph::Edge> et;
48 /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e)
51 ///If \c g is not Euler then the resulted tour will not be full or closed.
53 ///\todo Test required
57 typedef typename Graph::Node Node;
58 typedef typename Graph::NodeIt NodeIt;
59 typedef typename Graph::Edge Edge;
60 typedef typename Graph::EdgeIt EdgeIt;
61 typedef typename Graph::OutEdgeIt OutEdgeIt;
62 typedef typename Graph::InEdgeIt InEdgeIt;
65 typename Graph::NodeMap<OutEdgeIt> nedge;
66 std::list<Edge> euler;
72 ///\param _g A directed graph.
73 ///\param start The starting point of the tour. If it is not given
74 /// the tour will start from the first node.
75 EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
78 if(start==INVALID) start=NodeIt(g);
79 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
80 while(nedge[start]!=INVALID) {
81 euler.push_back(nedge[start]);
82 Node next=g.target(nedge[start]);
89 operator Edge() { return euler.empty()?INVALID:euler.front(); }
90 bool operator==(Invalid) { return euler.empty(); }
91 bool operator!=(Invalid) { return !euler.empty(); }
93 ///Next edge of the tour
94 EulerIt &operator++() {
95 Node s=g.target(euler.front());
97 //This produces a warning.Strange.
98 //std::list<Edge>::iterator next=euler.begin();
99 typename std::list<Edge>::iterator next=euler.begin();
100 while(nedge[s]!=INVALID) {
101 euler.insert(next,nedge[s]);
102 Node n=g.target(nedge[s]);
108 ///Postfix incrementation
110 ///\warning This incrementation
111 ///returns an \c Edge, not an \ref EulerIt, as one may
121 ///Euler iterator for undirected graphs.
123 /// \ingroup topology
124 ///This iterator converts to the \c Edge (or \cUEdge)
125 ///type of the graph and using
126 ///operator ++ it provides an Euler tour of an \undirected
127 ///graph (if there exists).
130 ///if the given graph if Euler (i.e it has only one nontrivial component
131 ///and the degree of each node is even),
132 ///the following code will print the edge IDs according to an
133 ///Euler tour of \c g.
135 /// for(UEulerIt<ListUGraph> e(g),e!=INVALID;++e) {
136 /// std::cout << g.id(UEdge(e)) << std::eol;
139 ///Although the iterator provides an Euler tour of an undirected graph,
140 ///in order to indicate the direction of the tour, UEulerIt
141 ///returns directed edges (that convert to the undirected ones, of course).
143 ///If \c g is not Euler then the resulted tour will not be full or closed.
145 ///\todo Test required
146 template<class Graph>
149 typedef typename Graph::Node Node;
150 typedef typename Graph::NodeIt NodeIt;
151 typedef typename Graph::Edge Edge;
152 typedef typename Graph::EdgeIt EdgeIt;
153 typedef typename Graph::OutEdgeIt OutEdgeIt;
154 typedef typename Graph::InEdgeIt InEdgeIt;
157 typename Graph::NodeMap<OutEdgeIt> nedge;
158 typename Graph::UEdgeMap<bool> visited;
159 std::list<Edge> euler;
165 ///\param _g An undirected graph.
166 ///\param start The starting point of the tour. If it is not given
167 /// the tour will start from the first node.
168 UEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
169 : g(_g), nedge(g), visited(g,false)
171 if(start==INVALID) start=NodeIt(g);
172 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
173 while(nedge[start]!=INVALID) {
174 euler.push_back(nedge[start]);
175 Node next=g.target(nedge[start]);
177 start=next; while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
182 operator Edge() { return euler.empty()?INVALID:euler.front(); }
183 bool operator==(Invalid) { return euler.empty(); }
184 bool operator!=(Invalid) { return !euler.empty(); }
186 ///Next edge of the tour
187 UEulerIt &operator++() {
188 Node s=g.target(euler.front());
190 typename std::list<Edge>::iterator next=euler.begin();
192 while(nedge[s]!=INVALID) {
193 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
194 if(nedge[s]==INVALID) break;
196 euler.insert(next,nedge[s]);
197 Node n=g.target(nedge[s]);
205 ///Postfix incrementation
207 ///\warning This incrementation
208 ///returns an \c Edge, not an \ref UEulerIt, as one may
219 ///Checks if the graph is Euler
221 /// \ingroup topology
222 ///Checks if the graph is Euler. It works for both directed and
223 ///undirected graphs.
224 ///\note By definition, a directed graph is called \e Euler if
225 ///and only if connected and the number of it is incoming and outgoing edges
226 ///are the same for each node.
227 ///Similarly, an undirected graph is called \e Euler if
228 ///and only if it is connected and the number of incident edges is even
229 ///for each node. <em>Therefore, there are graphs which are not Euler, but
230 ///still have an Euler tour</em>.
231 ///\todo Test required
232 template<class Graph>
236 typename enable_if<UndirectedTagIndicator<Graph>,bool>::type
237 euler(const Graph &g)
239 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
240 if(countIncEdges(g,n)%2) return false;
243 template<class Graph>
244 typename disable_if<UndirectedTagIndicator<Graph>,bool>::type
246 euler(const Graph &g)
248 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
249 if(countInEdges(g,n)!=countOutEdges(g,n)) return false;