[Boost-commit] svn:boost r46484 - sandbox/SOC/2008/graphs/trunk/libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-18 12:44:29

Author: asutton
Date: 2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
New Revision: 46484
URL: http://svn.boost.org/trac/boost/changeset/46484

Log:
Initial implementation of the vertex map. Cleaned up and mostly finished
implementations of other vertex stores (excluding the vector for now). This
basically includes fixing and propagating find functions. Started playing
with static asserts.

Need to explicitly wrap vertex descriptors to help get away from weird
overloading problems.

Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test.hpp   (contents, props changed)
Removed:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile |     2 ++                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp  |     6 ++++--                                  
   sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp  |     4 +---                                    
   3 files changed, 7 insertions(+), 5 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
@@ -1,3 +1,5 @@
 
 exe un : un.cpp : <include>../../ <include>/usr/local/include ;
 exe di : di.cpp : <include>../../ <include>/usr/local/include ;
+exe set : set.cpp : <include>../../ <include>/usr/local/include ;
+exe map : map.cpp : <include>../../ <include>/usr/local/include ;

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp	2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
@@ -3,13 +3,15 @@
 
 #include <boost/graphs/directed_graph.hpp>
 
+#include "test.hpp"
+
 using namespace std;
 using namespace boost;
-namespace d = directed;
+
 
 int main()
 {
-    typedef directed_graph<int, int, vertex_vector, d::edge_vector> Graph;
+    typedef directed_graph<int, int, vertex_vector, edge_vector> Graph;
     Graph g;
 
     return 0;

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp	2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
@@ -0,0 +1,22 @@
+
+#include <iostream>
+
+#include <boost/graphs/undirected_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+int main()
+{
+    typedef undirected_graph<int, none, vertex_map<string>, edge_set<> > Graph;
+    Graph g;
+    g.add_vertex("Jan", 1);
+    g.add_vertex("Feb", 2);
+    g.add_vertex("Mar", 3);
+    g.add_vertex("Apr", 4);
+    g.add_vertex("May", 5);
+
+    g.remove_vertex("Mar");
+
+    cout << g[g.find_vertex("Apr")] << endl;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp	2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
@@ -0,0 +1,91 @@
+
+#include <iostream>
+
+#include <boost/graphs/undirected_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+/**
+ * Dumb type that will cause common functions like std::less and std::greater
+ * to call the custom operators.
+ */
+struct Vertex
+{
+    Vertex(int x)
+        : value(x)
+    { }
+
+    int value;
+
+    inline bool operator<(Vertex const& x) const
+    {
+        cout << "    op< " << value << " " << x.value << endl;
+        return value < x.value;
+    }
+
+    inline bool operator>(Vertex const& x) const
+    {
+        cout << "    op> " << value << " " << x.value << endl;
+        return value > x.value;
+    }
+};
+
+template <typename Props>
+struct custom
+{
+    bool operator()(Props const& a, Props const& b) const
+    {
+        cout << "    custom " << a.value << " " << b.value << endl;
+        return a.value < b.value;
+    }
+};
+
+template <typename>
+struct non_template
+{
+    bool operator()(Vertex const& a, Vertex const& b) const
+    {
+        cout << "    custom " << a.value << " " << b.value << endl;
+        return a.value < b.value;
+    }
+};
+
+template <template <typename> class Compare>
+void test()
+{
+    typedef undirected_graph<Vertex, int, vertex_set<Compare>, edge_set<> > Graph;
+    Graph g;
+    cout << "inserting 1" << endl;
+    g.add_vertex(1);
+    cout << "inserting 2" << endl;
+    g.add_vertex(2);
+}
+
+void comps()
+{
+    cout << "LESS" << endl;
+    test<less>();
+
+    cout << "GREATER" << endl;
+    test<greater>();
+
+    cout << "CUSTOM" << endl;
+    test<custom>();
+
+    cout << "NON-TEMPLATE" << endl;
+    test<non_template>();
+}
+
+int main()
+{
+    typedef undirected_graph<string, none, vertex_set<>, edge_set<> > Graph;
+    Graph g;
+    g.add_vertex("Jan");
+    cout << g[g.find_vertex("Jan")] << endl;
+
+    typedef undirected_graph<none, int, vertex_list, edge_list> Tmp;
+    Tmp f;
+    f.remove_vertex(0);
+}
+

Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp	2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
+++ (empty file)
@@ -1,13 +0,0 @@
-
-#include <list>
-
-using namespace std;
-
-int main()
-{
-    list<int> a;
-    list<int>::iterator x = a.begin(), y = a.end();
-    // x < y;
-    return 0;
-}
-

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test.hpp	2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
@@ -0,0 +1,49 @@
+
+#ifndef TEST_HPP
+#define TEST_HPP
+
+#include <list>
+#include <set>
+
+template <typename Graph>
+void test_add_vertices()
+{
+    Graph g;
+    std::list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+}
+
+template <typename Graph>
+void test_add_remove_vertices()
+{
+    Graph g;
+    std::list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    BOOST_ASSERT(g.num_vertices() == 5);
+    while(!V.empty()) {
+        g.remove_vertex(V.front());
+        V.pop_front();
+    }
+    BOOST_ASSERT(g.num_vertices() == 0);
+}
+
+template <typename Graph>
+void test_make_simple_triangle()
+{
+    Graph g;
+    std::vector<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+}
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	2008-06-18 12:44:28 EDT (Wed, 18 Jun 2008)
@@ -11,8 +11,6 @@
 using namespace std;
 using namespace boost;
 
-namespace u = undirected;
-
 typedef int City;
 typedef int Road;
 
@@ -84,7 +82,7 @@
 
 void vec_vec()
 {
-    typedef undirected_graph<City, Road, vertex_vector, u::edge_vector> Graph;
+    typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
     test_add_vertices<Graph>();
     test_make_simple_triangle<Graph>();
 }