[Avida-SVN] r1527 - in branches/dkdev/source: actions cpu main
dknoester at myxo.css.msu.edu
dknoester at myxo.css.msu.edu
Fri May 4 12:47:55 PDT 2007
Author: dknoester
Date: 2007-05-04 15:47:55 -0400 (Fri, 04 May 2007)
New Revision: 1527
Modified:
branches/dkdev/source/actions/PopulationActions.cc
branches/dkdev/source/cpu/cHardwareCPU.cc
branches/dkdev/source/main/cDeme.h
branches/dkdev/source/main/cPopulation.cc
branches/dkdev/source/main/cStats.cc
branches/dkdev/source/main/cStats.h
Log:
Added new ReplicateDemes event for small diameter networks.
Modified: branches/dkdev/source/actions/PopulationActions.cc
===================================================================
--- branches/dkdev/source/actions/PopulationActions.cc 2007-05-04 01:18:34 UTC (rev 1526)
+++ branches/dkdev/source/actions/PopulationActions.cc 2007-05-04 19:47:55 UTC (rev 1527)
@@ -893,7 +893,8 @@
else if (in_trigger == "full_deme") m_rep_trigger = 1;
else if (in_trigger == "corners") m_rep_trigger = 2;
else if (in_trigger == "topo-connected") m_rep_trigger = 3;
- else if (in_trigger == "deme-age") m_rep_trigger = 4;
+ else if (in_trigger == "deme-age") m_rep_trigger = 4;
+ else if (in_trigger == "min-diameter") m_rep_trigger = 5;
else {
cString err("Unknown replication trigger '");
err += in_trigger;
Modified: branches/dkdev/source/cpu/cHardwareCPU.cc
===================================================================
--- branches/dkdev/source/cpu/cHardwareCPU.cc 2007-05-04 01:18:34 UTC (rev 1526)
+++ branches/dkdev/source/cpu/cHardwareCPU.cc 2007-05-04 19:47:55 UTC (rev 1527)
@@ -3539,15 +3539,15 @@
// What is the cell that we're trying to connect to?
int connectTo=0;
// First, do we have a label?
- if(GetLabel().GetSize()) {
- // Yes; get the cell to connect to from the register.
- connectTo = GetRegister(FindModifiedRegister(REG_BX));
- // Now, if this isn't a valid cell ID, fail.
- if(!deme.IsCellID(connectTo)) return false;
- } else {
+// if(GetLabel().GetSize()) {
+// // Yes; get the cell to connect to from the register.
+// connectTo = GetRegister(FindModifiedRegister(REG_BX));
+// // Now, if this isn't a valid cell ID, fail.
+// if(!deme.IsCellID(connectTo)) return false;
+// } else {
// No; get the cell to connect to from our facing.
connectTo = cell.ConnectionList().GetFirst()->GetID();
- }
+// }
// Now, are this cell and the cell we're connecting to in the network? If no,
// add them; if yes, then get a ref to the vertex descriptors.
Modified: branches/dkdev/source/main/cDeme.h
===================================================================
--- branches/dkdev/source/main/cDeme.h 2007-05-04 01:18:34 UTC (rev 1526)
+++ branches/dkdev/source/main/cDeme.h 2007-05-04 19:47:55 UTC (rev 1527)
@@ -15,6 +15,8 @@
#define cDeme_h
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/visitors.hpp>
#include <map>
#include <utility>
@@ -91,4 +93,22 @@
int _age; //!< How old this deme is, in updates.
};
+
+//! A BGL breadth-first visitor to calculate distances between vertices.
+template <class Distance>
+class DistanceVisitor : public boost::bfs_visitor< > {
+public:
+ DistanceVisitor(Distance d) : distance(d) { }
+ template <class Graph>
+ void tree_edge(typename boost::graph_traits<Graph>::edge_descriptor e, Graph& g) {
+ typename boost::graph_traits<Graph>::vertex_descriptor u, v;
+ u = boost::source(e, g);
+ v = boost::target(e, g);
+ distance[v] = distance[u] + 1;
+ }
+
+private:
+ Distance distance;
+};
+
#endif
Modified: branches/dkdev/source/main/cPopulation.cc
===================================================================
--- branches/dkdev/source/main/cPopulation.cc 2007-05-04 01:18:34 UTC (rev 1526)
+++ branches/dkdev/source/main/cPopulation.cc 2007-05-04 19:47:55 UTC (rev 1527)
@@ -890,6 +890,94 @@
if(source_deme.GetAge() < m_world->GetConfig().MAX_DEME_AGE.Get()) continue;
break;
}
+ case 5: {
+ // This flavor of replicate demes rewards for constructing networks with a
+ // small per-node longest shortest-path.
+ //
+ // We check to see if the topology that has been build by this deme:
+ // 1) Contains all vertices.
+ // 2) Is connected.
+ // 3) Has one component.
+ // 4) And then rewards the deme based on how close it is to having the minimum average diameter.
+ cDeme::Network& network = source_deme.GetNetwork();
+
+ // Do we have all the vertices?
+ if(boost::num_vertices(network) != (unsigned int)source_deme.GetSize()) continue;
+
+ // Do we have a connected graph?
+ std::vector<int> components(boost::num_vertices(network));
+ int num_components = boost::connected_components(network, &components[0]);
+ if(num_components > 1) continue;
+
+ // Calculate the shortest distances between all vertices.
+ typedef cDeme::Network::vertices_size_type size_type;
+ typedef std::vector<size_type> DistanceVector;
+ std::vector<DistanceVector> distance_matrix(boost::num_vertices(network),
+ DistanceVector(boost::num_vertices(network), 0));
+ for(size_type i=0; i<boost::num_vertices(network); ++i) {
+ DistanceVisitor<size_type*> visitor(&distance_matrix[i][0]);
+ cDeme::Network::vertex_descriptor src = boost::vertices(network).first[i];
+ boost::breadth_first_search(network, src, boost::visitor(visitor));
+ }
+
+ // Now calculate the mean longest shortest-path from each node.
+ size_type sum_lsp=0;
+ for(size_type i=0; i<boost::num_vertices(network); ++i) {
+ sum_lsp += *std::max_element(distance_matrix[i].begin(), distance_matrix[i].end());
+ }
+ double mean_lsp = (double)sum_lsp / boost::num_vertices(network);
+
+ // Record that it worked.
+ m_world->GetStats().ConnectedTopology(source_deme, mean_lsp);
+
+ // Check to see if we need to update the deme's merit.
+ if(m_world->GetConfig().DEMES_USE_GERMLINE.Get() &&
+ m_world->GetConfig().DEMES_HAVE_MERIT.Get()) {
+ // Source germline:
+ cGermline& source_germline = source_deme.GetGermline();
+
+ // Worst-case mean lsp == 3/4 of a single path.
+ double max_lsp = world_x * world_y/num_demes * 0.75;
+
+ // Quick hack: max# of edges.
+ int max_edges=0;
+ switch(m_world->GetConfig().WORLD_GEOMETRY.Get()) {
+ case nGeometry::GRID: {
+ const int interior_nodes = (world_x-2) * (world_y/num_demes - 2);
+ const int exterior_nodes = source_deme.GetSize() - interior_nodes;
+ // Each interior node has 8 edges.
+ max_edges += interior_nodes * 8;
+ // Each external node (except for corners) has 5 edges.
+ max_edges += (exterior_nodes-4) * 5;
+ // Each corner has 3 edges.
+ max_edges += 12;
+ // And now we've counted each edge twice.
+ max_edges /= 2;
+ break;
+ }
+ case nGeometry::TORUS: {
+ // Each node has 8 edges; avoid double-counting.
+ max_edges = source_deme.GetSize()*4;
+ break;
+ }
+ case nGeometry::CLIQUE: {
+ // Euler's formula.
+ max_edges = source_deme.GetSize()*(source_deme.GetSize()-1)/2;
+ break;
+ }
+ default: {
+ assert(false);
+ break;
+ }
+ }
+
+ // Now, update this deme's merit.
+ source_germline.UpdateMerit(pow(max_lsp - mean_lsp + 1, 2) // This is for mean lsp.
+ + pow(max_edges - boost::num_edges(network) + 1, 2) // This is to reduce edge-count.
+ );
+ }
+ break;
+ }
default:
cerr << "ERROR: Invalid replication trigger " << rep_trigger
<< " in cPopulation::ReplicateDemes()" << endl;
Modified: branches/dkdev/source/main/cStats.cc
===================================================================
--- branches/dkdev/source/main/cStats.cc 2007-05-04 01:18:34 UTC (rev 1526)
+++ branches/dkdev/source/main/cStats.cc 2007-05-04 19:47:55 UTC (rev 1527)
@@ -855,10 +855,11 @@
}
-void cStats::ConnectedTopology(cDeme& deme) {
+void cStats::ConnectedTopology(cDeme& deme, double meanlsp) {
cDeme::Network& network = deme.GetNetwork();
++m_topo_numReplications;
m_topo_numEdges.Add(boost::num_edges(network));
+ m_topo_meanLsp.Add(meanlsp);
m_topo_lastNetwork = network;
m_topo_germline = deme.GetGermline();
}
@@ -884,8 +885,10 @@
df.Write(GetUpdate(), "update" );
df.Write(m_topo_numReplications, "Number of deme replications.");
df.Write(m_topo_numEdges.Average(), "Avg. number of edges on deme replication.");
+ df.Write(m_topo_meanLsp.Average(), "Avg. longest shortest-path.");
m_topo_numReplications = 0;
m_topo_numEdges.Clear();
+ m_topo_meanLsp.Clear();
df.Endl();
if(boost::num_vertices(m_topo_lastNetwork) > 0) {
Modified: branches/dkdev/source/main/cStats.h
===================================================================
--- branches/dkdev/source/main/cStats.h 2007-05-04 01:18:34 UTC (rev 1526)
+++ branches/dkdev/source/main/cStats.h 2007-05-04 19:47:55 UTC (rev 1527)
@@ -204,6 +204,7 @@
int m_topo_numReplications; //!< Number of deme replications since the last stats output.
cDoubleSum m_topo_numEdges; //!< Average number of edges per deme upon replication.
+ cDoubleSum m_topo_meanLsp; //!< Mean longest shortest-path in the network.
cDeme::Network m_topo_lastNetwork; //!< The network resulting from the last replication.
cGermline m_topo_germline; //!< The germline that built the network above.
@@ -551,7 +552,7 @@
void PrintMarketData(const cString& filename);
// Topology
- void ConnectedTopology(cDeme& deme);
+ void ConnectedTopology(cDeme& deme, double meanlsp=0.0);
void PrintTopologyData(const cString& filename);
};
More information about the Avida-cvs
mailing list