Subject: [boost] BGL
From: Sultana Rashid (sultana32_at_[hidden])
Date: 2011-04-17 06:49:41
I have submitted two proposals to Boost.I am very interested in C++ works
and algorithms,so I submitted only for Boost projects.I met an accident
after proposal submission so that I could not refine my project ideas.Now I
am well and have enough free time to interact with mentors and do the
necessary works.My proposals can be found here:
Now I am writing something about one of my algorithms' prospective design.
*Dinitz blocking max flow algorithm:*
*Input:* Graph& g .A directed graph. The graph's type will be a model of
VertexListGraph and IncidenceGraph.
*Input:* *source node* which is a vertex. Its type will be graph's vertex
*Input:* *sink node* ,its type will be same as source node.
*Input:* capacity map(CapacityEdgeMap cap),the edge capacity property map.
The type must be a model of a constant Lvalue Property Map. The key type of
the map must be the graph's edge descriptor type.
Default: get(edge_capacity, g)
*Input:* reverse edge map(ReverseEdgeMap rev) An edge property map that maps
every edge (u,v) in the graph to the reverse edge (v,u). The map must be a
model of constant Lvalue Property Map. The key type of the map must be the
graph's edge descriptor type.
Default: get(edge_reverse, g)
*Input:*residual capacity map(ResidualCapacityEdgeMap res) ,This maps edges
to their residual capacity. The type must be a model of a mutable Lvalue
Property Map. The key type of the map must be the graph's edge descriptor
Default: get(edge_residual_capacity, g)
At first the whole capacity will be the residual capacity,then after every
phase of calculation it will act as output.
*Input:* vertex index(VertexIndexMap index_map)
Maps each vertex of the graph to a unique integer in the range [0,
num_vertices(g)). The map must be a model of constant LvaluePropertyMap. The
key type of the map must be the graph's vertex descriptor type.
Default: get(vertex_index, g)
*Output:*The total flow of the network,flow in every iteration and min cut.
*** User will be able to use the algorithm in two ways, named parameter
version and non-named parameter version.*
*** In named parameter version,explicit inputs will be the graph,source and
sink node.Other will be default params.
*** In non-named parameter version,all will be explicitly input.
I studied already implemented flow algorithms and took help.But I am in
confusion about UTIL parameters.*
If I get help or advice ,I'll try my best to refine my ideas about
implementation and design.I studied all the relevant algorithms and wish to
write all after getting feedback.I am not sure what to write about algorithm
design.Would I write details how input and output will work as how min cut
will be got or how flow will be determined?
Please give me some hints.Hope to get some help.If I am not suitable for
GSoC,however I want to know and implement.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk