vpr::sim::NetworkGraph class Reference

00098       : mGraphValid(false)
00099    {
00100       /* Do nothing. */ ;
00101    }

00072 {
00073    vpr::ReturnStatus status;
00074    std::ifstream input_file(path.c_str());
00075 
00076    if ( input_file.is_open() )
00077    {
00078       vpr::Uint32 node_count, full_edge_count, half_edge_count;
00079       std::map<int, boost::graph_traits<net_graph_t>::vertex_descriptor> vertex_map;
00080       std::string temp_str;
00081       vpr::Uint32 index, last_index, localhost_index;
00082       vpr::Uint16 node_type;
00083 
00084       input_file >> node_count;
00085 
00086       for ( vpr::Uint32 i = 0; i < node_count; ++i )
00087       {
00088          std::string node_ip;
00089 
00090          input_file >> index >> node_type >> node_ip;
00091          skipToEOL(input_file);
00092 
00093          // Now create the vertex and add it to the graph.
00094          NetworkNodePtr node_prop( new NetworkNode(index, node_type, node_ip) );
00095          vertex_map[index] = boost::add_vertex(NodeProperty( node_prop),
00096                                                mGraph);
00097       }
00098 
00099       // Add a node to the graph that will represent localhost.  It will have
00100       // an edge to the last node added to the graph.
00101       // index and node_type will have the values of the last vertex added to
00102       // the graph.  We will use this vertex to represent localhost.
00103       last_index      = index;
00104       localhost_index = last_index + 1;
00105       NetworkNodePtr node_prop(new NetworkNode(localhost_index, node_type,
00106                                                std::string("127.0.0.1")));
00107       vprASSERT(vertex_map.count(localhost_index) == 0 && "The index for localhost is already in use");
00108       vertex_map[localhost_index] = boost::add_vertex(NodeProperty(node_prop),
00109                                                       mGraph);
00110 
00111       input_file >> full_edge_count;
00112 
00113       // The file format tells us that there are twice as many edges as
00114       // actually listed--probably to indicate bidirectional links.
00115       half_edge_count = full_edge_count / 2;
00116 
00117       net_edge_t new_edge;
00118       bool added;
00119       boost::property_map<net_graph_t, boost::edge_weight_t>::type weight_map;
00120       weight_map = boost::get(boost::edge_weight_t(), mGraph);
00121 
00122       // This is outside the loop so that it can be used when making the
00123       // loopback link for localhost.
00124       vpr::Uint16 net_id;
00125 
00126       for ( vpr::Uint32 i = 0; i < full_edge_count; ++i )
00127       {
00128          double length, delay, bw;
00129          vpr::Uint32 from_node, to_node;
00130          std::string net_type, net_ip;
00131 
00132          input_file >> from_node >> to_node >> length >> delay >> bw
00133                     >> net_type >> net_id >> net_ip;
00134 
00135          // This is here mainly for debugging this clunky "parser".
00136          vprDEBUG(vprDBG_ALL, vprDBG_HVERB_LVL)
00137             << "Loading edge #" << i << ": (" << from_node << " --> "
00138             << to_node << ", " << length << " miles, " << delay << " us, "
00139             << bw << " Mbps, type: " << net_type << ", ID: " << net_id << ", "
00140             << net_ip << ")\n" << vprDEBUG_FLUSH;
00141 
00142          // Now add the edge to the graph.
00143          NetworkLine line(length, bw, delay, net_type, net_id, net_ip);
00144          boost::tie(new_edge, added) = boost::add_edge(vertex_map[from_node],
00145                                                        vertex_map[to_node],
00146                                                        LineProperty(line),
00147                                                        mGraph);
00148 
00149          if ( added )
00150          {
00151             weight_map[new_edge] = line.getWeight();
00152          }
00153 
00154          // Sanity check to ensure that we do not get stuck trying to read
00155          // bytes that aren't there.  This probably slows things down, but I
00156          // don't know of a better way to do this.
00157          if ( input_file.peek() == EOF && i + 1 < full_edge_count )
00158          {
00159             vprDEBUG(vprDBG_ALL, vprDBG_WARNING_LVL)
00160                << "WARNING: Expected " << full_edge_count
00161                << " edges, found " << i + 1 << std::endl << vprDEBUG_FLUSH;
00162             break;
00163          }
00164       }
00165 
00166       // Make a very, very short, very, very high-bandwidth link for the
00167       // localhost loopback.
00168       NetworkLine line(0.0000001f, 100000, 0.0000001f, std::string("LOOPBACK"),
00169                        net_id, std::string("127.0.0.0"));
00170       boost::tie(new_edge, added) = boost::add_edge(vertex_map[localhost_index],
00171                                                     vertex_map[last_index],
00172                                                     LineProperty(line),
00173                                                     mGraph);
00174       vprASSERT(added && "Addition of loopback line for localhost failed");
00175       weight_map[new_edge] = line.getWeight();
00176 
00177       mGraphValid = true;
00178    }
00179    else
00180    {
00181       vprDEBUG(vprDBG_ALL, vprDBG_CRITICAL_LVL)
00182          << "ERROR: Failed to open graph input file named " << path
00183          << std::endl << vprDEBUG_FLUSH;
00184       status.setCode(vpr::ReturnStatus::Fail);
00185    }
00186 
00187    return status;
00188 }

