Changeset 3a5c19

Timestamp:

12/03/08 16:26:18 (4 years ago)

Author:

Tiago de Paula Peixoto <tiago@…>

Branches:

master, python3

Children:

8cd708

Parents:

7cdf96

git-author:

Tiago de Paula Peixoto <tiago@…> (12/02/08 00:19:07)

git-committer:

Tiago de Paula Peixoto <tiago@…> (12/03/08 16:26:18)

Message:

Re-implement community graph calculation

Location:

src

Files:

• graph/community/Makefile.am (modified) (1 diff)
• graph/community/graph_community.cc (modified) (1 diff)
• graph/community/graph_community_network.cc (modified) (2 diffs)
• graph/community/graph_community_network.hh (modified) (2 diffs)
• graph_tool/community/__init__.py (modified) (2 diffs)

src/graph/community/Makefile.am

@@ -16 +16 @@
 
 libgraph_tool_community_la_SOURCES = \
-    graph_community.cc
+    graph_community.cc \
+    graph_community_network.cc

src/graph/community/graph_community.cc

@@ -113 +113 @@
 using namespace boost::python;
 
+
+extern void community_network(GraphInterface& gi, GraphInterface& cgi,
+                              boost::any community_property,
+                              boost::any vertex_count,
+                              boost::any edge_count, boost::any weight);
+
 BOOST_PYTHON_MODULE(libgraph_tool_community)
 {
     def("community_structure", &community_structure);
     def("modularity", &modularity);
+    def("community_network", &community_network);
 }

src/graph/community/graph_community_network.cc

@@ -16 +16 @@
 // along with this program. If not, see <http://www.gnu.org/licenses/>.
 
-
 #include "graph_filtering.hh"
 #include "graph.hh"
-#include "histogram.hh"
 #include "graph_selectors.hh"
 #include "graph_properties.hh"
 
-
-#include <boost/lambda/bind.hpp>
-#include <tr1/unordered_set>
-#include <iostream>
-#include <iomanip>
+//#include <boost/lambda/bind.hpp>
+#include <boost/bind.hpp>
+#include <boost/bind/placeholders.hpp>
+#include <boost/mpl/push_back.hpp>
+#include <boost/python.hpp>
 
 #include "graph_community_network.hh"
@@ -33 +31 @@
 using namespace std;
 using namespace boost;
-using namespace boost::lambda;
+
 using namespace graph_tool;
 
-void GraphInterface::GetCommunityNetwork(string property, string size_property,
-                                         string out_file, string format) const
+
+void community_network(GraphInterface& gi, GraphInterface& cgi,
+                       boost::any community_property, boost::any vertex_count,
+                       boost::any edge_count, boost::any weight)
 {
+    // using boost::lambda::bind;
+    // using boost::lambda::_1;
+    // using boost::lambda::_2;
+    // using boost::lambda::_3;
+    // using boost::lambda::_4;
+
+    typedef DynamicPropertyMapWrap<double,GraphInterface::edge_t> weight_map_t;
+    typedef ConstantPropertyMap<double,GraphInterface::edge_t> no_weight_map_t;
+    typedef mpl::vector<weight_map_t,no_weight_map_t> weight_properties;
+
+    if (weight.empty())
+        weight = no_weight_map_t(1.0);
+    else
+        weight = weight_map_t(weight, edge_scalar_properties());
+
+    typedef vector_property_map<int32_t,GraphInterface::vertex_index_map_t>
+        vcount_t;
+    vcount_t vcount(gi.GetVertexIndex());
     try
     {
-        boost::any vertex_prop = prop(property, _vertex_index, _properties);
+        vcount = any_cast<vcount_t>(vertex_count);
+    }
+    catch (bad_any_cast&)
+    {
+        throw GraphException("invalid vertex count property");
+    }
 
-        dynamic_properties_copy edge_properties;
-        for (typeof(_properties.begin()) iter = _properties.begin();
-             iter != _properties.end(); ++iter)
-            if (iter->second->key() == typeid(edge_t))
-                edge_properties.insert(iter->first,
-                                       auto_ptr<dynamic_property_map>
-                                           (iter->second));
+    typedef property_map_types::apply<mpl::vector<int32_t,double>,
+                                      GraphInterface::edge_index_map_t,
+                                      mpl::bool_<false> >::type
+        ecount_properties;
 
-        run_action<>()(*this,
-                       bind<void>(get_community_network(), _1, _2, property,
-                                  size_property, var(edge_properties),
-                                  out_file, format), vertex_scalar_properties())
-            (vertex_prop);
-    }
-    catch (property_not_found)
-    {
-        throw GraphException("edge property " + property + " not found");
-    }
+    if (!belongs<ecount_properties>()(edge_count))
+        throw GraphException("invalid edge count property");
+
+     run_action<>()(gi, bind<void>(get_community_network(), _1,
+                                          &cgi.GetGraph(), cgi.GetVertexIndex(),
+                                          cgi.GetEdgeIndex(), _2,
+                                          _3, vcount, _4),
+                   vertex_properties(), weight_properties(),
+                   ecount_properties())
+        (community_property, weight, edge_count);
 }

