Changeset 38738


Ignore:
Timestamp:
Aug 17, 2007, 1:15:11 PM (11 years ago)
Author:
Andrew Sutton
Message:

Rewriting most of the examples

Location:
sandbox/SOC/2007/graphs/libs/graph/examples
Files:
7 edited
1 moved

Legend:

Unmodified
Added
Removed
  • sandbox/SOC/2007/graphs/libs/graph/examples/Jamfile.v2

    r38678 r38738  
    99exe influence_prestige : influence_prestige.cpp ;
    1010exe closeness_centrality : closeness_centrality.cpp ;
    11 exe norm_closeness_centrality : norm_closeness_centrality.cpp ;
     11exe scaled_closeness_centrality : scaled_closeness_centrality.cpp ;
    1212exe mean_geodesic : mean_geodesic.cpp ;
    1313exe eccentricity : eccentricity.cpp ;
  • sandbox/SOC/2007/graphs/libs/graph/examples/closeness_centrality.cpp

    r38678 r38738  
    55// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
    66
    7 #include "social_network.hpp"
    8 #include "helper.hpp"
    9 
     7//[closeness_centrality_example
    108#include <iostream>
    119#include <iomanip>
     10
     11#include <boost/graph/undirected_graph.hpp>
     12#include <boost/graph/exterior_property.hpp>
     13#include <boost/graph/constant_property_map.hpp>
    1214#include <boost/graph/floyd_warshall_shortest.hpp>
    1315#include <boost/graph/closeness_centrality.hpp>
     16#include "helper.hpp"
    1417
    1518using namespace std;
    1619using namespace boost;
    1720
     21// The Actor type stores the name of each vertex in the graph.
     22struct Actor
     23{
     24    std::string name;
     25};
     26
     27// Declare the graph type and its vertex and edge types.
     28typedef undirected_graph<Actor> Graph;
     29typedef graph_traits<Graph>::vertex_descriptor Vertex;
     30typedef graph_traits<Graph>::edge_descriptor Edge;
     31
     32// Declare a matrix type and its corresponding property map that
     33// will contain the distances between each pair of vertices.
     34typedef exterior_vertex_property<Graph, int> DistanceProperty;
     35typedef DistanceProperty::matrix_type DistanceMatrix;
     36typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
     37
     38// Declare the weight map so that each edge returns the same value.
     39typedef constant_property_map<Edge, int> WeightMap;
     40
     41// Declare a container and its corresponding property map that
     42// will contain the resulting closeness centralities of each
     43// vertex in the graph.
     44typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
     45typedef ClosenessProperty::container_type ClosenessContainer;
     46typedef ClosenessProperty::map_type ClosenessMap;
     47
    1848int
    1949main(int argc, char *argv[])
    2050{
     51    // Create the graph and read it from standard input.
    2152    Graph g;
    22     map<string, Vertex> verts;
     53    read_graph(g, cin);
    2354
    24     // Read in and build the graph
    25     for(string line; getline(cin, line); ) {
    26         if(line.empty()) continue;
    27         size_t index = line.find_first_of(',');
    28         string first(line, 0, index);
    29         string second(line, index + 1);
    30 
    31         Vertex u = add_named_vertex(g, first, verts);
    32         Vertex v = add_named_vertex(g, second, verts);
    33         add_edge(u, v, g);
    34     }
    35 
    36     //[compute_constant_distances
     55    // Compute the distances between all pairs of vertices using
     56    // the Floyd-Warshall algorithm. Note that the weight map is
     57    // created so that every edge has a weight of 1.
    3758    DistanceMatrix distances(num_vertices(g));
    3859    DistanceMatrixMap dm(distances, g);
    3960    WeightMap wm(1);
    4061    floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
    41     //]
    4262
    4363    // Compute the degree centrality for graph
    44     //[compute_closeness_centrality
    4564    ClosenessContainer cents(num_vertices(g));
    4665    ClosenessMap cm(cents, g);
    4766    closeness_centrality(g, dm, cm);
    48     //]
    4967
    50     //[closeness_sort_vertices
    51     vector<Vertex> sorted(num_vertices(g));
    52     sort_vertices(sorted, g, cm);
    53     //]
    54 
    55     // Print the degree centrality of each vertex
    56     //[print_sorted_closeness
    57     vector<Vertex>::iterator i, end = sorted.end();
    58     for(i = sorted.begin(); i != end; ++i) {
     68    // Print the closeness centrality of each vertex.
     69    graph_traits<Graph>::vertex_iterator i, end;
     70    for(tie(i, end) = vertices(g); i != end; ++i) {
    5971        cout << setw(12) << setiosflags(ios::left)
    60              << g[*i].name << cm[*i] << "\n";
     72             << g[*i].name << get(cm, *i) << endl;
    6173    }
    62     //]
    6374
    6475    return 0;
    6576}
     77//]
  • sandbox/SOC/2007/graphs/libs/graph/examples/degree_centrality.cpp

    r38621 r38738  
    55// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
    66
    7 #include "social_network.hpp"
    8 #include "helper.hpp"
    97
     8//[degree_centrality_example
    109#include <iostream>
    1110#include <iomanip>
    1211
     12#include <boost/graph/undirected_graph.hpp>
     13#include <boost/graph/exterior_property.hpp>
    1314#include <boost/graph/degree_centrality.hpp>
     15
     16#include "helper.hpp"
    1417
    1518using namespace std;
    1619using namespace boost;
    1720
     21// The Actor type stores the name of each vertex in the graph.
     22struct Actor
     23{
     24    string name;
     25};
     26
     27// Declare the graph type and its vertex and edge types.
     28typedef undirected_graph<Actor> Graph;
     29typedef graph_traits<Graph>::vertex_descriptor Vertex;
     30typedef graph_traits<Graph>::edge_descriptor Edge;
     31
     32// Declare a container type for degree centralities and its
     33// corresponding property map.
     34typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
     35typedef CentralityProperty::container_type CentralityContainer;
     36typedef CentralityProperty::map_type CentralityMap;
     37
    1838int
    1939main(int argc, char *argv[])
    2040{
    21     //[setup_social_network
     41    // Create the graph and read it from standard input.
    2242    Graph g;
    23     map<string, Vertex> verts;
    24     //]
     43    read_graph(g, cin);
    2544
    26     // Read in and build the graph
    27     //[build_social_network
    28     for(string line; getline(cin, line); ) {
    29         if(line.empty()) continue;
    30         size_t index = line.find_first_of(',');
    31         string first(line, 0, index);
    32         string second(line, index + 1);
    33 
    34         Vertex u = add_named_vertex(g, first, verts);
    35         Vertex v = add_named_vertex(g, second, verts);
    36         add_edge(u, v, g);
    37     }
    38     //]
    39 
    40     // Compute the degree centrality for graph
    41     //[measure_social_network
     45    // Compute the degree centrality for graph.
    4246    CentralityContainer cents(num_vertices(g));
    4347    CentralityMap cm(cents, g);
    4448    degree_centrality(g, cm);
    45     //]
    4649
    47     // Print the degree centrality of each vertex
    48     //[print_social_network
     50    // Print the degree centrality of each vertex.
    4951    graph_traits<Graph>::vertex_iterator i, end;
    5052    for(tie(i, end) = vertices(g); i != end; ++i) {
    5153        cout << setiosflags(ios::left) << setw(12)
    52              << g[*i].name << cm[*i] << "\n";
     54             << g[*i].name << cm[*i] << endl;
    5355    }
    54     //]
    5556
    5657    return 0;
    5758}
     59//]
  • sandbox/SOC/2007/graphs/libs/graph/examples/flow_network.hpp

    r38621 r38738  
    1515#include <boost/graph/constant_property_map.hpp>
    1616
    17 //[flow_network_types
    1817struct Actor
    1918{
     
    2423typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
    2524typedef boost::graph_traits<Graph>::edge_descriptor Edge;
    26 //]
    2725
    2826typedef boost::exterior_vertex_property<Graph, int> DistanceProperty;
  • sandbox/SOC/2007/graphs/libs/graph/examples/helper.hpp

    r38621 r38738  
    88#define BOOST_GRAPH_EXAMPLE_HELPER_HPP
    99
     10#include <string>
     11#include <map>
    1012#include <algorithm>
    1113
    12 //[add_named_vertex
    1314template <typename Graph, typename VertexMap>
    1415typename boost::graph_traits<Graph>::vertex_descriptor
     
    3637    return v;
    3738}
    38 //]
     39
     40template <typename Graph, typename InputStream>
     41inline std::map<
     42        std::string,
     43        typename boost::graph_traits<Graph>::vertex_descriptor>
     44read_graph(Graph& g, InputStream& is)
     45{
     46    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
     47    std::map<std::string, Vertex> verts;
     48    for(std::string line; std::getline(is, line); ) {
     49        if(line.empty()) continue;
     50        std::size_t index = line.find_first_of(',');
     51        std::string first(line, 0, index);
     52        std::string second(line, index + 1);
     53
     54        Vertex u = add_named_vertex(g, first, verts);
     55        Vertex v = add_named_vertex(g, second, verts);
     56        add_edge(u, v, g);
     57    }
     58    return verts;
     59}
     60
     61
    3962
    4063//[property_comparator
  • sandbox/SOC/2007/graphs/libs/graph/examples/influence_prestige.cpp

    r38621 r38738  
    55// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
    66
     7//[influence_prestige_example
    78#include <iostream>
    89#include <iomanip>
    9 #include <string>
    10 #include <vector>
    11 #include <map>
    1210
    1311#include <boost/graph/directed_graph.hpp>
     
    1513#include <boost/graph/degree_centrality.hpp>
    1614
    17 #include "flow_network.hpp"
    1815#include "helper.hpp"
    1916
     
    2118using namespace boost;
    2219
     20// The Actor type stores the name of each vertex in the graph.
     21struct Actor
     22{
     23    std::string name;
     24};
     25
     26// Declare the graph type and its vertex and edge types.
     27typedef directed_graph<Actor> Graph;
     28typedef graph_traits<Graph>::vertex_descriptor Vertex;
     29typedef graph_traits<Graph>::edge_descriptor Edge;
     30
     31// Declare a container type for influence and prestige (both
     32// of which are degree centralities) and its corresponding
     33// property map.
     34typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
     35typedef CentralityProperty::container_type CentralityContainer;
     36typedef CentralityProperty::map_type CentralityMap;
     37
    2338int
    2439main(int argc, char *argv[])
    2540{
     41    // Create the graph and read it from standard input.
    2642    Graph g;
    27     map<string, Vertex> verts;
     43    read_graph(g, cin);
    2844
    29     // Read in and build the graph
    30     for(string line; getline(cin, line); ) {
    31         if(line.empty()) continue;
    32         size_t index = line.find_first_of(',');
    33         string first(line, 0, index);
    34         string second(line, index + 1);
    35 
    36         Vertex u = add_named_vertex(g, first, verts);
    37         Vertex v = add_named_vertex(g, second, verts);
    38         add_edge(u, v, g);
    39     }
    40 
    41     // Compute the influence and prestige for the graph
    42     //[compute_influence_prestige
     45    // Compute the influence for the graph.
    4346    CentralityContainer influence(num_vertices(g));
    4447    CentralityMap im(influence, g);
    4548    degree_centrality(g, im, measure_influence(g));
    4649
     50    // Compute the influence for the graph.
    4751    CentralityContainer prestige(num_vertices(g));
    4852    CentralityMap pm(prestige, g);
    4953    degree_centrality(g, pm, measure_prestige(g));
    50     //]
    5154
    5255    // Print the degree centrality of each vertex
    53     //[print_influence_prestige
    5456    graph_traits<Graph>::vertex_iterator i, end;
    5557    for(tie(i, end) = vertices(g); i != end; ++i) {
     
    5860             << g[v].name << "\t"
    5961             << im[v] << "\t"
    60              << pm[v] << "\n";
     62             << pm[v] << endl;
    6163    }
    62     //]
    6364
    6465    return 0;
    6566}
     67//]
  • sandbox/SOC/2007/graphs/libs/graph/examples/mean_geodesic.cpp

    r38678 r38738  
    55// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
    66
    7 #include "social_network.hpp"
    8 #include "helper.hpp"
    9 
     7//[mean_geodesic_example
    108#include <iostream>
    119#include <iomanip>
     10
     11#include <boost/graph/undirected_graph.hpp>
     12#include <boost/graph/exterior_property.hpp>
     13#include <boost/graph/constant_property_map.hpp>
    1214#include <boost/graph/floyd_warshall_shortest.hpp>
    1315#include <boost/graph/geodesic_distance.hpp>
     16#include "helper.hpp"
    1417
    1518using namespace std;
    1619using namespace boost;
    1720
     21// The Actor type stores the name of each vertex in the graph.
     22struct Actor
     23{
     24    std::string name;
     25};
     26
     27// Declare the graph type and its vertex and edge types.
     28typedef undirected_graph<Actor> Graph;
     29typedef graph_traits<Graph>::vertex_descriptor Vertex;
     30typedef graph_traits<Graph>::edge_descriptor Edge;
     31
     32// Declare a matrix type and its corresponding property map that
     33// will contain the distances between each pair of vertices.
     34typedef exterior_vertex_property<Graph, int> DistanceProperty;
     35typedef DistanceProperty::matrix_type DistanceMatrix;
     36typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
     37
     38// Declare the weight map so that each edge returns the same value.
     39typedef constant_property_map<Edge, int> WeightMap;
     40
     41// Declare a container and its corresponding property map that
     42// will contain the resulting mean geodesic distances of each
     43// vertex in the graph.
     44typedef exterior_vertex_property<Graph, float> GeodesicProperty;
     45typedef GeodesicProperty::container_type GeodesicContainer;
     46typedef GeodesicProperty::map_type GeodesicMap;
     47
     48
    1849int
    1950main(int argc, char *argv[])
    2051{
     52    // Create the graph and read it from standard input.
    2153    Graph g;
    22     map<string, Vertex> verts;
     54    read_graph(g, cin);
    2355
    24     // Read in and build the graph
    25     for(string line; getline(cin, line); ) {
    26         if(line.empty()) continue;
    27         size_t index = line.find_first_of(',');
    28         string first(line, 0, index);
    29         string second(line, index + 1);
    30 
    31         Vertex u = add_named_vertex(g, first, verts);
    32         Vertex v = add_named_vertex(g, second, verts);
    33         add_edge(u, v, g);
    34     }
    35 
     56    // Compute the distances between all pairs of vertices using
     57    // the Floyd-Warshall algorithm. Note that the weight map is
     58    // created so that every edge has a weight of 1.
    3659    DistanceMatrix distances(num_vertices(g));
    3760    DistanceMatrixMap dm(distances, g);
     
    3962    floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
    4063
    41     // Compute the degree centrality for graph
    42     //[compute_mean_geodesics
     64    // Compute the mean geodesic distances for each vertex in
     65    // the graph.
    4366    GeodesicContainer geodesics(num_vertices(g));
    4467    GeodesicMap gm(geodesics, g);
    4568    mean_geodesic(g, dm, gm);
     69
     70    // Using the previously computed mean geodesic distances, compute
     71    // the mean geodesic distance for the entire graph.
    4672    float geo = graph_mean_geodesic(g, gm);
    47     //]
    4873
     74    // Print the mean geodesic distance of each vertex and finally,
     75    // the graph itself.
    4976    graph_traits<Graph>::vertex_iterator i, end;
    5077    for(tie(i, end) = vertices(g); i != end; ++i) {
    51         cout << g[*i].name << " : " << get(gm, *i) << "\n";
     78        cout << setw(12) << setiosflags(ios::left)
     79             << g[*i].name << get(gm, *i) << endl;
    5280    }
    53 
    54     //[print_graph_mean_geodesic
    5581    cout << "mean geodesic distance: " << geo << endl;
    56     //]
    5782
    5883
    5984    return 0;
    6085}
     86//]
  • sandbox/SOC/2007/graphs/libs/graph/examples/scaled_closeness_centrality.cpp

    r38656 r38738  
    55// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
    66
    7 #include "social_network.hpp"
    8 #include "helper.hpp"
    9 
     7//[scaled_closeness_centrality_example
    108#include <iostream>
    119#include <iomanip>
     10
     11#include <boost/graph/undirected_graph.hpp>
     12#include <boost/graph/exterior_property.hpp>
     13#include <boost/graph/constant_property_map.hpp>
    1214#include <boost/graph/floyd_warshall_shortest.hpp>
    1315#include <boost/graph/closeness_centrality.hpp>
     16#include "helper.hpp"
    1417
    1518using namespace std;
    1619using namespace boost;
    1720
    18 //[normalized_closeness_measure
     21// This template struct provides a generic version of a "scaling"
     22// closeness measure. Specifically, this implementation divides
     23// the number of vertices in the graph by the sum of geodesic
     24// distances of each vertex. This measure allows customization
     25// of the distance type, result type, and even the underlying
     26// divide operation.
    1927template <typename Graph,
    2028          typename Distance,
    2129          typename Result,
    22           typename Divide = std::divides<Result> >
    23 struct normalized_closeness_measure
     30          typename Divide = divides<Result> >
     31struct scaled_closeness_measure
    2432{
    2533    typedef Distance distance_type;
     
    3745    Divide div;
    3846};
    39 //]
     47
     48// The Actor type stores the name of each vertex in the graph.
     49struct Actor
     50{
     51    std::string name;
     52};
     53
     54// Declare the graph type and its vertex and edge types.
     55typedef undirected_graph<Actor> Graph;
     56typedef graph_traits<Graph>::vertex_descriptor Vertex;
     57typedef graph_traits<Graph>::edge_descriptor Edge;
     58
     59// Declare a matrix type and its corresponding property map that
     60// will contain the distances between each pair of vertices.
     61typedef exterior_vertex_property<Graph, int> DistanceProperty;
     62typedef DistanceProperty::matrix_type DistanceMatrix;
     63typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
     64
     65// Declare the weight map so that each edge returns the same value.
     66typedef constant_property_map<Edge, int> WeightMap;
     67
     68// Declare a container and its corresponding property map that
     69// will contain the resulting closeness centralities of each
     70// vertex in the graph.
     71typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
     72typedef ClosenessProperty::container_type ClosenessContainer;
     73typedef ClosenessProperty::map_type ClosenessMap;
    4074
    4175int
    4276main(int argc, char *argv[])
    4377{
     78    // Create the graph and read it from standard input.
    4479    Graph g;
    45     map<string, Vertex> verts;
     80    read_graph(g, cin);
    4681
    47     // Read in and build the graph
    48     for(string line; getline(cin, line); ) {
    49         if(line.empty()) continue;
    50         size_t index = line.find_first_of(',');
    51         string first(line, 0, index);
    52         string second(line, index + 1);
    53 
    54         Vertex u = add_named_vertex(g, first, verts);
    55         Vertex v = add_named_vertex(g, second, verts);
    56         add_edge(u, v, g);
    57     }
    58 
     82    // Compute the distances between all pairs of vertices using
     83    // the Floyd-Warshall algorithm. Note that the weight map is
     84    // created so that every edge has a weight of 1.
    5985    DistanceMatrix distances(num_vertices(g));
    6086    DistanceMatrixMap dm(distances, g);
    6187    WeightMap wm(1);
    6288    floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
    63     //]
     89
     90    // Create the scaled closeness measure.
     91    scaled_closeness_measure<Graph, int, float> m;
    6492
    6593    // Compute the degree centrality for graph
    66     //[compute_normalized_closeness
    6794    ClosenessContainer cents(num_vertices(g));
    6895    ClosenessMap cm(cents, g);
    69     normalized_closeness_measure<Graph, int, float> m;
    7096    closeness_centrality(g, dm, cm, m);
    71     //]
    7297
    73     vector<Vertex> sorted(num_vertices(g));
    74     sort_vertices(sorted, g, cm);
    75 
    76     // Print the degree centrality of each vertex
    77     vector<Vertex>::iterator i, end = sorted.end();
    78     for(i = sorted.begin(); i != end; ++i) {
     98    // Print the scaled closeness centrality of each vertex.
     99    graph_traits<Graph>::vertex_iterator i, end;
     100    for(tie(i, end) = vertices(g); i != end; ++i) {
    79101        cout << setw(12) << setiosflags(ios::left)
    80              << g[*i].name << cm[*i] << "\n";
     102             << g[*i].name << get(cm, *i) << endl;
    81103    }
    82104
    83105    return 0;
    84106}
     107//]
Note: See TracChangeset for help on using the changeset viewer.