TODO

plot times                                      []

recover the flow in a more efficient way        []

merger_edge scans all edges each iteration.
Faster way to do this?                          []

Checking for the resulting flow              
(storing the neighbours of sink)                []
excess storage
could maybe store is_strong as a local 
field of vertex. At least for PS since
vertices can only become strong, not weak. 
and they only become strong at a single
place                                           []

maybe reset vertexsets length, rather than 
allocating/deallocating it once for each set
of active vertices                              []

analyze if the edges need pointers to 
vertices / values / both                        [done]
get rid of either first or first_ref
from edges                                      [done]

fix memory leaks                                [done]

get rid of cpp module                           [done]
for this, need to get rid of
vertexcollection_contains

source_edges, source_neighbours and relevant
crap. get rid of.                               [done]

now when I have out_edges for all vertices,
I can get an edgecollection directly as a path,
not a vertexcollection that I later need to 
convert.                                        [done]
for this, we need a 
get_out_edge(network, first, second)

implement the GBT algorithm                     [done]
discharge                                       [done]
push_relabel                                    [done]

I think the biggest part is redundant 
calculations of the index for edges and
vertices. If vertices and edges held 
additional information then all these 
redundant computations could be avoided.        [done]

option 1: create a new structure called eg
networkvertex containing a vertex and the 
extra information
implications:   
    * have to change vertex and 
      edgecollection. In fact, have to change
      edge to networkedge and vertex to 
      networkvertex in entire program
    * one may level of indirection 
    * remove all network arguments from 
      networkedge and networkvertex

option 2: store the network information in the
old structures.
[chosen procedure]
implications:
    * do not have to change vertex and 
      edgecollection
    * less modular code and wierder
    * remove all network arguments from 
      networkedge and networkvertex

eliminate uneccesary pointers
to edges for example
edges                                           [done]

improve the speed of 
vertexcollection_to_edgecollection              [done]

store adjacent edges to vertices like 
the goldberg- tarjan specification              [done]

do I really need to store residual_edges?       [done]
more efficient way to get admissable edge,
active vertex

have to go through each module and check
* are there functions that exist that does 
  not make sense?
* are there too long lines?
* Is there missing/outdated documentation?

vertex.c                                        []
util.c                                          []
parser.c                                        []
network.c                                       []
networkedge.c                                   []
networkvertex.c                                 []
pseudoflow.c                                    []
pseudoflow_network.c                            []
push_relabel.c                                  []
push_relabel_network.                           []
tokenizer.c                                     []
tokentable.c                                    []
tree.c                                          []
treevertex.c                                    []
vertexcollection.c                              []
Makefile                                        []
spit.c                                          []
collection.c                                    [done]
cpp                                             [done]
edge.c                                          [done]
edgecollection.c                                [done]
graph.c                                         [done]

parser should not initialize the network,
it should be done in network.c                  [done]

if the edge held references to its vertices,
then the algorithm would speed up               [done]

do not explicitly need to maintain 
strong and weak vertexsets. The strong 
vertices are the ones that have positive
excess.                                         [done]

maintain the excesses for constant time lookup
right now the most timeconsuming function has to 
do with excesses: is_strong. Iterates over all
edges.                                          [done]

MISC:

fails on 5x5.dmx                                [done]
excess not correct                              [done]

the node is in the strong branch, it should
not be chosen, it should not be weak.
The maintenence of the strong and weak
nodes are wrong.
The only Nodes that are strong at 
initialization are A(s). Then nodes become 
strong after the split operation                [done]

algorithm is trying to push along a residual
edge that does not exist

should have excesses as a function              [done]

maybe pseudoflow is not considering backward
edges                                           [done]

new bug: the flow never gets pushed past the 
first layer solution: (seemingly) have 
to maintain the strong/weak vertex sets. 
Forgot to do that before                        [done]

The difference with (4, 5) is that we call
networkedge_augment instead of split            [done]

program hangs. Maybe in 
vertexcollection_to_edgecollection but not 
sure                                            [done]
problem lies in tree_get_path_to_root
p(4) == 5 and p(5) == 4

The edge (4, 5) gets selected twice. 
Seems like the only time networkedge_augment
gets called, the algorithm fucks up.
This also does not get called in the 2x2
instance
Ok, the flow does not get augmented, because 
added_flow = delta = 0 = the excess of the
strong branch. Has no excess because it never
gets set to anything else after initialization
to 0

