Changeset ba2aee

Timestamp:

06/30/07 23:39:31 (6 years ago)

Author:

Tiago de Paula Peixoto <tiago@…>

Branches:

master, python3

Children:

0075ec

Parents:

d199d4

git-author:

Tiago de Paula Peixoto <tiago@…> (06/30/07 23:39:31)

git-committer:

Tiago de Paula Peixoto <tiago@…> (06/30/07 23:39:31)

Message:

* add support for betweenness centrality 
* change from HashedDescriptorMap to vector_property_map in several
  algorithms to save memory and increase speed in the most common
  case, where the graph is unfiltered.




git-svn-id: https://svn.forked.de/graph-tool/trunk@102 d4600afd-f417-0410-95de-beed9576f240

Location:

src

Files:

• boost-workaround/boost/graph/betweenness_centrality.hpp (added)
• graph-tool (modified) (3 diffs)
• graph/Makefile.am (modified) (1 diff)
• graph/graph.hh (modified) (1 diff)
• graph/graph_adaptor.hh (modified) (1 diff)
• graph/graph_betweenness.cc (added)
• graph/graph_bind.cc (modified) (1 diff)
• graph/graph_clustering.cc (modified) (1 diff)
• graph/graph_community.cc (modified) (1 diff)
• graph/graph_extended_clustering.cc (modified) (1 diff)
• graph/graph_filtering.hh (modified) (2 diffs)
• graph/graph_io.cc (modified) (1 diff)
• graph/graph_minimum_spanning_tree.cc (modified) (1 diff)
• graph/graph_properties.cc (modified) (1 diff)
• graph/graph_properties.hh (modified) (1 diff)

src/graph-tool

@@ -1 +1 @@
 #! /usr/bin/env python
+# graph-tool -- a general graph modification and manipulation thingy
+#
 # Copyright (C) 2007 Tiago de Paula Peixoto <tiago@forked.de>
 #
@@ -112 +114 @@
 statistics.add_option("--minimum-spanning-tree", action="callback", callback=push_option, type="string", metavar="[WEIGHT|]PROPERTY", help="mark the minimum spanning tree edges in PROPERTY")
 statistics.add_option("--line-graph", action="callback", callback=push_option, type="string", metavar="FILE[|FORMAT]", help="save the corresponding line graph to FILE")
+statistics.add_option("--betweenness-centrality", action="callback", callback=push_option, type="string", metavar="VERTEX_BETWEENESS[EDGE_BETWEENESS]", help="calculate and store the vertex and/or edge betweenness centrality")
 
 correlations =  parser.add_option_group("Correlations")
@@ -504 +507 @@
             format = ""
         graph.GetLineGraph(values[0], format)
+    elif opt.name == "betweenness-centrality":
+        values = parse_values(opt.value)
+        if len(values) < 1 or len(values) > 3:
+            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
+        if just_file:
+            return None
+        vertex_centrality = values[0]
+        if len(values) > 1:
+            edge_centrality = values[1]
+        else:
+            edge_centrality = ""
+        if len(values) > 2:
+            weight = values[2]
+        else:
+            weight = ""
+        graph.GetBetweenness(weight, vertex_centrality, edge_centrality)
     elif opt.name == "vertex-correlation-histogram":
         values = parse_values(opt.value)

src/graph/Makefile.am

@@ -41 +41 @@
     graph_community_network.cc\
     graph_line_graph.cc\
+    graph_betweenness.cc\
     graph_io.cc\
     graph_bind.cc\

src/graph/graph.hh

@@ -98 +98 @@
     void   GetMinimumSpanningTree(std::string weight, std::string property);
     void   GetLineGraph(std::string out_file, std::string format);
+    void   GetBetweenness(std::string weight, std::string edge_betweenness, std::string vertex_betweenness);
 
     // community structure

src/graph/graph_adaptor.hh

@@ -358 +358 @@
 };
 
+template <class Graph>
+struct graph_traits< const UndirectedAdaptor<Graph> >: public graph_traits< UndirectedAdaptor<Graph> > {};
+
 //==============================================================================
 // Nonmember functions

src/graph/graph_bind.cc

@@ -240 +240 @@
         .def("GetMinimumSpanningTree", &GraphInterfaceWrap::GetMinimumSpanningTree)
         .def("GetLineGraph", &GraphInterfaceWrap::GetLineGraph)
+        .def("GetBetweenness", &GraphInterfaceWrap::GetBetweenness)
         .def("GetCommunityStructure", &GraphInterfaceWrap::GetCommunityStructure)
         .def("GetCommunityNetwork", &GraphInterfaceWrap::GetCommunityNetwork)

src/graph/graph_clustering.cc