src/graph/community/graph_community_network.hh

@@ -23 +23 @@
 #include <iomanip>
 
-#include <boost/graph/graphviz.hpp>
-#include <boost/graph/graphml.hpp>
-#include <boost/algorithm/string.hpp>
-#include <boost/iostreams/filtering_stream.hpp>
-#include <boost/iostreams/filter/gzip.hpp>
-#include <boost/iostreams/filter/bzip2.hpp>
-#include <boost/iostreams/device/file.hpp>
-
 namespace graph_tool
 {
@@ -41 +33 @@
 struct get_community_network
 {
-    template <class Graph, class CommunityMap>
-    void operator()(const Graph* gp, CommunityMap s, string property,
-                    string size_property, dynamic_properties& edge_properties,
-                    string file, string format) const
+    template <class Graph, class CommunityGraph, class CommunityMap,
+              class WeightMap, class EdgeIndex, class VertexIndex,
+              class VertexProperty, class EdgeProperty>
+    void operator()(const Graph* gp, CommunityGraph* cgp,
+                    VertexIndex cvertex_index, EdgeIndex cedge_index,
+                    CommunityMap s_map, WeightMap weight,
+                    VertexProperty vertex_count, EdgeProperty edge_count) const
     {
         const Graph& g = *gp;
+        CommunityGraph& cg = *cgp;
 
         typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
         typedef typename graph_traits<Graph>::edge_descriptor edge_t;
+        typedef typename graph_traits<CommunityGraph>::vertex_descriptor
+            cvertex_t;
+        typedef typename graph_traits<CommunityGraph>::edge_descriptor
+            cedge_t;
+        typedef typename boost::property_traits<CommunityMap>::value_type
+            s_type;
 
-        tr1::unordered_map
-            <typename boost::property_traits<CommunityMap>::value_type, size_t>
+        tr1::unordered_map<s_type, vector<vertex_t>, boost::hash<s_type> >
             comms;
-
         typename graph_traits<Graph>::vertex_iterator v, v_end;
         for (tie(v, v_end) = vertices(g); v != v_end; ++v)
-            comms[get(s, *v)]++;
+            comms[get(s_map, *v)].push_back(*v);
 
-        typedef boost::property<edge_index_t, size_t> EdgeProperty;
-
-        typedef typename graph_traits<Graph>::directed_category
-            directed_category;
-        typedef typename mpl::if_<typename is_convertible<directed_category,
-                                                          directed_tag>::type,
-                                  bidirectionalS,
-                                  undirectedS>::type directed_selector;
-
-        typedef adjacency_list <vecS, // edges
-                                vecS, // vertices
-                                directed_selector,
-                                no_property,
-                                EdgeProperty > comm_graph_t;
-
-        comm_graph_t comm_graph;
-
-        typedef typename property_map<comm_graph_t, vertex_index_t>::type
-            comm_vertex_index_map_t;
-        comm_vertex_index_map_t
-            comm_vertex_index(get(vertex_index, comm_graph));
-
-        vector_property_map<typename property_traits<CommunityMap>::value_type,
-                            comm_vertex_index_map_t>
-            comm_map(comm_vertex_index);
-        vector_property_map<size_t, comm_vertex_index_map_t>
-            comm_size_map(comm_vertex_index);
-        tr1::unordered_map
-            <typename property_traits<CommunityMap>::value_type,
-            typename graph_traits<comm_graph_t>::vertex_descriptor>
-            comm_vertex_map;
+        // create vertices
+        tr1::unordered_map<s_type, cvertex_t, boost::hash<s_type> >
+            comm_vertices;
         for (typeof(comms.begin()) iter = comms.begin(); iter != comms.end();
              ++iter)
         {
-            comm_vertex_map[iter->first] = add_vertex(comm_graph);
-            comm_map[comm_vertex_map[iter->first]] = iter->first;
-            if (size_property != "")
-                comm_size_map[comm_vertex_map[iter->first]] = iter->second;
+            cvertex_t v = add_vertex(cg);
+            vertex_count[v] = iter->second.size();
+            comm_vertices[iter->first] = v;
         }
 
-        dynamic_properties dp;
-        dp.property(property, comm_map);
-        if (size_property != "")
-            dp.property(size_property, comm_size_map);
+        // create edges
+        tr1::unordered_map<pair<size_t, size_t>,
+                           cedge_t, boost::hash<pair<size_t, size_t> > >
+            comm_edges;
+        for (typeof(comms.begin()) iter = comms.begin(); iter != comms.end();
+             ++iter)
+        {
 
-        typedef typename property_map<comm_graph_t,edge_index_t>::type
-            comm_edge_index_map_t;
-        comm_edge_index_map_t comm_edge_index(get(edge_index_t(), comm_graph));
-
-        typedef HashedDescriptorMap<comm_edge_index_map_t, edge_t> edge_map_t;
-        edge_map_t edge_map(comm_edge_index);
-
-        size_t e_index = 0;
-        typename graph_traits<Graph>::edge_iterator e, e_end;
-        for (tie(e, e_end) = edges(g); e != e_end; ++e)
-        {
-            typename graph_traits<comm_graph_t>::edge_descriptor edge;
-            edge  = add_edge(comm_vertex_map[get(s,source(*e, g))],
-                             comm_vertex_map[get(s,target(*e, g))],
-                             comm_graph).first;
-            edge_map[edge] = *e;
-            comm_edge_index[edge] = e_index++;
-        }
-
-        for (typeof(edge_properties.begin()) iter = edge_properties.begin();
-             iter != edge_properties.end(); ++iter)
-            dp.insert(iter->first,
-                      auto_ptr<dynamic_property_map>
-                          (new dynamic_property_map_wrap<edge_map_t>
-                           (edge_map, *iter->second)));
-
-        bool graphviz = false;
-        if (format == "")
-            graphviz = ends_with(file,".dot") || ends_with(file,".dot.gz") ||
-                ends_with(file,".dot.bz2");
-        else if (format == "dot")
-            graphviz = true;
-        else if (format != "xml")
-            throw GraphException("error writing to file '" + file +
-                                 "': requested invalid format '" +
-                                 format + "'");
-        try
-        {
-            iostreams::filtering_stream<iostreams::output> stream;
-            ofstream file_stream;
-            if (file == "-")
-                stream.push(cout);
-            else
+            cvertex_t cs = comm_vertices[iter->first];
+            for (size_t i = 0; i < iter->second.size(); ++i)
             {
-                file_stream.open(file.c_str(), ios_base::out |
-                                 ios_base::binary);
-                file_stream.exceptions(ios_base::badbit | ios_base::failbit);
-                if (ends_with(file,".gz"))
-                    stream.push(iostreams::gzip_compressor());
-                if (ends_with(file,".bz2"))
-                    stream.push(iostreams::bzip2_compressor());
-                stream.push(file_stream);
+                vertex_t s = iter->second[i];
+                typename graph_traits<Graph>::out_edge_iterator e, e_end;
+                for (tie(e, e_end) = out_edges(s, g); e != e_end; ++e)
+                {
+                    vertex_t t = target(*e, g);
+                    cvertex_t ct = comm_vertices[get(s_map, t)];
+                    if (ct == cs) // self-loops are pointless
+                        continue;
+                    cedge_t ce;
+                    if (comm_edges.find(make_pair(cs, ct)) != comm_edges.end())
+                        ce = comm_edges[make_pair(cs, ct)];
+                    else if (!is_directed::apply<Graph>::type::value &&
+                             comm_edges.find(make_pair(ct, cs)) != comm_edges.end())
+                        ce = comm_edges[make_pair(ct, cs)];
+                    else
+                    {
+                        ce = add_edge(cs,ct,cg).first;
+                        comm_edges[make_pair(cs, ct)] = ce;
+                    }
+                    edge_count[ce] += get(weight, *e);
+                }
             }
-            stream.exceptions(ios_base::badbit | ios_base::failbit);
-
-            if (graphviz)
-            {
-                dp.property("vertex_id", comm_vertex_index);
-                write_graphviz(stream, comm_graph, dp, string("vertex_id"));
-            }
-            else
-            {
-                write_graphml(stream, comm_graph, comm_vertex_index, dp, true);
-            }
-            stream.reset();
-        }
-        catch (ios_base::failure &e)
-        {
-            throw GraphException("error writing to file '" + file + "':" +
-                                 e.what());
         }
     }
-
-    template <class EdgeMap>
-    class dynamic_property_map_wrap: public dynamic_property_map
-    {
-    public:
-        dynamic_property_map_wrap(EdgeMap& edge_map, dynamic_property_map& dm):
-            _edge_map(edge_map), _dm(dm) {}
-        any get(const any& key)
-        {
-            return _dm.get(_edge_map[any_cast<key_t>(key)]);
-        }
-
-        string get_string(const any& key)
-        {
-            return _dm.get_string(_edge_map[any_cast<key_t>(key)]);
-        }
-
-        void put(const any& key, const any& value)
-        {
-            return _dm.put(_edge_map[any_cast<key_t>(key)], value);
-        }
-
-        const type_info& key() const
-        {
-            return typeid(key_t);
-        }
-
-        const type_info& value() const
-        {
-            return _dm.value();
-        }
-    private:
-        EdgeMap& _edge_map;
-        typedef typename property_traits<EdgeMap>::key_type key_t;
-        dynamic_property_map& _dm;
-    };
-
 };
 

src/graph_tool/community/__init__.py

@@ -20 +20 @@
 dl_import("import libgraph_tool_community")
 
-from .. core import _degree, _prop
+from .. core import _degree, _prop, Graph, libcore
 import random, sys
 
-__all__ = ["community_structure", "modularity"]
+__all__ = ["community_structure", "modularity", "community_network"]
 
 
@@ -47 +47 @@
     c = libgraph_tool_clustering.global_clustering(g._Graph__graph)
     return c
+
+def community_network(g, prop, weight=None):
+    gp = Graph()
+    vcount = g.new_vertex_property("int32_t")
+    if weight != None:
+        ecount = g.new_edge_property("double")
+        weight = _prop("e", g, weight)
+    else:
+        ecount = g.new_edge_property("int32_t")
+        weight = libcore.any()
+    libgraph_tool_community.community_network(g._Graph__graph,
+                                              gp._Graph__graph,
+                                              _prop("v", g, prop),
+                                              _prop("v", g, vcount),
+                                              _prop("e", g, ecount),
+                                              weight)
+    return gp, vcount, ecount
+