For a cyclic, undirected diagram of nodes with edges of indefinite length, where some of the nodes have known coordinates and others do not I want to write an algorithm (ultimately in Java, but I need the general algorithm first) to evenly place the non-localized nodes based on those around them with a known location.

For example:

```
A(0,0) -- B(?,?) -- C(2,0) -- D(?,?) -- E(?,?)
| |
| |
F(0,1) -- H(?,?) -- I(?,?) -- J(6,1)
| |
| |
G(?,?) K(2,6)
```

The (wrong) algorithm I currently have in pseudo Java is as follows:

```
getAveragePointForNode (Node node)
{
Pair summedLocations = getSummedLocationsAndCount(node,0,0,emptyList,0);
NodeLocation = (summedLocations.x/summedLocations.count, summedLocations.y/summedLocations.count);
}
getSummedLocationsAndCount(currentNode, currentX, currentY, visitedNodes)
{
If (visitedNodes.contains(currentNode))
{
return new Pair((currentX,currentY),1);
}
Else
{
visitedNodes.add(currentNode);
summedLocationsCount = 0;
If this node has a known location
{
return new Pair((currentX + currentNode.X,currentY + currentNode.Y),1);
}
Else, for each adjacent node:
{
If adjacent node has a known location
{
currentX += adjacentNode.X
currentY += adjacentNode.Y
summedLocationsCount++;
alreadyVisited.add(adjacentNode);
}
Else
{
Pair result = getSummedLocationsAndCount(adjacentNode, currentX, currentY, visitedNodes);
if (result.count > 0)
{
currentX += result.X
currentY += result.Y
summedLocationsCount += result.count
}
}
}
return new Pair((currentX,currentY),summedLocationsCount );
}
}
```

The problem with this algorithm is that it tends to make the first point halfway between the start and end, the second point halfway between this point and the start, etc. and you get a halving effect rather than evenly distributed points.

e.g. the above algorithm could give on a straight line

`P--Q----R---------S-----------------T`

rather than

`P--------Q--------R--------S--------T`