vpr::sim::NetworkGraph Class Reference

Container for a BGL graph object that represents a simulated network constructed from an input file. More...

#include <vpr/md/SIM/Network/NetworkGraph.h>

List of all members.

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.
typedef boost::graph_traits< net_graph_t >::edge_descriptor	net_edge_t
	Type of an edge (network line) in the BGL graph.
typedef boost::graph_traits< net_graph_t >::vertex_descriptor	net_vertex_t
	Type of a vertex (network node) in the BGL graph.
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 Member Functions
	NetworkGraph ()
vpr::ReturnStatus	construct (const std::string &path)
	Fills in the graph using the contents of the specified file.
bool	isValid () const
void	clear ()
	Removes all the lines (edges) and nodes (vertices) from the network.
vpr::sim::NetworkLine &	getLineProperty (const net_edge_t &e)
	Retrieves the property (an instance of vpr::sim::NetworkLine) for the given edge.
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).
vpr::sim::NetworkNodePtr	getNodeProperty (const net_vertex_t &e)
	Retrieves the property (an instance of vpr::sim::NetworkNode) for the given vertex.
void	setNodeProperty (const net_vertex_t &v, vpr::sim::NetworkNodePtr prop)
	Assigns the given property to the designated node.
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.
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).
VertexListPtr	reversePath (VertexListPtr path)
	Reverses the given vertex path.
vpr::Uint32	getNodeCount () const
	Returns the current number of nodes in this network.
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.
vpr::ReturnStatus	getAllAddresses (AddressList &list)
	Returns all the addresses in the network via the by-reference parameter.

---

Detailed Description

Container for a BGL graph object that represents a simulated network constructed from an input file.

In the overall sim socket scheme, this sits at the hardware level (aka, the physical layer).

Definition at line 97 of file NetworkGraph.h.

---

Member Typedef Documentation

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, NodeProperty, LineProperty> vpr::sim::NetworkGraph::net_graph_t

Type of the BGL graph encapsulated by this class.

boost::vecS is chosen because graph traversal speed is important, and memory consumption is an issue for very large simulations. boost::listS does not perform well in those two areas.

Definition at line 131 of file NetworkGraph.h.

typedef boost::graph_traits<net_graph_t>::edge_descriptor vpr::sim::NetworkGraph::net_edge_t

Type of an edge (network line) in the BGL graph.

Definition at line 134 of file NetworkGraph.h.

typedef boost::graph_traits<net_graph_t>::vertex_descriptor vpr::sim::NetworkGraph::net_vertex_t

Type of a vertex (network node) in the BGL graph.

Definition at line 137 of file NetworkGraph.h.

typedef std::vector<net_vertex_t> vpr::sim::NetworkGraph::VertexList

Definition at line 139 of file NetworkGraph.h.

typedef boost::shared_ptr<VertexList> vpr::sim::NetworkGraph::VertexListPtr

Definition at line 140 of file NetworkGraph.h.

typedef std::vector<std::pair<net_vertex_t, vpr::Uint32> > vpr::sim::NetworkGraph::AddressList

Definition at line 142 of file NetworkGraph.h.

---

Constructor & Destructor Documentation

vpr::sim::NetworkGraph::NetworkGraph

(

)

[inline]

Definition at line 100 of file NetworkGraph.h.

      : mGraphValid(false)
   {
      /* Do nothing. */ ;
   }

---

Member Function Documentation

vpr::ReturnStatus vpr::sim::NetworkGraph::construct

(

const std::string &

path

)

Fills in the graph using the contents of the specified file.

The file must be in the GT-ITM "alternative" format.

Definition at line 71 of file NetworkGraph.cpp.

References vpr::ReturnStatus::Fail, vpr::sim::NetworkLine::getWeight(), vpr::ReturnStatus::setCode(), vpr::sim::skipToEOL(), vprASSERT, vprDBG_ALL(), vprDBG_CRITICAL_LVL, vprDBG_HVERB_LVL, vprDBG_WARNING_LVL, vprDEBUG, and vprDEBUG_FLUSH.

