Problem Stmt: Suppose you have a graph $G$ with edges $E$ and nodes $V$. The nodes have ${x,y,z}$ coordinates in 3D Cartesian space. Assuming each node contains an $x$ amount of material, the idea is to remove those materials through one or more exit nodes. The only way one could remove the material is to orient the outgoing edge of that node to the gravity direction vector $\hat{g}=(0,0,-1)$. At the end of the iteration, there should be zero material present. By the way, one iteration is when you change the graph orientation and update the weights.

Just to make things clear: By orientation, I mean the edge vector's orientation with respect to the gravity vector $\hat{g}$. Also, the graph is a directed graph.

Question: Is there a graph-based algorithm for maximizing flow through a graph based on its edge orientation?

  • $\begingroup$ Can you clarify the problem statement? I don't understand exactly what you mean. $\endgroup$
    – Neal Young
    Jul 5, 2022 at 13:53
  • $\begingroup$ Sure, this was my first stack exchange question. Sorry for being vague! I just want to find a sequence of rotations of the graph such that all the flow (you can assume a water) will escape through a user-specified node (exit node) along the graph edges (flow path). I hope this is a bit more clear. A flow happens only when the path is aligned to the gravity direction (you can image a pipe - horizontal vs vertical). It is gravity-assisted flow only, no external force (such as a pump) to push the flow. $\endgroup$
    – Vysakh
    Jul 5, 2022 at 15:00
  • $\begingroup$ Actually, I still don't understand what exactly happens in each iteration. I guess each edge $(u, w)$ is given an orientation $u\rightarrow w$ or $w\rightarrow u$. The nodes of the graph have some "flow" on them (with initial flows given as part of the input). Then, in each iteration, the node flows are somehow updated according to the orientations? But how? E.g. what if a node $u$ has some flow on it, and has several outgoing edges that are oriented out of $u$ in that iteration? In a single iteration, can flow travel across more than one edge? A sequence of edges? Etc. $\endgroup$
    – Neal Young
    Jul 5, 2022 at 15:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.