Looks like excess and flows of root->branch 
edges should be updated somewhere else. I get
an augmentation of delta=0

might want to store all edges together          []
(root + reverse + normal)
places where simplicity would be improved:
networkedge_residual_capacity
vertexcollection_to_edgecollection

May not need root edges, if the semantics 
of the algorithm is as i think:
until [v_i, v_i+1]->second == root              []

Have to check if I can replace network->source
and network->sink with root.                    [done]
In the algorithm itself it's nothing referring 
to source or sink
network->source / sink: 
pseudoflow.c
parser.c
push_relabel_network.c
network.c
have to keep sorce/sink - since the algorithm 
initially partitions the set into strong/weak 
vertices depending on which are adjacent to
the source or sink. Can however add a new 
root vertex and treat it as sink/source

new bug: algorithm thinks (6, 11) is an edge
in gen3x3.dmx but it's not. The algorithm 
specifies all vertices to be a part of 
the tree in the initialization, even though
in the graph, they are not. 
However, the arcs of a normalized tree is 
a subset of the arcs of the graph in addition
to a new set of arcs which goes from the root 
to each vertex.                                 []

The problem arises because the algorithm 
should consider network->source and
network->sink the same node in the tree
but the program doesnt do that. So I get
(5, 1) which should be the same as (5, 6)
but the program does not understand that        [done]

also, the function 
vertexcollection_to_edgecollection should 
not be in tree.c. The reason is that it 
needs things that are outside the scope
of a tree.                                      [done]
This function should probably also be 
reworked.                                       []

add inflow to the ps algorithm

Path now returns a path from vertex to root.
I need a path from root -> vertex               [done]
or do I? no                                     [done]  

Now I need to get the path 
[r_s, ..s, w, r_w, r] and push delta units
along it. Ie. given a tree, I need to get 
the edgepath described by a path. I can use
tree_path_to_root to get a vertexpath. Then
I can explicitly build an edgepath from this
using edgecollection_get_reference. 
More efficient way? * store the edge (v, p(v))
in each vertex

May not need a pointer to 
the children. May just need to maintain 
parent pointers.                                [done]

Also, might be necessary to store make
stree work with normal vertices instead of
a special structure. Keep parent pointers
in struct vertex.                               [done]

Why Can't I implement vertexcollection as 
a cpp map etc?

when deattaching and merging the tree, 
the order becomes inversed. Alternatives:
(1) keep the tree (????)
(2) new root for the tree
can be done in logn according to paper
Flip the pointers on the path from vertex to 
current root

change tree_insert order of arguments to 
something sane                                  [done]

change tree_insert to insert a vertexpointer
not a treevertexpointer. Should probably try
to minimize interaction with vertexpointer.     [done]

For the merge step, need to detach the strong
branch from the root and connect the tree 
using (s, w). To detach the strong branch, 
we need to 
(1) remove the pointer from s to root.
(2) romeve the pointer from root to s

To connect the tree using (s, w) we need to
(1) take the subtree s and insert it under w
using tree_insert.

LOGIC:

to remove something from edgecollection, it 
is not enough to use collection to remove.
We also need to update the indices map.

Get the branch which contains a particular
vertex                                          [done]
Have no such function in tree. Need to
implement it. However, I have a treevertex_get.
Just need to wrap it in tree.
*** IMPORTANT *** Need to take action with 
trees contains
structure. Is it needed for the algorithm? If 
I can delete it, it would mean a much simpler
tree. If not deleted, both make_tree and tree_get
is BROKEN.
I don't expcilitly need to check if a tree 
contains a vertex => can remove this 
functionality                                   [done]

TESTS:
initialize_pseudoflow                           [done]
merger_edge                                     [done]
tree_deattach                                   [done]

FUNCTIONS:

tree_set_root                                   []
for each vertex on the path from v to root:
(1) add parent(v) to children(v)
(2) remove v from children(parent)
(3) set parent(v) = null
(4) set parent(parent) = v
tree_path                                       []
initialize_pseudoflow_algorithm                 [done]
get_merger_edge()                               [done]
scan the residual edges. Each vertex in the tree
represents a vertex in the graph. The excess of 
each node is always updated and maintained. So
we need a 
    int *excess