Referenced by vpr::sim::Controller::constructNetwork().

{
   vpr::ReturnStatus status;
   std::ifstream input_file(path.c_str());

   if ( input_file.is_open() )
   {
      vpr::Uint32 node_count, full_edge_count, half_edge_count;
      std::map<int, boost::graph_traits<net_graph_t>::vertex_descriptor> vertex_map;
      std::string temp_str;
      vpr::Uint32 index, last_index, localhost_index;
      vpr::Uint16 node_type;

      input_file >> node_count;

      for ( vpr::Uint32 i = 0; i < node_count; ++i )
      {
         std::string node_ip;

         input_file >> index >> node_type >> node_ip;
         skipToEOL(input_file);

         // Now create the vertex and add it to the graph.
         NetworkNodePtr node_prop( new NetworkNode(index, node_type, node_ip) );
         vertex_map[index] = boost::add_vertex(NodeProperty( node_prop),
                                               mGraph);
      }

      // Add a node to the graph that will represent localhost.  It will have
      // an edge to the last node added to the graph.
      // index and node_type will have the values of the last vertex added to
      // the graph.  We will use this vertex to represent localhost.
      last_index      = index;
      localhost_index = last_index + 1;
      NetworkNodePtr node_prop(new NetworkNode(localhost_index, node_type,
                                               std::string("127.0.0.1")));
      vprASSERT(vertex_map.count(localhost_index) == 0 && "The index for localhost is already in use");
      vertex_map[localhost_index] = boost::add_vertex(NodeProperty(node_prop),
                                                      mGraph);

      input_file >> full_edge_count;

      // The file format tells us that there are twice as many edges as
      // actually listed--probably to indicate bidirectional links.
      half_edge_count = full_edge_count / 2;

      net_edge_t new_edge;
      bool added;
      boost::property_map<net_graph_t, boost::edge_weight_t>::type weight_map;
      weight_map = boost::get(boost::edge_weight_t(), mGraph);

      // This is outside the loop so that it can be used when making the
      // loopback link for localhost.
      vpr::Uint16 net_id;

      for ( vpr::Uint32 i = 0; i < full_edge_count; ++i )
      {
         double length, delay, bw;
         vpr::Uint32 from_node, to_node;
         std::string net_type, net_ip;

         input_file >> from_node >> to_node >> length >> delay >> bw
                    >> net_type >> net_id >> net_ip;

         // This is here mainly for debugging this clunky "parser".
         vprDEBUG(vprDBG_ALL, vprDBG_HVERB_LVL)
            << "Loading edge #" << i << ": (" << from_node << " --> "
            << to_node << ", " << length << " miles, " << delay << " us, "
            << bw << " Mbps, type: " << net_type << ", ID: " << net_id << ", "
            << net_ip << ")\n" << vprDEBUG_FLUSH;

         // Now add the edge to the graph.
         NetworkLine line(length, bw, delay, net_type, net_id, net_ip);
         boost::tie(new_edge, added) = boost::add_edge(vertex_map[from_node],
                                                       vertex_map[to_node],
                                                       LineProperty(line),
                                                       mGraph);

         if ( added )
         {
            weight_map[new_edge] = line.getWeight();
         }

         // Sanity check to ensure that we do not get stuck trying to read
         // bytes that aren't there.  This probably slows things down, but I
         // don't know of a better way to do this.
         if ( input_file.peek() == EOF && i + 1 < full_edge_count )
         {
            vprDEBUG(vprDBG_ALL, vprDBG_WARNING_LVL)
               << "WARNING: Expected " << full_edge_count
               << " edges, found " << i + 1 << std::endl << vprDEBUG_FLUSH;
            break;
         }
      }

      // Make a very, very short, very, very high-bandwidth link for the
      // localhost loopback.
      NetworkLine line(0.0000001f, 100000, 0.0000001f, std::string("LOOPBACK"),
                       net_id, std::string("127.0.0.0"));
      boost::tie(new_edge, added) = boost::add_edge(vertex_map[localhost_index],
                                                    vertex_map[last_index],
                                                    LineProperty(line),
                                                    mGraph);
      vprASSERT(added && "Addition of loopback line for localhost failed");
      weight_map[new_edge] = line.getWeight();

      mGraphValid = true;
   }
   else
   {
      vprDEBUG(vprDBG_ALL, vprDBG_CRITICAL_LVL)
         << "ERROR: Failed to open graph input file named " << path
         << std::endl << vprDEBUG_FLUSH;
      status.setCode(vpr::ReturnStatus::Fail);
   }

   return status;
}