@@ -198 +198 @@
 void GraphInterface::SetLocalClusteringToProperty(string property)
 {
-    typedef HashedDescriptorMap<vertex_index_map_t,double> clust_map_t;
+    typedef vector_property_map<double,vertex_index_map_t> clust_map_t;
     clust_map_t clust_map(_vertex_index);
 

src/graph/graph_community.cc

@@ -652 +652 @@
 void GraphInterface::GetCommunityStructure(double gamma, comm_corr_t corr, size_t n_iter, double Tmin, double Tmax, size_t Nspins, size_t seed, bool verbose, string history_file, string weight, string property)
 {
-    typedef HashedDescriptorMap<vertex_index_map_t,size_t> comm_map_t;
+    typedef vector_property_map<size_t,vertex_index_map_t> comm_map_t;
     comm_map_t comm_map(_vertex_index);
 

src/graph/graph_extended_clustering.cc

@@ -159 +159 @@
 void GraphInterface::SetExtendedClusteringToProperty(string property_prefix, size_t max_depth)
 {
-    typedef HashedDescriptorMap<vertex_index_map_t,double> cmap_t;
+    typedef vector_property_map<double, vertex_index_map_t> cmap_t;
     vector<cmap_t> cmaps(max_depth);
     for (size_t i = 0; i < cmaps.size(); ++i)

src/graph/graph_filtering.hh

@@ -41 +41 @@
 #endif
 
+// some additional functions...
+namespace boost
+{
+//==============================================================================
+// vertex(i, filtered_graph<G>)
+//==============================================================================
+template <class Graph, class EdgePredicate, class VertexPredicate> 
+typename graph_traits<filtered_graph<Graph,EdgePredicate,VertexPredicate> >::vertex_descriptor
+vertex(size_t i, const filtered_graph<Graph,EdgePredicate,VertexPredicate>& g)
+{
+    typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g.m_g);
+    if (g.m_vertex_pred(v))
+        return v;
+    else
+        return graph_traits<Graph>::null_vertex();
+}
+
+//==============================================================================
+// vertex(i, reverse_graph<G>)
+//==============================================================================
+template <class Graph> 
+typename graph_traits<reverse_graph<Graph> >::vertex_descriptor
+vertex(size_t i, const reverse_graph<Graph>& g)
+{
+    return vertex(i, g.m_g);
+}
+
+} // namespace boost
+
+
 namespace graph_tool
 {
@@ -97 +127 @@
 };
 
-
-//==============================================================================
-// vertex(i, filtered_graph<G>)
-//==============================================================================
-template <class Graph, class EdgePredicate, class VertexPredicate> 
-typename graph_traits<filtered_graph<Graph,EdgePredicate,VertexPredicate> >::vertex_descriptor
-vertex(size_t i, const filtered_graph<Graph,EdgePredicate,VertexPredicate>& g)
-{
-    typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g.m_g);
-    if (g.m_vertex_pred(v))
-        return v;
-    else
-        return graph_traits<Graph>::null_vertex();
-}
-
-//==============================================================================
-// vertex(i, reverse_graph<G>)
-//==============================================================================
-template <class Graph> 
-typename graph_traits<reverse_graph<Graph> >::vertex_descriptor
-vertex(size_t i, const reverse_graph<Graph>& g)
-{
-    return vertex(i, g.m_g);
-}
-
-
 //==============================================================================
 // RangeFilter

src/graph/graph_io.cc

@@ -67 +67 @@
 //==============================================================================
 
-typedef mpl::vector<bool, int, long, float, double, string> value_types;
-
 template <class VertexIndexMap, class EdgeIndexMap>
 struct create_dynamic_map

src/graph/graph_minimum_spanning_tree.cc

@@ -56 +56 @@
 void GraphInterface::GetMinimumSpanningTree(string weight, string property)
 {
-    typedef HashedDescriptorMap<edge_index_map_t,size_t> tree_map_t;
+    typedef vector_property_map<size_t, edge_index_map_t> tree_map_t;
     tree_map_t tree_map(_edge_index);
 

src/graph/graph_properties.cc

@@ -35 +35 @@
 using namespace graph_tool;
 
-typedef mpl::vector<bool, int, long, size_t, float, double, std::string> value_types;
+namespace graph_tool
+{
+// global property types
 const char* type_names[] = {"boolean", "int", "long", "long", "float", "double", "string"};
 
+// scalar types
+const char* scalar_names[] = {"boolean", "int", "long", "long", "float", "double"};
+}
 
 //==============================================================================

src/graph/graph_properties.hh

@@ -32 +32 @@
 {
 
+// global property types
+typedef boost::mpl::vector<bool, int, long, size_t, float, double, std::string> value_types;
+extern const char* type_names[];
+
+// scalar types
+typedef boost::mpl::vector<bool, int, long, size_t, float, double> scalar_types;
+extern const char* scalar_names[];
+
+
+
 //==============================================================================
 // Property Map Utility Functions