00110    {
00111       return mGraphValid;
00112    }

00118    {
00119       mGraph.clear();
00120    }

00191 {
00192    // XXX: Need to make an assertion that e is in mGraph!
00193 //   vprASSERT(... && "Given edge not found in the graph!");
00194 
00195    boost::property_map<net_graph_t, network_line_t>::type line_prop_map;
00196 
00197    line_prop_map = boost::get(network_line_t(), mGraph);
00198 
00199    return line_prop_map[e];
00200 }

00204 {
00205    // XXX: Need to make an assertion that e is in mGraph!
00206 //   vprASSERT(... && "Given edge not found in the graph!");
00207 
00208    boost::property_map<net_graph_t, network_line_t>::type line_prop_map;
00209 
00210    line_prop_map    = boost::get(network_line_t(), mGraph);
00211    line_prop_map[e] = prop;
00212 }

00152    {
00153       return boost::vertex(index, mGraph);
00154    }

00216 {
00217    vprASSERT(isValid() && "Trying to use invalid graph");
00218 
00219    vpr::ReturnStatus status(vpr::ReturnStatus::Fail);
00220    boost::graph_traits<net_graph_t>::vertex_iterator vi, vi_end;
00221    NetworkNodePtr node_prop;
00222 
00223    boost::tie(vi, vi_end) = boost::vertices(mGraph);
00224 
00225    for ( ; vi != vi_end; ++vi )
00226    {
00227       node_prop = getNodeProperty(*vi);
00228 
00229       if ( node_prop->getIpAddress() == addr )
00230       {
00231          node = *vi;
00232          status.setCode(vpr::ReturnStatus::Succeed);
00233          break;
00234       }
00235    }
00236 
00237    return status;
00238 }

00241 {
00242    // XXX: Need to make an assertion that v is in mGraph!
00243 //   vprASSERT(... && "Given vertex not found in the graph!");
00244 
00245    boost::property_map<net_graph_t, network_node_t>::type node_prop_map;
00246 
00247    node_prop_map = boost::get(network_node_t(), mGraph);
00248 
00249    return node_prop_map[v];
00250 }

00254 {
00255    // XXX: Need to make an assertion that v is in mGraph!
00256 //   vprASSERT(... && "Given vertex not found in the graph!");
00257 
00258    boost::property_map<net_graph_t, network_node_t>::type node_prop_map;
00259 
00260    node_prop_map    = boost::get(network_node_t(), mGraph);
00261    node_prop_map[v] = prop;
00262 }

00191    {
00192       return boost::edge(u, v, mGraph);
00193    }

00267 {
00268    NetworkGraph::VertexListPtr vlist(new NetworkGraph::VertexList);
00269    std::vector<int> dist(boost::num_vertices(mGraph));
00270    std::vector<net_vertex_t> pred(boost::num_vertices(mGraph));
00271    NetworkGraph::net_vertex_t p(dest), q;
00272    boost::property_map<net_graph_t, network_node_t>::const_type node_prop_map;
00273    boost::property_map<net_graph_t, boost::edge_weight_t>::const_type weight_map;
00274 
00275    // NOTE: There is no default constructor for this type.  The copy
00276    // constructor must be used.
00277    boost::property_map<net_graph_t, boost::vertex_index_t>::const_type vertex_map
00278       = boost::get(boost::vertex_index_t(), mGraph);
00279 
00280    node_prop_map = boost::get(network_node_t(), mGraph);
00281    weight_map    = boost::get(boost::edge_weight_t(), mGraph);
00282 
00283    vprASSERT(boost::out_degree(src, mGraph) > 0 && "No outgoing edges from source");
00284    vprASSERT(boost::out_degree(dest, mGraph) > 0 && "No outgoing edges from destination");
00285 
00286    vprDEBUG_BEGIN(vprDBG_ALL, vprDBG_STATE_LVL)
00287       << "NetworkGraph::getShortestPath(): Looking up the shortest path "
00288       << "between " << node_prop_map[src]->getIpAddressString() << " and "
00289       << node_prop_map[dest]->getIpAddressString() << "\n" << vprDEBUG_FLUSH;
00290 
00291 //   boost::dijkstra_shortest_paths(mGraph, src,
00292 //                                  boost::distance_map(&dist[0]).predecessor_map(&pred[0]));
00293    boost::dijkstra_shortest_paths(mGraph, src, &pred[0], &dist[0], weight_map,
00294                                   vertex_map, std::less<int>(),
00295                                   boost::closed_plus<int>(),
00296                                   std::numeric_limits<int>::max(), 0,
00297                                   boost::default_dijkstra_visitor());
00298 
00299    vlist->push_back(dest);
00300 
00301    vprDEBUG(vprDBG_ALL, vprDBG_VERB_LVL)
00302       << "Path (dest <-- src): " << node_prop_map[dest]->getIpAddressString()
00303       << vprDEBUG_FLUSH;
00304 
00305    // Put the vertices returned in the predecessor map into a stack so that
00306    // we can reverse the order and put them into vlist.
00307    while ( (q = pred[p]) != p )
00308    {
00309       vprDEBUG_CONT(vprDBG_ALL, vprDBG_VERB_LVL)
00310          << " <-- " << node_prop_map[q]->getIpAddressString()
00311          << vprDEBUG_FLUSH;
00312 
00313       vlist->push_back(q);
00314       p = q;
00315    }
00316 
00317    vprDEBUG_CONT_END(vprDBG_ALL, vprDBG_STATE_LVL) << "\n" << vprDEBUG_FLUSH;
00318    vprASSERT(p == src && "Destination is unreachable from source!");
00319 
00320    std::reverse(vlist->begin(), vlist->end());
00321 
00322    return vlist;
00323 }