bool vpr::sim::NetworkGraph::isValid

(

)

const [inline]

Definition at line 112 of file NetworkGraph.h.

Referenced by vpr::sim::Controller::constructNetwork(), and getNodeWithAddr().

   {
      return mGraphValid;
   }

void vpr::sim::NetworkGraph::clear

(

)

[inline]

Removes all the lines (edges) and nodes (vertices) from the network.

Definition at line 120 of file NetworkGraph.h.

Referenced by vpr::sim::Controller::constructNetwork().

   {
      mGraph.clear();
   }

vpr::sim::NetworkLine & vpr::sim::NetworkGraph::getLineProperty

(

const net_edge_t &

e

)

Retrieves the property (an instance of vpr::sim::NetworkLine) for the given edge.

Precondition:

The given edge object must be in the graph.

Definition at line 190 of file NetworkGraph.cpp.

Referenced by vpr::sim::Controller::flushPath(), vpr::sim::Controller::processNextEvent(), and vpr::sim::SocketManager::sendMessage().

{
   // XXX: Need to make an assertion that e is in mGraph!
//   vprASSERT(... && "Given edge not found in the graph!");

   boost::property_map<net_graph_t, network_line_t>::type line_prop_map;

   line_prop_map = boost::get(network_line_t(), mGraph);

   return line_prop_map[e];
}

void vpr::sim::NetworkGraph::setLineProperty	(	const net_edge_t &	e,
		const vpr::sim::NetworkLine &	prop
	)

Definition at line 202 of file NetworkGraph.cpp.

{
   // XXX: Need to make an assertion that e is in mGraph!
//   vprASSERT(... && "Given edge not found in the graph!");

   boost::property_map<net_graph_t, network_line_t>::type line_prop_map;

   line_prop_map    = boost::get(network_line_t(), mGraph);
   line_prop_map[e] = prop;
}

net_vertex_t vpr::sim::NetworkGraph::getNode

(

const vpr::Uint32

index

)

const [inline]

Definition at line 154 of file NetworkGraph.h.

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

vpr::ReturnStatus vpr::sim::NetworkGraph::getNodeWithAddr	(	const vpr::Uint32	addr,
		net_vertex_t &	node
	)

Looks up the network node with the given address (a 32-bit IPv4 address).

If the node exists in the network, success is returned, and the by-reference parameter is assigned the discovered node. Otherwise, failure is returned to indicate that there is no node with the given address.

Parameters:

	addr	The address of the desired node as a 32-bit IPv4 address.
	node	Storage for the discovered node if one is found.

Definition at line 214 of file NetworkGraph.cpp.

References vpr::ReturnStatus::Fail, getNodeProperty(), isValid(), vpr::ReturnStatus::setCode(), vpr::ReturnStatus::Succeed, and vprASSERT.

Referenced by vpr::sim::SocketManager::assignToNode(), vpr::sim::SocketManager::ensureNetworkNodeIsRegistered(), and vpr::sim::SocketManager::sendMessageTo().

{
   vprASSERT(isValid() && "Trying to use invalid graph");

   vpr::ReturnStatus status(vpr::ReturnStatus::Fail);
   boost::graph_traits<net_graph_t>::vertex_iterator vi, vi_end;
   NetworkNodePtr node_prop;

   boost::tie(vi, vi_end) = boost::vertices(mGraph);

   for ( ; vi != vi_end; ++vi )
   {
      node_prop = getNodeProperty(*vi);

      if ( node_prop->getIpAddress() == addr )
      {
         node = *vi;
         status.setCode(vpr::ReturnStatus::Succeed);
         break;
      }
   }

   return status;
}

