Ferramentas de Utilizador
inf05504:2012-2-trabalhos
Diferenças
Esta página mostra as diferenças entre as duas revisões da página.
| Ambos os lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
|
inf05504:2012-2-trabalhos [2012/11/21 13:05] marcus [Trabalho 4 (Emparelhamentos)] |
inf05504:2012-2-trabalhos [2013/01/13 09:01] (Actual) marcus [Entregas] |
||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| ==== Entregas ==== | ==== Entregas ==== | ||
| - | Atualizado: 02/10/2012 | + | Atualizado: 13/01/2012 |
| ^ No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ | ^ No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ | ||
| | 118489 | - | - | - | - | - | | | 118489 | - | - | - | - | - | | ||
| - | | 136830 | - | - | - | - | - | | + | | 136830 | P | - | - | - | - | |
| - | | 150821 | - | - | - | - | - | | + | | 150821 | P | - | P | - | P | |
| - | | 152985 | - | - | - | - | - | | + | | 152985 | P | P | P | P | P | |
| - | | 159847 | P | - | - | - | - | | + | | 159847 | P | P | P | R | P | |
| - | | 160636 | P | - | - | - | - | | + | | 160636 | P | P | P | - | P | |
| - | | 173362 | P | - | - | - | - | | + | | 173362 | P | R | - | - | P | |
| | 180190 | - | - | - | - | - | | | 180190 | - | - | - | - | - | | ||
| | 181026 | - | - | - | - | - | | | 181026 | - | - | - | - | - | | ||
| Linha 200: | Linha 200: | ||
| /** | /** | ||
| * \file maxflow.cpp | * \file maxflow.cpp | ||
| - | * \author Marcus Ritt <mrpritt@inf.ufrgs.br> | + | * \author Marcus Ritt <mrpritt@inf.ufrgs.br> |
| * \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $ | * \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $ | ||
| - | * \date Time-stamp: <2009-03-23 17:52:25 ritt> | + | * \date Time-stamp: <2012-12-06 17:10:05 ritt> |
| * | * | ||
| * Read a maximum flow problem in DIMACS format and output the maximum flow. | * Read a maximum flow problem in DIMACS format and output the maximum flow. | ||
| Linha 213: | Linha 213: | ||
| #include <boost/graph/adjacency_list.hpp> | #include <boost/graph/adjacency_list.hpp> | ||
| #include <boost/graph/read_dimacs.hpp> | #include <boost/graph/read_dimacs.hpp> | ||
| - | #include <boost/graph/edmunds_karp_max_flow.hpp> | + | #include <boost/graph/edmonds_karp_max_flow.hpp> |
| + | #include <boost/graph/push_relabel_max_flow.hpp> | ||
| using namespace boost; | using namespace boost; | ||
| + | |||
| + | // graph element descriptors | ||
| + | typedef adjacency_list_traits<vecS,vecS,directedS>::vertex_descriptor DiNode; | ||
| + | typedef adjacency_list_traits<vecS,vecS,directedS>::edge_descriptor Edge; | ||
| // a directed graph with reverse edges | // a directed graph with reverse edges | ||
| struct VertexInformation {}; | struct VertexInformation {}; | ||
| - | struct EdgeInformation; | ||
| - | |||
| - | typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph; | ||
| - | typedef graph_traits<DiGraph>::edge_descriptor Edge; | ||
| - | typedef graph_traits<DiGraph>::vertex_descriptor DiNode; | ||
| - | |||
| typedef unsigned Capacity; | typedef unsigned Capacity; | ||
| struct EdgeInformation { | struct EdgeInformation { | ||
| Linha 231: | Linha 229: | ||
| Edge reverse_edge; | Edge reverse_edge; | ||
| }; | }; | ||
| + | |||
| + | typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph; | ||
| int main(int argc, char *argv[]) { | int main(int argc, char *argv[]) { | ||
| Linha 237: | Linha 237: | ||
| DiGraph g; | DiGraph g; | ||
| DiNode s,t; | DiNode s,t; | ||
| + | | ||
| read_dimacs_max_flow(g, | read_dimacs_max_flow(g, | ||
| get(&EdgeInformation::edge_capacity,g), | get(&EdgeInformation::edge_capacity,g), | ||
| get(&EdgeInformation::reverse_edge,g), | get(&EdgeInformation::reverse_edge,g), | ||
| s, t); | s, t); | ||
| + | | ||
| // (1) determine maximum flow | // (1) determine maximum flow | ||
| - | cout << edmonds_karp_max_flow(g, s, t, | + | cout << push_relabel_max_flow(g, s, t, |
| capacity_map(get(&EdgeInformation::edge_capacity,g)). | capacity_map(get(&EdgeInformation::edge_capacity,g)). | ||
| residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)). | residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)). | ||
| Linha 273: | Linha 273: | ||
| * Para compilar: Usar C++ e Boost. | * Para compilar: Usar C++ e Boost. | ||
| <code c++> | <code c++> | ||
| - | #include <iostream> | + | #include <iostream> |
| - | #include <cassert> | + | #include <cassert> |
| - | using namespace std; | + | using namespace std; |
| - | | + | |
| - | #include <boost/graph/adjacency_list.hpp> | + | #include <boost/graph/adjacency_list.hpp> |
| - | #include <boost/graph/max_cardinality_matching.hpp> | + | #include <boost/graph/max_cardinality_matching.hpp> |
| - | using namespace boost; | + | using namespace boost; |
| - | + | ||
| - | // information stored in vertices | + | |
| - | struct VertexInformation; | + | |
| - | + | ||
| - | // information stored in edges | + | |
| - | struct EdgeInformation {}; | + | |
| - | + | ||
| - | // graph is an adjacency list represented by vectors | + | |
| - | typedef adjacency_list<vecS, vecS, undirectedS,VertexInformation,EdgeInformation> Graph; | + | |
| - | typedef graph_traits<Graph>::vertex_descriptor Node; | + | |
| - | typedef graph_traits <Graph>::edge_descriptor Edge; | + | |
| + | // graph element descriptors | ||
| + | typedef adjacency_list_traits<vecS,vecS,undirectedS>::vertex_descriptor Node; | ||
| + | typedef adjacency_list_traits<vecS,vecS,undirectedS>::edge_descriptor Edge; | ||
| + | |||
| + | // information stored in vertices | ||
| struct VertexInformation { | struct VertexInformation { | ||
| Node mate; // partner or graph_traits<Graph>::null_vertex() | Node mate; // partner or graph_traits<Graph>::null_vertex() | ||
| - | }; | + | }; |
| - | | + | // information stored in edges |
| - | int main(int argc, char *argv[]) { | + | struct EdgeInformation {}; |
| + | |||
| + | // graph is an adjacency list represented by vectors | ||
| + | typedef adjacency_list<vecS,vecS,undirectedS,VertexInformation,EdgeInformation> Graph; | ||
| + | |||
| + | int main(int argc, char *argv[]) { | ||
| assert(argc == 3); | assert(argc == 3); | ||
| unsigned n = atoi(argv[1]); | unsigned n = atoi(argv[1]); | ||
| double p = atof(argv[2]); | double p = atof(argv[2]); | ||
| + | |||
| srand48(time(0)); | srand48(time(0)); | ||
| + | | ||
| // (1) generate random bi-partite graph | // (1) generate random bi-partite graph | ||
| Graph g; | Graph g; | ||
| + | | ||
| for(unsigned i=0; i<2*n; i++) | for(unsigned i=0; i<2*n; i++) | ||
| add_vertex(g); | add_vertex(g); | ||
| + | | ||
| for(unsigned i=0; i<n; i++) | for(unsigned i=0; i<n; i++) | ||
| for(unsigned j=n; j<2*n; j++) | for(unsigned j=n; j<2*n; j++) | ||
| Linha 314: | Linha 313: | ||
| Edge e = add_edge(i,j,g).first; | Edge e = add_edge(i,j,g).first; | ||
| } | } | ||
| + | |||
| // (2) get maximum matching | // (2) get maximum matching | ||
| edmonds_maximum_cardinality_matching(g, get(&VertexInformation::mate,g)); | edmonds_maximum_cardinality_matching(g, get(&VertexInformation::mate,g)); | ||
| Linha 322: | Linha 321: | ||
| if (g[*vb].mate != graph_traits<Graph>::null_vertex()) | if (g[*vb].mate != graph_traits<Graph>::null_vertex()) | ||
| card++; | card++; | ||
| - | cout << "The cardinality of a maximum matching is " << card/2 << "." << endl; | + | //cout << "The cardinality of a maximum matching is " << card/2 << "." << endl; |
| + | |||
| // (3) print out in DIMACS format | // (3) print out in DIMACS format | ||
| - | cout << "c Bi-partite graph" << endl; | + | cout << "c Bi-partite graph" << endl << endl; |
| cout << "p edge " << num_vertices(g) << " " << num_edges(g) << endl; | cout << "p edge " << num_vertices(g) << " " << num_edges(g) << endl; | ||
| graph_traits<Graph>::edge_iterator eb, ee; | graph_traits<Graph>::edge_iterator eb, ee; | ||
inf05504/2012-2-trabalhos.1353510311.txt.gz · Esta página foi modificada pela última vez em: 2012/11/21 13:05 (Edição externa)
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