pointer where we store that.

A vertex is strong if excess(T_ri) > 0 and weak
otherwise. Could initially create a function that 
scans the tree, for each vertex met, check the excess.
since the excess is maintained for ri by the algorithm,
we could quickly get a tuple of strong and weak vertices.

Now, we would like to find a residual edge that connects
these two sets S, W. Naive: Scan the residual edges. for an 
edge (u, v), check if u in S and v in W.

MISC:

save index together with edge in edgeset?
avoid get_index?                                []

push_relabel_network.{c,h}
I would like to use the network modules for the
next algorithm as well. Need to be careful what 
is native to push/relabel and not psuedoflow:
* network->active_vertices                      [done]
    - activate_vertices                         [done]
    - initialize
    - networkvertex_active
* network->distance_labels                      [done]
* network->is_reverse (?)                       [done]

Excesses depends on inflows/outflows, but it's
more general than exflow: instead of a single
vertex it's the flow difference of a vertex-set,
and the edges are the edges cut by the vertices

If functions in networkedge/networkvertex 
are completely for push_relabel, should move
to a new module                                 [done]

is_active(vertex) needs to be extended to
is_strong(vertexset) because the pseudoflow-
algorithm works on subtrees aka vertexsets      [done]

Then rename algorithms to push_relabel and      [done]
initialize a new module for psuedoflow          [done]

-----------------

timer in ./bin/main                             [done]
add constructs to allow for constant access     [done]
(do not need to generate res_graph etc)
clean up, sort network
change spit to accept a network

efficient maintanence of residual graph         [done]
remove, add max Ologn                           [done]

network store in_edges for each vertex          [done]

store the inflow and outflow of vertices        [done]

most time taken by vertex comparisons:          [done]
change vertexpointer to vertex?

need not flows of edges? enough with vertex     [done]
in/out flows?

better time remove                              [done]

store active vertices                           [done]
an active vertex is a vertex with exflow > 0
active vertex change = exflow change
exflow change = inflow, outflow change
inflow, outflow change only in add_flow 

instead of removing, I could add a guard to
make edges residual. residual edges are only
added and removed at two places. 
1. the initialization of the algorithm
2. when augmenting
At these places I could set a residual 
property to true/false

The residual edges are used at
1. find_min
2. networkedge_is_admissable
nowhere else.

Where do i iterate over residual edges?
* find_min
I could have a map is_residual that I check in  [done]
find_min
networkedge_admissable
turn out it's actually more expensive to check
this map, than to perform the remove explicitly.
aborting.

RENAMINGS:

set_* to replace*                               [done]
change variables of *collection to edges        [done]
change variables of *collection to vertices     [done]
array to collection                             [done]
edgeset to edgecollection                       [done]
vertexset to vertexcollection                   [done]

FUNCTIONS:

edgecollection_length                           [done]
vertexcollection_length                         [done]
array_length                                    [done]
exflow(vertex) = inflow - outflow               [done]
active(vertex) = exflow > 0                     [done]
distance_label(vertex)                          [done]
is_admissable(edge)                             [done]
network_residual                                ?
float residualal_capacity(networkedge)          [done]
network_edge_is_reverse                         [done]
networkvertex_distance_label                    [done]
edgecollection_remove                           [done]

TESTS FUNCTIONS:

graph_incident_with                             [done]
networkvertex_exflow                            [done]
network_active_vertex                           [done]
network_admissable_edge                         [] *
edgecollection_index_of                         [] * (needs to be the d+(v))
vertexcollection_index_of                       [] *
network_edge_is_residual                        [] *
edge_equals_reverse                             [] *
networkedge_augment                             [] *
networkvertex_set_distance_label                [done]
networkvertex_distance_label                    [done]
push_relabel                                    [] *
network_flow                                    []
graph_neighbours_of                             [] 
network_edge_is_reverse                         [done]

TESTS MODULES:

array.c                                         [done]
disjointset.c                                   [done]
edge.c                                          [done]
edgecollection.c                                [done]
graph.c                                         [done]
parser.c                                        [done]
spit.c                                          []
tokenizer.c                                     [done]
tokentable.c                                    [done]
tree.c                                          []
treevertex.c                                    []
util.c                                          []
vertex.c                                        [done]
vertexcollection.c                              []
network.c                                       []
main.c