CYCLUS
exchange_graph.h
Go to the documentation of this file.
1 #ifndef CYCLUS_SRC_EXCHANGE_GRAPH_H_
2 #define CYCLUS_SRC_EXCHANGE_GRAPH_H_
3 
4 #include <limits>
5 #include <map>
6 #include <string>
7 #include <utility>
8 #include <vector>
9 
10 #include <boost/shared_ptr.hpp>
11 #include <boost/weak_ptr.hpp>
12 
13 namespace cyclus {
14 
15 class ExchangeNodeGroup;
16 class Arc;
17 
18 /// @class ExchangeNode
19 ///
20 /// @brief ExchangeNodes are used in ExchangeGraphs to house information about a
21 /// given translated Bid or Request. Specifically, ExchangeNodes have a notion
22 /// of unit capacities that the given Bid or Request contribute to the overall
23 /// capacity of ExchangeNodeGroup. ExchangeNodes also have a notion of quantity,
24 /// i.e., the maximum amount of a resource that can be attributed to
25 /// it. Finally, nodes can be exclusive, that is to say that they represent a
26 /// request or bid that must be exclusively satisfied (it can not be split).
27 struct ExchangeNode {
28  public:
29  typedef boost::shared_ptr<ExchangeNode> Ptr;
30 
31  ExchangeNode();
32  explicit ExchangeNode(double qty);
33  ExchangeNode(double qty, bool exclusive);
34  ExchangeNode(double qty, bool exclusive, std::string commod);
35  ExchangeNode(double qty, bool exclusive, std::string commod, int agent_id);
36 
37  /// @brief the parent ExchangeNodeGroup to which this ExchangeNode belongs
39 
40  /// @brief unit values associated with this ExchangeNode corresponding to
41  /// capacties of its parent ExchangeNodeGroup. This information corresponds to
42  /// the resource object from which this ExchangeNode was translated.
43  std::map<Arc, std::vector<double> > unit_capacities;
44 
45  /// @brief preference values for arcs
46  std::map<Arc, double> prefs;
47 
48  /// @brief whether this node represents an exclusive request or offer
49  bool exclusive;
50 
51  /// @brief the commodity associated with this exchange node
52  std::string commod;
53 
54  /// @brief the id of the agent associated with this node
55  int agent_id;
56 
57  /// @brief the maximum amount of a resource that can be associated with this
58  /// node
59  double qty;
60 };
61 
62 /// @brief An arc represents a possible connection between two nodes in the
63 /// bipartite resource exchange graph. It is common to refer to the two sets of
64 /// nodes in a bipartite graph by the set variables U and V (see
65 /// http://en.wikipedia.org/wiki/Bipartite_graph). By convention, arc.unode() ==
66 /// request node, arc.vnode() == bid node.
67 class Arc {
68  public:
69  /// default required for usage in maps
70  /// @warning, in general do not use this constructor; it exists for arcs to be
71  /// map values
72  Arc() {}
73 
74  Arc(boost::shared_ptr<ExchangeNode> unode,
75  boost::shared_ptr<ExchangeNode> vnode);
76  Arc(const Arc& other);
77 
78  inline Arc& operator=(const Arc& other) {
79  unode_ = other.unode();
80  vnode_ = other.vnode();
81  exclusive_ = other.exclusive();
82  excl_val_ = other.excl_val();
83  return *this;
84  }
85 
86  inline bool operator <(const Arc& rhs) const {
87  return unode_ < rhs.unode_ ||
88  (!(rhs.unode_ < unode_) && vnode_ < rhs.vnode_);
89  }
90 
91  inline bool operator==(const Arc& rhs) const {
92  return unode() == rhs.unode() && vnode() == rhs.vnode();
93  }
94 
95  inline boost::shared_ptr<ExchangeNode> unode() const { return unode_.lock(); }
96  inline boost::shared_ptr<ExchangeNode> vnode() const { return vnode_.lock(); }
97  inline bool exclusive() const { return exclusive_; }
98  inline double excl_val() const { return excl_val_; }
99  inline double pref() const { return pref_; }
100  inline void pref(double pref) { pref_ = pref; }
101 
102  private:
103  boost::weak_ptr<ExchangeNode> unode_;
104  boost::weak_ptr<ExchangeNode> vnode_;
105  bool exclusive_;
106  double excl_val_, pref_;
107 };
108 
109 /// @brief ExchangeNode-ExchangeNode equality operator
110 inline bool operator==(const ExchangeNode& lhs, const ExchangeNode& rhs);
111 
112 /// @class ExchangeNodeGroup
113 ///
114 /// @brief A ExchangeNodeGroup is a collection of ExchangeNodes, and is the
115 /// ExchangeGraph representation of a BidPortfolio or RequestPortfolio. It
116 /// houses information about the concrete capacities associated with either
117 /// portfolio.
119  public:
120  typedef boost::shared_ptr<ExchangeNodeGroup> Ptr;
121 
122  const std::vector<ExchangeNode::Ptr>& nodes() const { return nodes_; }
123  std::vector<ExchangeNode::Ptr>& nodes() { return nodes_; }
124 
125  /// @brief exclusive node groups represent nodes over whose combined arcs flow
126  /// can only exist on one arc
127  const std::vector< std::vector<ExchangeNode::Ptr> >&
129  return excl_node_groups_;
130  }
131  std::vector< std::vector<ExchangeNode::Ptr> >& excl_node_groups() {
132  return excl_node_groups_;
133  }
134 
135  /// @brief the flow capacities assocaited with this group
136  const std::vector<double>& capacities() const { return capacities_; }
137  std::vector<double>& capacities() { return capacities_; }
138 
139  /// @brief Add the node to the ExchangeNodeGroup and informs the node it is a
140  /// member of this ExchangeNodeGroup
141  virtual void AddExchangeNode(ExchangeNode::Ptr node);
142 
143  /// @brief Adds a node grouping to the set of exclusive node groups, in
144  /// general this function is used for bid exclusivity. An exclusive group
145  /// implies that for all nodes in that group, flow is only allowed to flow
146  /// over one. This is the case for multiple bids that refer to the same
147  /// exclusive object.
148  inline void AddExclGroup(std::vector<ExchangeNode::Ptr>& nodes) {
149  excl_node_groups_.push_back(nodes);
150  }
151 
152  /// @return true of any nodes have arcs associated with them
153  bool HasArcs() {
154  for (std::vector<ExchangeNode::Ptr>::iterator it = nodes_.begin();
155  it != nodes_.end();
156  ++it) {
157  if (it->get()->prefs.size() > 0)
158  return true;
159  }
160  return false;
161  }
162 
163  /// @brief adds a single node to the set of exclusive node groupings, in
164  /// general this function is used for demand exclusivity
165  void AddExclNode(ExchangeNode::Ptr n);
166 
167  /// @brief Add a flow capacity to the group
168  inline void AddCapacity(double c) { capacities_.push_back(c); }
169 
170  private:
171  std::vector<ExchangeNode::Ptr> nodes_;
172  std::vector< std::vector<ExchangeNode::Ptr> > excl_node_groups_;
173  std::vector<double> capacities_;
174 };
175 
176 /// @class RequestGroup
177 ///
178 /// @brief A RequestGroup is a specific ExchangeNodeGroup with a notion of an total
179 /// requested quantity.
181  public:
182  typedef boost::shared_ptr<RequestGroup> Ptr;
183 
184  explicit RequestGroup(double qty = 0.0);
185 
186  double qty() { return qty_; }
187 
188  /// @brief Add the node to the ExchangeNodeGroup and informs the node it is a
189  /// member of this ExchangeNodeGroup, if the node is exclusive, also add it to
190  /// the group of exclusive nodes
191  virtual void AddExchangeNode(ExchangeNode::Ptr node);
192 
193  private:
194  double qty_;
195 };
196 
197 typedef std::pair<Arc, double> Match;
198 
199 /// @class ExchangeGraph
200 ///
201 /// @brief An ExchangeGraph is a resource-neutral representation of a
202 /// ResourceExchange. In general, it is produced via translation by an
203 /// ExchangeTranslator. It is comprised of ExchangeNodes that are collected into
204 /// ExchangeNodeGroups. Arcs are defined, connecting ExchangeNodes to each
205 /// other. An ExchangeSolver can solve a given instance of an ExchangeGraph, and
206 /// the solution is stored on the Graph in the form of Matches.
208  public:
209  typedef boost::shared_ptr<ExchangeGraph> Ptr;
210 
211  ExchangeGraph();
212 
213  /// @brief adds a request group to the graph
214  void AddRequestGroup(RequestGroup::Ptr prs);
215 
216  /// @brief adds a supply group to the graph
217  void AddSupplyGroup(ExchangeNodeGroup::Ptr prs);
218 
219  /// @brief adds an arc to the graph
220  void AddArc(const Arc& a);
221 
222  /// @brief adds a match for a quanity of flow along an arc
223  ///
224  /// @param pa the arc corresponding to a match
225  /// @param qty the amount of flow corresponding to a match
226  void AddMatch(const Arc& a, double qty);
227 
228  /// clears all matches
229  inline void ClearMatches() { matches_.clear(); }
230 
231  inline const std::vector<RequestGroup::Ptr>& request_groups() const {
232  return request_groups_;
233  }
234  inline std::vector<RequestGroup::Ptr>& request_groups() {
235  return request_groups_;
236  }
237 
238  inline const std::vector<ExchangeNodeGroup::Ptr>& supply_groups() const {
239  return supply_groups_;
240  }
241  inline std::vector<ExchangeNodeGroup::Ptr>& supply_groups() {
242  return supply_groups_;
243  }
244 
245  inline const std::map<ExchangeNode::Ptr, std::vector<Arc> >&
246  node_arc_map() const {
247  return node_arc_map_;
248  }
249  inline std::map<ExchangeNode::Ptr, std::vector<Arc> >& node_arc_map() {
250  return node_arc_map_;
251  }
252 
253  inline const std::vector<Match>& matches() { return matches_; }
254 
255  inline const std::vector<Arc>& arcs() const { return arcs_; }
256  inline std::vector<Arc>& arcs() { return arcs_; }
257 
258  inline const std::map<Arc, int>& arc_ids() const { return arc_ids_; }
259  inline std::map<Arc, int>& arc_ids() { return arc_ids_; }
260 
261  inline const std::map<int, Arc>& arc_by_id() const { return arc_by_id_; }
262  inline std::map<int, Arc>& arc_by_id() { return arc_by_id_; }
263 
264  private:
265  std::vector<RequestGroup::Ptr> request_groups_;
266  std::vector<ExchangeNodeGroup::Ptr> supply_groups_;
267  std::map<ExchangeNode::Ptr, std::vector<Arc> > node_arc_map_;
268  std::vector<Match> matches_;
269  std::vector<Arc> arcs_;
270  std::map<Arc, int> arc_ids_;
271  std::map<int, Arc> arc_by_id_;
272  int next_arc_id_;
273 };
274 
275 } // namespace cyclus
276 
277 #endif // CYCLUS_SRC_EXCHANGE_GRAPH_H_
std::vector< ExchangeNodeGroup::Ptr > & supply_groups()
std::map< Arc, double > prefs
preference values for arcs
const std::vector< std::vector< ExchangeNode::Ptr > > & excl_node_groups() const
exclusive node groups represent nodes over whose combined arcs flow can only exist on one arc ...
An arc represents a possible connection between two nodes in the bipartite resource exchange graph...
bool operator<(const CapacityConstraint< T > &lhs, const CapacityConstraint< T > &rhs)
CapacityConstraint-CapacityConstraint comparison operator, allows usage in ordered containers...
bool exclusive
whether this node represents an exclusive request or offer
bool exclusive() const
boost::shared_ptr< RequestGroup > Ptr
ExchangeNodeGroup * group
the parent ExchangeNodeGroup to which this ExchangeNode belongs
std::pair< Arc, double > Match
const std::vector< ExchangeNode::Ptr > & nodes() const
const std::vector< Arc > & arcs() const
A ExchangeNodeGroup is a collection of ExchangeNodes, and is the ExchangeGraph representation of a Bi...
const std::vector< double > & capacities() const
the flow capacities assocaited with this group
boost::shared_ptr< ExchangeNode > Ptr
std::vector< double > & capacities()
boost::shared_ptr< ExchangeNodeGroup > Ptr
std::string commod
the commodity associated with this exchange node
std::vector< ExchangeNode::Ptr > & nodes()
boost::shared_ptr< ExchangeNode > vnode() const
std::vector< RequestGroup::Ptr > & request_groups()
boost::shared_ptr< ExchangeGraph > Ptr
std::vector< Arc > & arcs()
void ClearMatches()
clears all matches
const std::vector< ExchangeNodeGroup::Ptr > & supply_groups() const
Arc & operator=(const Arc &other)
const std::vector< Match > & matches()
int agent_id
the id of the agent associated with this node
std::vector< std::vector< ExchangeNode::Ptr > > & excl_node_groups()
ExchangeNodes are used in ExchangeGraphs to house information about a given translated Bid or Request...
Arc()
default required for usage in maps
bool operator==(const Arc &rhs) const
std::map< int, Arc > & arc_by_id()
const std::map< Arc, int > & arc_ids() const
bool operator==(const CapacityConstraint< T > &lhs, const CapacityConstraint< T > &rhs)
CapacityConstraint-CapacityConstraint equality operator.
const std::map< ExchangeNode::Ptr, std::vector< Arc > > & node_arc_map() const
std::map< Arc, std::vector< double > > unit_capacities
unit values associated with this ExchangeNode corresponding to capacties of its parent ExchangeNodeGr...
taken directly from OsiSolverInterface.cpp on 2/17/14 from https://projects.coin-or.org/Osi/browser/trunk.
Definition: agent.cc:14
const std::map< int, Arc > & arc_by_id() const
double pref() const
void AddCapacity(double c)
Add a flow capacity to the group.
double qty
the maximum amount of a resource that can be associated with this node
double excl_val() const
void pref(double pref)
std::map< Arc, int > & arc_ids()
const std::vector< RequestGroup::Ptr > & request_groups() const
boost::shared_ptr< ExchangeNode > unode() const
An ExchangeGraph is a resource-neutral representation of a ResourceExchange.
std::map< ExchangeNode::Ptr, std::vector< Arc > > & node_arc_map()
void AddExclGroup(std::vector< ExchangeNode::Ptr > &nodes)
Adds a node grouping to the set of exclusive node groups, in general this function is used for bid ex...
A RequestGroup is a specific ExchangeNodeGroup with a notion of an total requested quantity...