vpr::sim::NetworkNodePtr vpr::sim::NetworkGraph::getNodeProperty

(

const net_vertex_t &

e

)

Retrieves the property (an instance of vpr::sim::NetworkNode) for the given vertex.

Precondition:

The given vertex object must be in the graph.

Definition at line 240 of file NetworkGraph.cpp.

Referenced by vpr::sim::SocketManager::ensureNetworkNodeIsRegistered(), getAllAddresses(), getNodeWithAddr(), and vpr::sim::SocketManager::sendMessageTo().

{
   // XXX: Need to make an assertion that v is in mGraph!
//   vprASSERT(... && "Given vertex not found in the graph!");

   boost::property_map<net_graph_t, network_node_t>::type node_prop_map;

   node_prop_map = boost::get(network_node_t(), mGraph);

   return node_prop_map[v];
}

void vpr::sim::NetworkGraph::setNodeProperty	(	const net_vertex_t &	v,
		vpr::sim::NetworkNodePtr	prop
	)

Assigns the given property to the designated node.

Precondition:

The node object must be in the graph.

Definition at line 252 of file NetworkGraph.cpp.

{
   // XXX: Need to make an assertion that v is in mGraph!
//   vprASSERT(... && "Given vertex not found in the graph!");

   boost::property_map<net_graph_t, network_node_t>::type node_prop_map;

   node_prop_map    = boost::get(network_node_t(), mGraph);
   node_prop_map[v] = prop;
}

std::pair<net_edge_t, bool> vpr::sim::NetworkGraph::getEdge	(	const net_vertex_t &	u,
		const net_vertex_t &	v
	)			const [inline]

Returns the edge that connects vertices u and v in this graph.

Definition at line 191 of file NetworkGraph.h.

Referenced by vpr::sim::Controller::flushPath(), and vpr::sim::SocketManager::sendMessage().

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

NetworkGraph::VertexListPtr vpr::sim::NetworkGraph::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).

Parameters:

	src	The source node.
	dest	The destination node.

Returns:

Returns a pointer to a vertex list that is the shortest path between the two nodes.

Definition at line 264 of file NetworkGraph.cpp.

References vprASSERT, vprDBG_ALL(), vprDBG_STATE_LVL, vprDBG_VERB_LVL, vprDEBUG, vprDEBUG_BEGIN, vprDEBUG_CONT, vprDEBUG_CONT_END, and vprDEBUG_FLUSH.

Referenced by vpr::sim::SocketManager::connect(), vpr::sim::SocketManager::findRoute(), and vpr::sim::SocketManager::sendMessageTo().

