Struct BlocksInfo

struct BlocksInfo {
    id: BlockId,
    succs: BTreeSet<BlockWithRank<usize>>,
    flow: BTreeSet<BlockWithRank<(BigRational, isize)>>,
}

Information used to compute the switch exits. We compute this information for every block in the graph. Note that we make sure to use immutable sets because we rely a lot on cloning.

Fields

id: BlockId

succs: BTreeSet<BlockWithRank<usize>>

All the successors of the block

flow: BTreeSet<BlockWithRank<(BigRational, isize)>>

Let’s say we put a quantity of water equal to 1 on the block, and the water flows downards. Whenever there is a branching, the quantity of water gets equally divided between the branches. When the control flows join, we put the water back together. The set below computes the amount of water received by each descendant of the node.

TODO: there must be a known algorithm which computes this, right?… This is exactly this problems: https://stackoverflow.com/questions/78221666/algorithm-for-total-flow-through-weighted-directed-acyclic-graph TODO: the way I compute this is not efficient.

Remark: in order to rank the nodes, we also use the negation of the rank given by the topological order. The last elements of the set have the highest flow, that is they are the nodes to which the maximum number of paths converge. If several nodes have the same flow, we want to take the highest one in the hierarchy: hence the use of the inverse of the topological rank.

Ex.:

A  -- we start here
|
|---------------------------------------
|            |            |            |
B:(0.25,-1)  C:(0.25,-2)  D:(0.25,-3)  E:(0.25,-4)
|            |            |
|--------------------------
|
F:(0.75,-5)
|
|
G:(0.75,-6)

The “best” node (with the highest (flow, rank) in the graph above is F.

Trait Implementations

impl Clone for BlocksInfo

fn clone(&self) -> BlocksInfo

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BlocksInfo

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.