<div dir="ltr"><div><div><div><div><div><div>Hello,<br><br></div>I am basing myself on the network_simplex_simple.h code written by N. Bonneel (<a href="http://liris.cnrs.fr/~nbonneel/FastTransport/">http://liris.cnrs.fr/~nbonneel/FastTransport/</a>).<br><br></div>I am developing an algorithm where I would need to initialise the network with already known flows. <br></div>I want to input a 2D array of size (number of sources x number of sinks) and the network simplex to begin the algorithm with the flows in my 2D array.<br><br></div>First, is there something similar already coded?<br><br></div>If not, I gave it a try and here is what I did :<br><br></div><div>My idea was to let the algorithm initialise the artificial arcs with the root, and before it runs the main execution loop, I do iterations where I set the entering arc and the amount by which the flow changes.<br></div><div><br>initialValues_[i][j] : 2D array with initial flows with n0_ sources and n1_ sinks<br><br></div>// EDIT IN THE START() FUNCTION<br><br><div>template <typename PivotRuleImpl><br>        ProblemType start() {<br>          <br>// BEGIN EDIT<br><br>            // Initialisation by user sets the entering arc and the quantity by which the flow changes.<br>            // The rest is handled by already existing functions.<br><br>            if(my_initialise_bool){<br>              for(int i = 0; i < n0_; i++) {<br>                for(int j = 0; j < n1_; j++) {<br>                if(initialValues_[i][j]>0){<br>                  in_arc=findArc(_graph.nodeFromId(i),_graph.nodeFromId(j+n0_));<br>                  // sanity check :  i = _node_id(_source[in_arc]) and j = _node_id(_target[in_arc]) --> returns true! yay! :)<br>                  findJoinNode();<br>                  bool change = findLeavingArc();<br>                  if (delta >= LEMON_MAX) return UNBOUNDED;<br><br></div><div>                  // if the amount of flow I want to initialise with is lower the total possible amount, then change = false<br></div><div>                  if(delta>initialValues_[i][j]){<br>                    change = false;<br>                  } else {<br>                    change = true;<br>                  }<br><br></div><div>                  // set delta = amount of flow I want to initialise with<br></div><div>                  delta = (double)initialValues_[i][j];<br><br>                  changeFlow(change);<br>                  if (change) {<br>                      updateTreeStructure();<br>                      updatePotential();<br>                  }<br>                }<br>                }<br>              }<br>            }<br>            <br>// END EDIT<br>          <br>            PivotRuleImpl pivot(*this);<br><br>            if (!initialPivots()) return UNBOUNDED;<br>            <br>            // Execute the Network Simplex algorithm<br>            while (pivot.findEnteringArc()) {<br>                findJoinNode();<br>                bool change = findLeavingArc();<br>                if (delta >= LEMON_MAX) return UNBOUNDED;<br>                changeFlow(change);<br>                if (change) {<br>                    updateTreeStructure();<br>                    updatePotential();<br>                }   [...]<br><br><br></div><div>After my "edit", I get that the artificial arcs have 0 flow (which is normal).<br><br></div><div>I have tried initialising it to the optimal solution, and I still get iterations in the while loop of the execution (i.e. pivot.findEnteringArc() is true and change is true) and I can't quite figure out why.<br><br></div><div>If anyone knows the solution or has any appropriate direction of inquiry, it would be much appreciated!<br><br></div><div>Cheers,<br><br></div><div>Matthew<br></div></div>