Menu

TODO: (top) assign dimensions to graph nodes

the basic algorithm to be implemented is as follows:

add int variable to nodes: sources_missing_dimensions.
add int variable to networks: inputs_missing_dimensions.

1. for each node, set # of sources that do not have complete internal dimensions assigned to number of sources (minus ones that are already assigned)
2. for each network, set # of inputs that do not have complete internal dimensions assigned.

then dimension assignment can be done recursively, in roughly O(N)+O(E) time (where n = number of nodes and e = number of edges):

when assigning internal dimensions to a node:
* decrement each sink's # of sources that do not have complete internal dimensions assigned
* if that brings the sink's count to 0:
* * if it is not a network input, assign internal dimensions to that node.
* * if it is a network input, also decrement that # of inputs that do not have complete internal dimensions assigned.
* * * if that brings the count to 0:
* * * * rename the dimensions of the network with the matching dimensions of its inputs, collect all remaining input dimensions into "extrinsic dimensions"
* * * * assign internal dimensions to all input nodes of that network.

3. assign dimensions to the entry network inputs. recursion should fill in the rest.

Posted by Kevin Baas 2010-08-18

Log in to post a comment.

Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.