- Gamma distributon random variable.
- Test file for random.h
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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 #ifndef LEMON_EDGE_SET_H
20 #define LEMON_EDGE_SET_H
23 #include <lemon/bits/default_map.h>
24 #include <lemon/bits/edge_set_extender.h>
26 /// \ingroup semi_adaptors
28 /// \brief EdgeSet classes.
30 /// Graphs which use another graph's node-set as own.
34 template <typename _Graph>
35 class ListEdgeSetBase {
39 typedef typename Graph::Node Node;
40 typedef typename Graph::NodeIt NodeIt;
45 int first_out, first_in;
46 NodeT() : first_out(-1), first_in(-1) {}
49 typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
55 int next_out, next_in;
56 int prev_out, prev_in;
57 EdgeT() : prev_out(-1), prev_in(-1) {}
60 std::vector<EdgeT> edges;
67 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
75 friend class ListEdgeSetBase<Graph>;
77 Edge(int _id) : id(_id) {}
81 Edge(Invalid) : id(-1) {}
82 bool operator==(const Edge& edge) const { return id == edge.id; }
83 bool operator!=(const Edge& edge) const { return id != edge.id; }
84 bool operator<(const Edge& edge) const { return id < edge.id; }
87 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
89 Edge addEdge(const Node& u, const Node& v) {
91 if (first_free_edge == -1) {
93 edges.push_back(EdgeT());
96 first_free_edge = edges[first_free_edge].next_in;
98 edges[n].next_in = (*nodes)[v].first_in;
99 if ((*nodes)[v].first_in != -1) {
100 edges[(*nodes)[v].first_in].prev_in = n;
102 (*nodes)[v].first_in = n;
103 edges[n].next_out = (*nodes)[u].first_out;
104 if ((*nodes)[u].first_out != -1) {
105 edges[(*nodes)[u].first_out].prev_out = n;
107 (*nodes)[u].first_out = n;
113 void erase(const Edge& edge) {
115 if (edges[n].prev_in != -1) {
116 edges[edges[n].prev_in].next_in = edges[n].next_in;
118 (*nodes)[edges[n].target].first_in = edges[n].next_in;
120 if (edges[n].next_in != -1) {
121 edges[edges[n].next_in].prev_in = edges[n].prev_in;
124 if (edges[n].prev_out != -1) {
125 edges[edges[n].prev_out].next_out = edges[n].next_out;
127 (*nodes)[edges[n].source].first_out = edges[n].next_out;
129 if (edges[n].next_out != -1) {
130 edges[edges[n].next_out].prev_out = edges[n].prev_out;
137 for (first(node); node != INVALID; next(node)) {
138 (*nodes)[node].first_in = -1;
139 (*nodes)[node].first_out = -1;
143 first_free_edge = -1;
146 void first(Node& node) const {
150 void next(Node& node) const {
154 void first(Edge& edge) const {
156 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
158 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
161 void next(Edge& edge) const {
162 if (edges[edge.id].next_in != -1) {
163 edge.id = edges[edge.id].next_in;
165 Node node = edges[edge.id].target;
166 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
168 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
172 void firstOut(Edge& edge, const Node& node) const {
173 edge.id = (*nodes)[node].first_out;
176 void nextOut(Edge& edge) const {
177 edge.id = edges[edge.id].next_out;
180 void firstIn(Edge& edge, const Node& node) const {
181 edge.id = (*nodes)[node].first_in;
184 void nextIn(Edge& edge) const {
185 edge.id = edges[edge.id].next_in;
188 int id(const Node& node) const { return graph->id(node); }
189 int id(const Edge& edge) const { return edge.id; }
191 Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
192 Edge edgeFromId(int ix) const { return Edge(ix); }
194 int maxNodeId() const { return graph->maxNodeId(); };
195 int maxEdgeId() const { return edges.size() - 1; }
197 Node source(const Edge& edge) const { return edges[edge.id].source;}
198 Node target(const Edge& edge) const { return edges[edge.id].target;}
200 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
202 NodeNotifier& notifier(Node) const {
203 return graph->notifier(Node());
206 template <typename _Value>
207 class NodeMap : public Graph::template NodeMap<_Value> {
210 typedef typename _Graph::template NodeMap<_Value> Parent;
212 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
213 : Parent(*edgeset.graph) {}
215 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
216 : Parent(*edgeset.graph, value) {}
218 NodeMap& operator=(const NodeMap& cmap) {
219 return operator=<NodeMap>(cmap);
222 template <typename CMap>
223 NodeMap& operator=(const CMap& cmap) {
224 Parent::operator=(cmap);
231 /// \ingroup semi_adaptors
233 /// \brief Graph using a node set of another graph and an
236 /// This structure can be used to establish another graph over a node set
237 /// of an existing one. The node iterator will go through the nodes of the
240 /// \param _Graph The type of the graph which shares its node set with
241 /// this class. Its interface must conform to the \ref concepts::Graph
244 /// In the edge extension and removing it conforms to the
245 /// \ref concepts::Graph "Graph" concept.
246 template <typename _Graph>
247 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
251 typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
253 typedef typename Parent::Node Node;
254 typedef typename Parent::Edge Edge;
256 typedef _Graph Graph;
259 typedef typename Parent::NodesImplBase NodesImplBase;
261 void eraseNode(const Node& node) {
263 Parent::firstOut(edge, node);
264 while (edge != INVALID ) {
266 Parent::firstOut(edge, node);
269 Parent::firstIn(edge, node);
270 while (edge != INVALID ) {
272 Parent::firstIn(edge, node);
280 class NodesImpl : public NodesImplBase {
282 typedef NodesImplBase Parent;
284 NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
285 : Parent(graph), _edgeset(edgeset) {}
287 virtual ~NodesImpl() {}
291 virtual void erase(const Node& node) {
292 _edgeset.eraseNode(node);
295 virtual void erase(const std::vector<Node>& nodes) {
296 for (int i = 0; i < int(nodes.size()); ++i) {
297 _edgeset.eraseNode(nodes[i]);
299 Parent::erase(nodes);
301 virtual void clear() {
302 _edgeset.clearNodes();
307 ListEdgeSet& _edgeset;
314 /// \brief Constructor of the adaptor.
316 /// Constructor of the adaptor.
317 ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
318 Parent::initalize(graph, nodes);
323 /// \ingroup semi_adaptors
325 /// \brief Graph using a node set of another graph and an
328 /// This structure can be used to establish another graph over a node set
329 /// of an existing one. The node iterator will go through the nodes of the
332 /// \param _Graph The type of the graph which shares its node set with
333 /// this class. Its interface must conform to the \ref concepts::Graph
336 /// In the edge extension and removing it conforms to the
337 /// \ref concepts::UGraph "UGraph" concept.
338 template <typename _Graph>
340 : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
344 typedef UEdgeSetExtender<UndirGraphExtender<
345 ListEdgeSetBase<_Graph> > > Parent;
347 typedef typename Parent::Node Node;
348 typedef typename Parent::Edge Edge;
350 typedef _Graph Graph;
353 typedef typename Parent::NodesImplBase NodesImplBase;
355 void eraseNode(const Node& node) {
357 Parent::firstOut(edge, node);
358 while (edge != INVALID ) {
360 Parent::firstOut(edge, node);
369 class NodesImpl : public NodesImplBase {
371 typedef NodesImplBase Parent;
373 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
374 : Parent(graph), _edgeset(edgeset) {}
376 virtual ~NodesImpl() {}
380 virtual void erase(const Node& node) {
381 _edgeset.eraseNode(node);
384 virtual void erase(const std::vector<Node>& nodes) {
385 for (int i = 0; i < int(nodes.size()); ++i) {
386 _edgeset.eraseNode(nodes[i]);
388 Parent::erase(nodes);
390 virtual void clear() {
391 _edgeset.clearNodes();
396 ListUEdgeSet& _edgeset;
403 /// \brief Constructor of the adaptor.
405 /// Constructor of the adaptor.
406 ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
407 Parent::initalize(graph, nodes);
412 template <typename _Graph>
413 class SmartEdgeSetBase {
416 typedef _Graph Graph;
417 typedef typename Graph::Node Node;
418 typedef typename Graph::NodeIt NodeIt;
423 int first_out, first_in;
424 NodeT() : first_out(-1), first_in(-1) {}
427 typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
429 NodesImplBase* nodes;
433 int next_out, next_in;
437 std::vector<EdgeT> edges;
441 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
449 friend class SmartEdgeSetBase<Graph>;
451 Edge(int _id) : id(_id) {}
455 Edge(Invalid) : id(-1) {}
456 bool operator==(const Edge& edge) const { return id == edge.id; }
457 bool operator!=(const Edge& edge) const { return id != edge.id; }
458 bool operator<(const Edge& edge) const { return id < edge.id; }
461 SmartEdgeSetBase() {}
463 Edge addEdge(const Node& u, const Node& v) {
464 int n = edges.size();
465 edges.push_back(EdgeT());
466 edges[n].next_in = (*nodes)[v].first_in;
467 (*nodes)[v].first_in = n;
468 edges[n].next_out = (*nodes)[u].first_out;
469 (*nodes)[u].first_out = n;
477 for (first(node); node != INVALID; next(node)) {
478 (*nodes)[node].first_in = -1;
479 (*nodes)[node].first_out = -1;
484 void first(Node& node) const {
488 void next(Node& node) const {
492 void first(Edge& edge) const {
493 edge.id = edges.size() - 1;
496 void next(Edge& edge) const {
500 void firstOut(Edge& edge, const Node& node) const {
501 edge.id = (*nodes)[node].first_out;
504 void nextOut(Edge& edge) const {
505 edge.id = edges[edge.id].next_out;
508 void firstIn(Edge& edge, const Node& node) const {
509 edge.id = (*nodes)[node].first_in;
512 void nextIn(Edge& edge) const {
513 edge.id = edges[edge.id].next_in;
516 int id(const Node& node) const { return graph->id(node); }
517 int id(const Edge& edge) const { return edge.id; }
519 Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
520 Edge edgeFromId(int ix) const { return Edge(ix); }
522 int maxNodeId() const { return graph->maxNodeId(); };
523 int maxEdgeId() const { return edges.size() - 1; }
525 Node source(const Edge& edge) const { return edges[edge.id].source;}
526 Node target(const Edge& edge) const { return edges[edge.id].target;}
528 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
530 NodeNotifier& notifier(Node) const {
531 return graph->notifier(Node());
534 template <typename _Value>
535 class NodeMap : public Graph::template NodeMap<_Value> {
538 typedef typename _Graph::template NodeMap<_Value> Parent;
540 explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
541 : Parent(*edgeset.graph) { }
543 NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
544 : Parent(*edgeset.graph, value) { }
546 NodeMap& operator=(const NodeMap& cmap) {
547 return operator=<NodeMap>(cmap);
550 template <typename CMap>
551 NodeMap& operator=(const CMap& cmap) {
552 Parent::operator=(cmap);
560 /// \ingroup semi_adaptors
562 /// \brief Graph using a node set of another graph and an
565 /// This structure can be used to establish another graph over a node set
566 /// of an existing one. The node iterator will go through the nodes of the
569 /// \param _Graph The type of the graph which shares its node set with
570 /// this class. Its interface must conform to the \ref concepts::Graph
573 /// In the edge extension and removing it conforms to the
574 /// \ref concepts::Graph "Graph" concept.
575 template <typename _Graph>
576 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
580 typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
582 typedef typename Parent::Node Node;
583 typedef typename Parent::Edge Edge;
585 typedef _Graph Graph;
589 typedef typename Parent::NodesImplBase NodesImplBase;
591 void eraseNode(const Node& node) {
592 if (Parent::InEdgeIt(*this, node) == INVALID &&
593 Parent::OutEdgeIt(*this, node) == INVALID) {
596 throw typename NodesImplBase::Notifier::ImmediateDetach();
603 class NodesImpl : public NodesImplBase {
605 typedef NodesImplBase Parent;
607 NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
608 : Parent(graph), _edgeset(edgeset) {}
610 virtual ~NodesImpl() {}
612 bool attached() const {
613 return Parent::attached();
618 virtual void erase(const Node& node) {
620 _edgeset.eraseNode(node);
622 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
627 virtual void erase(const std::vector<Node>& nodes) {
629 for (int i = 0; i < int(nodes.size()); ++i) {
630 _edgeset.eraseNode(nodes[i]);
632 Parent::erase(nodes);
633 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
638 virtual void clear() {
639 _edgeset.clearNodes();
644 SmartEdgeSet& _edgeset;
651 /// \brief Constructor of the adaptor.
653 /// Constructor of the adaptor.
654 SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
655 Parent::initalize(graph, nodes);
659 return nodes.attached();
664 /// \ingroup semi_adaptors
666 /// \brief Graph using a node set of another graph and an
669 /// This structure can be used to establish another graph over a node set
670 /// of an existing one. The node iterator will go through the nodes of the
673 /// \param _Graph The type of the graph which shares its node set with
674 /// this class. Its interface must conform to the \ref concepts::Graph
677 /// In the edge extension and removing it conforms to the
678 /// \ref concepts::UGraph "UGraph" concept.
679 template <typename _Graph>
681 : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
685 typedef UEdgeSetExtender<UndirGraphExtender<
686 SmartEdgeSetBase<_Graph> > > Parent;
688 typedef typename Parent::Node Node;
689 typedef typename Parent::Edge Edge;
691 typedef _Graph Graph;
695 typedef typename Parent::NodesImplBase NodesImplBase;
697 void eraseNode(const Node& node) {
698 if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
701 throw typename NodesImplBase::Notifier::ImmediateDetach();
708 class NodesImpl : public NodesImplBase {
710 typedef NodesImplBase Parent;
712 NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
713 : Parent(graph), _edgeset(edgeset) {}
715 virtual ~NodesImpl() {}
717 bool attached() const {
718 return Parent::attached();
723 virtual void erase(const Node& node) {
725 _edgeset.eraseNode(node);
727 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
732 virtual void erase(const std::vector<Node>& nodes) {
734 for (int i = 0; i < int(nodes.size()); ++i) {
735 _edgeset.eraseNode(nodes[i]);
737 Parent::erase(nodes);
738 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
743 virtual void clear() {
744 _edgeset.clearNodes();
749 SmartUEdgeSet& _edgeset;
756 /// \brief Constructor of the adaptor.
758 /// Constructor of the adaptor.
759 SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
760 Parent::initalize(graph, nodes);
764 return nodes.attached();