00326 {
00327    VertexListPtr new_path(new NetworkGraph::VertexList(path->size()));
00328 
00329    for ( vpr::Uint32 i = path->size(), j = 0; i > 0; i--, ++j )
00330    {
00331       (*new_path)[j] = (*path)[i - 1];
00332    }
00333 
00334    return new_path;
00335 }

00220    {
00221       return boost::num_vertices(mGraph);
00222    }

00228    {
00229       NetworkGraph::net_vertex_t source = boost::source(edge, mGraph);
00230 
00231       return vertex == source;
00232    }

00338 {
00339    vpr::ReturnStatus status;
00340    boost::graph_traits<net_graph_t>::vertex_iterator vi, vi_end;
00341    NetworkNodePtr node_prop;
00342 
00343    boost::tie(vi, vi_end) = boost::vertices(mGraph);
00344 
00345    for ( ; vi != vi_end; ++vi )
00346    {
00347       node_prop = getNodeProperty(*vi);
00348       list.push_back(std::pair<net_vertex_t, vpr::Uint32>(*vi,
00349                                                           node_prop->getIpAddress()));
00350    }
00351 
00352    return status;
00353 }

Public Types
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, NodeProperty, LineProperty >	net_graph_t
	Type of the BGL graph encapsulated by this class. More...
typedef boost::graph_traits< net_graph_t >::edge_descriptor	net_edge_t
	Type of an edge (network line) in the BGL graph. More...
typedef boost::graph_traits< net_graph_t >::vertex_descriptor	net_vertex_t
	Type of a vertex (network node) in the BGL graph. More...
typedef std::vector< net_vertex_t >	VertexList
typedef boost::shared_ptr< VertexList >	VertexListPtr
typedef std::vector< std::pair< net_vertex_t, vpr::Uint32 > >	AddressList
Public Methods
	NetworkGraph (void)
vpr::ReturnStatus	construct (const std::string &path)
	Fills in the graph using the contents of the specified file. More...
bool	isValid (void) const
void	clear (void)
	Removes all the lines (edges) and nodes (vertices) from the network. More...
vpr::sim::NetworkLine &	getLineProperty (const net_edge_t &e)
	Retrieves the property (an instance of vpr::sim::NetworkLine) for the given edge. More...
void	setLineProperty (const net_edge_t &e, const vpr::sim::NetworkLine &prop)
net_vertex_t	getNode (const vpr::Uint32 index) const
vpr::ReturnStatus	getNodeWithAddr (const vpr::Uint32 addr, net_vertex_t &node)
	Looks up the network node with the given address (a 32-bit IPv4 address). More...
vpr::sim::NetworkNodePtr	getNodeProperty (const net_vertex_t &e)
	Retrieves the property (an instance of vpr::sim::NetworkNode) for the given vertex. More...
void	setNodeProperty (const net_vertex_t &v, vpr::sim::NetworkNodePtr prop)
	Assigns the given property to the designated node. More...
std::pair< net_edge_t, bool >	getEdge (const net_vertex_t &u, const net_vertex_t &v) const
	Returns the edge that connects vertices u and v in this graph. More...
VertexListPtr	getShortestPath (const net_vertex_t &src, const net_vertex_t &dest) const
	Returns the shortest path (list of vertices) from src (source) to dest (destination). More...
VertexListPtr	reversePath (VertexListPtr path)
	Reverses the given vertex path. More...
vpr::Uint32	getNodeCount (void) const
	Returns the current number of nodes in this network. More...
bool	isSource (const net_vertex_t &vertex, const net_edge_t &edge) const
	Checks to see if the given vertex is the source of the given edge. More...
vpr::ReturnStatus	getAllAddresses (AddressList &list)
	Returns all the addresses in the network via the by-reference parameter. More...

vpr::sim::NetworkGraph Class Reference

Public Types

Public Methods

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation