Say you have a directed acyclic graph. Any node can have a colour or colours. The colours a node has are weighted -- e.g. a node which is only red has red with weight 1; a node with highly weighted red and less green might have 0.8 red and 0.2 green. I'm treating the weights as if they must sum to 1, but that isn't compulsory.
Any node which has no incoming edges (a source) has a single colour with total weight (e.g. red with weight 1).
Here's my question: I want to calculate the colours and weights of each non-source node as a function of the colors of the sources it is connected to. Sources which are further away from a given node (i.e. where there are more intervening non-source nodes on the path) should 'contribute' proportionally less. So in the following graph (where nodes with "..." represent some long path of intermediate nodes, with no branches):
If A has red with weight 1, and B green 1, then:
- D and F should both have red 1 (in both cases the only contribution is A)
- C should have red 0.5, green 0.5 (equal contributions from A and B, since they're the same distance away)
- E should have a higher weighting for red than green (proportional to the difference between the length of the of the AE path (1 -- single edge) compared with that of the BE path).
How should the colours and weights of these non-source nodes be calculated? I've played around a bit with this and can't find an obvious (to me) solution.
Apologies if this very simple -- I'm not a mathematician. I'm building a simple model of inherited reference in language and I want to gesture at how it might be formalised. This graph theory part helps me deal with cases where a later use of a term (the non-source nodes) is grounded in more than one distinct earlier use (different-coloured sources).
Thanks in advance!
I believe the following would give you want you want, but note that there are many similar ways you could weight nodes based on distance.
Let say we want to color a non-source node $x$. Let us compute the shortest path from every source $s_i$ to node $x$. Let $l_i$ be the length of such an $s_ix$ path, and $c_i$ the color of $s_i$. You could give the weight $\frac{1}{l_i}c_i$ to $x$ (you could also normalize this so that the sum of all weights equals $1$). You could also have some other decreasing function of $l_i$ such as $f(l_i) = \frac{1}{l_i^2}$. This proportionally favors closer sinks that the linear function previously described.
A potential issue that both of the above do not tackle is that you can have multiple paths from a source to a non-source (for instance if you add the are $(D, E)$ in your picture). Should vertices which can be reached multiple ways from $s_i$ have a larger contribution of $c_i$? If so you could count all paths, or perhaps all internally disjoint paths (meaning paths that do not share arcs). These are just some ideas, hope this helps!