123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145 |
- //=======================================================================
- // Copyright 2013 University of Warsaw.
- // Authors: Piotr Wygocki
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #ifndef SAMPLE_GRAPH_UNDIRECTED_HPP
- #define SAMPLE_GRAPH_UNDIRECTED_HPP
- #include <iostream>
- #include <cstdlib>
- #include <boost/graph/adjacency_list.hpp>
- namespace boost {
- struct SampleGraph {
- typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
- typedef adjacency_list < vecS, vecS, directedS, no_property,
- property < edge_capacity_t, long,
- property < edge_residual_capacity_t, long,
- property < edge_reverse_t, Traits::edge_descriptor,
- property <edge_weight_t, long>
- >
- >
- > > Graph;
- typedef property_map < Graph, edge_capacity_t >::type Capacity;
- typedef property_map < Graph, edge_residual_capacity_t >::type ResidualCapacity;
- typedef property_map < Graph, edge_weight_t >::type Weight;
- typedef property_map < Graph, edge_reverse_t>::type Reversed;
- typedef boost::graph_traits<Graph>::vertices_size_type size_type;
- typedef Traits::vertex_descriptor vertex_descriptor;
-
- template <class Graph, class Weight, class Capacity, class Reversed, class ResidualCapacity>
- class EdgeAdder {
- public:
- EdgeAdder(Graph& g, Weight& w, Capacity& c, Reversed& rev
- , ResidualCapacity&) : m_g(g), m_w(w), m_cap(c), m_rev(rev) {}
- void addEdge(vertex_descriptor v, vertex_descriptor w, long weight, long capacity) {
- Traits::edge_descriptor e,f;
- e = add(v, w, weight, capacity);
- f = add(w, v, -weight, 0);
- m_rev[e] = f;
- m_rev[f] = e;
- }
- private:
- Traits::edge_descriptor add(vertex_descriptor v, vertex_descriptor w
- , long weight, long capacity)
- {
- bool b;
- Traits::edge_descriptor e;
- boost::tie(e, b) = add_edge(vertex(v, m_g), vertex(w, m_g), m_g);
- if (!b) {
- std::cerr << "Edge between " << v << " and " << w << " already exists." << std::endl;
- std::abort();
- }
- m_cap[e] = capacity;
- m_w[e] = weight;
- return e;
- }
- Graph & m_g;
- Weight & m_w;
- Capacity & m_cap;
- Reversed & m_rev;
- };
- static void getSampleGraph(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
- Capacity capacity = get(edge_capacity, g);
- Reversed rev = get(edge_reverse, g);
- ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
- Weight weight = get(edge_weight, g);
- getSampleGraph(g,s,t,capacity,residual_capacity,weight,rev);
- }
- template <class Graph, class Weight, class Capacity, class Reversed, class ResidualCapacity>
- static void
- getSampleGraph(Graph &g, vertex_descriptor & s, vertex_descriptor & t,
- Capacity capacity, ResidualCapacity residual_capacity, Weight weight, Reversed rev) {
- size_type N(6);
- for(size_type i = 0; i < N; ++i){
- add_vertex(g);
- }
- s = 0;
- t = 5;
- EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity> ea(g, weight, capacity, rev, residual_capacity);
- ea.addEdge(0, 1, 4 ,2);
- ea.addEdge(0, 2, 2 ,2);
- ea.addEdge(1, 3, 2 ,2);
- ea.addEdge(1, 4, 1 ,1);
- ea.addEdge(2, 3, 1 ,1);
- ea.addEdge(2, 4, 1 ,1);
- ea.addEdge(3, 5, 4 ,20);
- ea.addEdge(4, 5, 2 ,20);
- }
- static void getSampleGraph2(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
- const boost::graph_traits<Graph>::vertices_size_type N(5);
- typedef property_map < Graph, edge_reverse_t >::type Reversed;
- for(size_type i = 0; i < N; ++i){
- add_vertex(g);
- }
- Capacity capacity = get(edge_capacity, g);
- Reversed rev = get(edge_reverse, g);
- ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
- Weight weight = get(edge_weight, g);
- s = 0;
- t = 4;
- EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity> ea(g, weight, capacity, rev, residual_capacity);
- ea.addEdge(0, 1, 4 ,2);
- ea.addEdge(0, 2, 2 ,2);
- ea.addEdge(1, 2, 2 ,2);
- ea.addEdge(2, 3, 1 ,1);
- ea.addEdge(2, 4, 1 ,1);
- ea.addEdge(3, 4, 1 ,1);
- ea.addEdge(1, 0, 2 ,2);
- ea.addEdge(2, 0, 1 ,1);
- ea.addEdge(2, 1, 5 ,2);
- ea.addEdge(3, 2, 1 ,1);
- ea.addEdge(4, 2, 2 ,2);
- ea.addEdge(4, 3, 1 ,3);
- }
- };
- } //boost
- #endif /* SAMPLE_GRAPH_UNDIRECTED_HPP */
|