Hello guys,
I mentioned that the ordering feature in ServiceRegistry is missing from
Harmony JDK on my GSoC proposal. I have been working on this in past few
days and come up with this rough idea. I don’t know if this way works or
not, I need your input ;)
So, the background is that user can have several SPIs in certain category.
Sometime they would also like to set preferences for those SPIs. Preference
is always set in pairwise. With ordering feature enabled, when user gets
service providers, the results should be in order (respect all the
preferences that set by user).
Because the preference is set in pairwise, I think this problem could be
treated as Directed Acyclic Graph (DAG) [1] ordering problem: SPIs would be
vertices and pairwise preferences would be directed edges that connect two
SPIs. Topological Sorting algorithm would be implemented for DAG sorting
issue (this is the easiest one?).
I had looked up in Wikipedia and got the detailed steps for Topological
Sorting [2]:
First, find a list of "start nodes" which have no incoming edges and insert
them into a set S; at least one such node must exist if graph is acyclic.
Then:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
output error message (graph has at least one cycle)
else
output message (proposed topologically sorted order: L)
So, I guess for each service providers, we need to store at least two
things: the number of incoming edges, and outgoing nodes. I came up with a
class like this:
private static class ProviderNode {
private int incomingEdges; // number of incoming edges
private Set