{
   NetworkGraph::VertexListPtr vlist(new NetworkGraph::VertexList);
   std::vector<int> dist(boost::num_vertices(mGraph));
   std::vector<net_vertex_t> pred(boost::num_vertices(mGraph));
   NetworkGraph::net_vertex_t p(dest), q;
   boost::property_map<net_graph_t, network_node_t>::const_type node_prop_map;
   boost::property_map<net_graph_t, boost::edge_weight_t>::const_type weight_map;

   // NOTE: There is no default constructor for this type.  The copy
   // constructor must be used.
   boost::property_map<net_graph_t, boost::vertex_index_t>::const_type vertex_map
      = boost::get(boost::vertex_index_t(), mGraph);

   node_prop_map = boost::get(network_node_t(), mGraph);
   weight_map    = boost::get(boost::edge_weight_t(), mGraph);

   vprASSERT(boost::out_degree(src, mGraph) > 0 && "No outgoing edges from source");
   vprASSERT(boost::out_degree(dest, mGraph) > 0 && "No outgoing edges from destination");

   vprDEBUG_BEGIN(vprDBG_ALL, vprDBG_STATE_LVL)
      << "NetworkGraph::getShortestPath(): Looking up the shortest path "
      << "between " << node_prop_map[src]->getIpAddressString() << " and "
      << node_prop_map[dest]->getIpAddressString() << "\n" << vprDEBUG_FLUSH;

//   boost::dijkstra_shortest_paths(mGraph, src,
//                                  boost::distance_map(&dist[0]).predecessor_map(&pred[0]));
   boost::dijkstra_shortest_paths(mGraph, src, &pred[0], &dist[0], weight_map,
                                  vertex_map, std::less<int>(),
                                  boost::closed_plus<int>(),
                                  std::numeric_limits<int>::max(), 0,
                                  boost::default_dijkstra_visitor());

   vlist->push_back(dest);

   vprDEBUG(vprDBG_ALL, vprDBG_VERB_LVL)
      << "Path (dest <-- src): " << node_prop_map[dest]->getIpAddressString()
      << vprDEBUG_FLUSH;

   // Put the vertices returned in the predecessor map into a stack so that
   // we can reverse the order and put them into vlist.
   while ( (q = pred[p]) != p )
   {
      vprDEBUG_CONT(vprDBG_ALL, vprDBG_VERB_LVL)
         << " <-- " << node_prop_map[q]->getIpAddressString()
         << vprDEBUG_FLUSH;

      vlist->push_back(q);
      p = q;
   }

   vprDEBUG_CONT_END(vprDBG_ALL, vprDBG_STATE_LVL) << "\n" << vprDEBUG_FLUSH;
   vprASSERT(p == src && "Destination is unreachable from source!");

   std::reverse(vlist->begin(), vlist->end());

   return vlist;
}

NetworkGraph::VertexListPtr vpr::sim::NetworkGraph::reversePath

(

VertexListPtr

path

)

Reverses the given vertex path.

This is basically a way to save computations by reducing the number of calls to getShortestPath(). The result of calling this with a path returned by getShortestPath(u,v) is the same as calling getShortestPath(v,u), but it runs in O(path->size()) time rather than O((V + E) * log V).

Definition at line 325 of file NetworkGraph.cpp.

Referenced by vpr::sim::SocketManager::findRoute().

{
   VertexListPtr new_path(new NetworkGraph::VertexList(path->size()));

   for ( vpr::Uint32 i = path->size(), j = 0; i > 0; i--, ++j )
   {
      (*new_path)[j] = (*path)[i - 1];
   }

   return new_path;
}

vpr::Uint32 vpr::sim::NetworkGraph::getNodeCount

(

)

const [inline]

Returns the current number of nodes in this network.

Definition at line 223 of file NetworkGraph.h.

   {
      return boost::num_vertices(mGraph);
   }

bool vpr::sim::NetworkGraph::isSource	(	const net_vertex_t &	vertex,
		const net_edge_t &	edge
	)			const [inline]

Checks to see if the given vertex is the source of the given edge.

Definition at line 231 of file NetworkGraph.h.

Referenced by vpr::sim::Controller::flushPath(), and vpr::sim::SocketManager::sendMessage().

   {
      NetworkGraph::net_vertex_t source = boost::source(edge, mGraph);

      return vertex == source;
   }

vpr::ReturnStatus vpr::sim::NetworkGraph::getAllAddresses

(

AddressList &

list

)

Returns all the addresses in the network via the by-reference parameter.

Definition at line 337 of file NetworkGraph.cpp.

References getNodeProperty().

{
   vpr::ReturnStatus status;
   boost::graph_traits<net_graph_t>::vertex_iterator vi, vi_end;
   NetworkNodePtr node_prop;

   boost::tie(vi, vi_end) = boost::vertices(mGraph);

   for ( ; vi != vi_end; ++vi )
   {
      node_prop = getNodeProperty(*vi);
      list.push_back(std::pair<net_vertex_t, vpr::Uint32>(*vi,
                                                          node_prop->getIpAddress()));
   }

   return status;
}

---

The documentation for this class was generated from the following files:

• NetworkGraph.h
• NetworkGraph.cpp

---