Yes, I have noticed this issue when I was trying to implement it today. The iterator should be able to run more than once. Keep a copy of incomingEdges Map within the iterator class would be good solution?
Thanks, Lang On Fri, Apr 23, 2010 at 10:11 AM, Alexei Fedotov <alexei.fedo...@gmail.com>wrote: > As for particalr algortithm, I like the idea to forget about the list > and return the iterator - that makes logic simpler. I'm not sure the > logic calculating incoming edges is correct. Would the iterator work > more than once? It would reduce incoming node caunts to zero on the > first run, wouldn't it? > > -- > With best regards / с наилучшими пожеланиями, > Alexei Fedotov / Алексей Федотов, > http://www.telecom-express.ru/ > http://harmony.apache.org/ > http://dataved.ru/ http://klsh.ru/ > > > > > On Fri, Apr 23, 2010 at 5:44 PM, Alexei Fedotov > <alexei.fedo...@gmail.com> wrote: > > Well, I don't mind using the algorithm from wiki. Why I have asked > > all that questions? > > > > The actual complexity depends on the typical use case. For example, if > > no algoritms intend to use setOrdeirng(), then no sorting is required. > > > > If we have small number of setOrdering() calls, then we can just keep > > the list of providers sorted after each setOrdering() call, thus no > > cache would be needed. > > > > > > > > -- > > With best regards / с наилучшими пожеланиями, > > Alexei Fedotov / Алексей Федотов, > > http://www.telecom-express.ru/ > > http://harmony.apache.org/ > > http://dataved.ru/ http://klsh.ru/ > > > > > > > > > > On Fri, Apr 23, 2010 at 5:01 PM, Alexei Fedotov > > <alexei.fedo...@gmail.com> wrote: > >> Lang, > >> 1. Could you please describe a scenario when setOrdering() would be > >> called? Currently there are no examples in the code base [1], are > >> they? > >> > >> 2. Any request to getServiceProviders() returns a list, not a graph. > >> Even if two elements are not comparable, the function will return them > >> in some order. Could the list collection be sufficient to handle > >> complexity of the task? > >> > >> [1] > http://www.google.com/codesearch?hl=ru&lr=&q=setOrdering&exact_package=http://svn.apache.org/repos/asf/harmony/enhanced/classlib/trunk > >> > >> > >> -- > >> With best regards / с наилучшими пожеланиями, > >> Alexei Fedotov / Алексей Федотов, > >> http://www.telecom-express.ru/ > >> http://harmony.apache.org/ > >> http://dataved.ru/ http://klsh.ru/ > >> > >> > >> > >> On Fri, Apr 23, 2010 at 9:05 AM, Lang Yang <yangl...@gmail.com> wrote: > >>> > >>> Hello Alexei, > >>> Thanks for those suggestions. I have been busy these few days as this > semester is ending in these two weeks in Canada. > >>> From description of setOrdering and unsetOrdering methods, we have to > save all the preferences between two objects in order to tell these > functions whether a preference is set or not. I don't think there's > something I could re-use directly. So, I am thinking of use Map to store the > preferences. And still stick with this Topological Sorting algorithm. > >>> I agree with the second idea, cache the sorting result. Every time when > getServiceProviders() is called, check if there was any change made. If > there was, performance the sorting function again, if there wasn't, just > return the cached result. > >>> I will implement this idea in few days, and post updates to this > mailing list. > >>> Kind Regards, > >>> Lang > >>> > >>> On Mon, Apr 19, 2010 at 6:53 AM, Alexei Fedotov < > alexei.fedo...@gmail.com> wrote: > >>>> > >>>> Lang, > >>>> Thanks for the nice contribution! > >>>> 1. Can we re-use any other JDK classes to implement service ordering? > Maybe some collection method can do? > >>>> 2. I don't think we need the whole set of providers to be sorted. > Ordering is used to answer getServiceProviders() > >>>> Maybe finding out this particular answer and cache it until the next > registration/reordering would suffice? > >>>> > >>>> -- > >>>> With best regards / с наилучшими пожеланиями, > >>>> Alexei Fedotov / Алексей Федотов, > >>>> http://www.telecom-express.ru/ > >>>> http://harmony.apache.org/ > >>>> http://dataved.ru/ http://klsh.ru/ > >>>> > >>>> > >>>> > >>>> On Fri, Apr 16, 2010 at 10:21 AM, Lang Yang <yangl...@gmail.com> > wrote: > >>>>> > >>>>> 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<Object> outgoingNodes; // all the outgoing nodes > >>>>> private Object provider; > >>>>> > >>>>> public ProviderNode(Object provider) { > >>>>> incomingEdges = 0; > >>>>> outgoingNodes = new HashSet<Object>(); > >>>>> this.provider = provider; > >>>>> } > >>>>> > >>>>> public Object getProvider() ; > >>>>> public Iterator getOutgoingNodes(); > >>>>> public boolean addOutEdge(Object provider); > >>>>> public boolean removeOutEdge(Object provider); > >>>>> public void addInEdge(); > >>>>> public void removeInEdge(); > >>>>> public int getIncomingEdges(); > >>>>> public boolean contains(Object provider); > >>>>> } > >>>>> And we also need to add some fields and methods to ProviderMap class > (this class stores SPIs within given category): > >>>>> private static class ProvidersMap { > >>>>> // create a ProviderNode for each service provider > >>>>> Map<Object, ProviderNode> nodeMap = new HashMap<Object, > ProviderNode>(); > >>>>> > >>>>> public boolean setOrdering(Object firstProvider, Object > secondProvider) { > >>>>> ProviderNode firstNode = nodeMap.get(firstProvider); > >>>>> ProviderNode secondNode = nodeMap.get(secondProvider); > >>>>> > >>>>> // if the ordering is already set, return false > >>>>> if (firstNode.contains(secondProvider)) { > >>>>> return false; > >>>>> } > >>>>> > >>>>> // put secondProvider into firstProvider's outgoing nodes > list > >>>>> firstNode.addOutEdge(secondProvider); > >>>>> // increase secondNode's incoming edge by 1 > >>>>> secondNode.addInEdge(); > >>>>> > >>>>> return true; > >>>>> } > >>>>> > >>>>> public boolean unsetOrdering(Object firstProvider, Object > secondProvider) { > >>>>> ProviderNode firstNode = nodeMap.get(firstProvider); > >>>>> ProviderNode secondNode = nodeMap.get(secondProvider); > >>>>> > >>>>> // if the ordering is not set, return false > >>>>> if (!firstNode.contains(secondProvider)) { > >>>>> return false; > >>>>> } > >>>>> > >>>>> // remove secondProvider from firstProvider's outgoing nodes > list > >>>>> firstNode.removeOutEdge(secondProvider); > >>>>> // decrease secondNode's incoming edge by 1 > >>>>> secondNode.removeInEdge(); > >>>>> > >>>>> return true; > >>>>> } > >>>>> } > >>>>> There is also an Iterator for ordered list, this basically > implemented sorting part of Topological Sorting: > >>>>> private static class OrderedProviderIterator implements Iterator { > >>>>> // store nodes which has 0 incoming edge > >>>>> private List<ProviderNode> emptyList = new > ArrayList<ProviderNode>(); > >>>>> > >>>>> public OrderedProviderIterator(Iterator it) { > >>>>> // find all the nodes that with 0 incoming edge > >>>>> while (it.hasNext()) { > >>>>> ProviderNode node = (ProviderNode)it.next(); > >>>>> if (node.getIncomingEdges()==0) { > >>>>> emptyList.add(node); > >>>>> } > >>>>> } > >>>>> } > >>>>> > >>>>> public boolean hasNext() { > >>>>> return !emptyList.isEmpty(); > >>>>> } > >>>>> public Object next() { > >>>>> if (emptyList.isEmpty()) { > >>>>> throw new NoSuchElementException(); > >>>>> } > >>>>> // get the first node from emptyList > >>>>> ProviderNode node = emptyList.get(0); > >>>>> // find all the outgoing nodes > >>>>> Iterator it = node.getOutgoingNodes(); > >>>>> while (it.hasNext()) { > >>>>> ProviderNode outNode = (ProviderNode) it.next(); > >>>>> // remove the incoming edge from the node. > >>>>> outNode.removeInEdge(); > >>>>> // add to the emptyList if this node's incoming edge is equal to 0 > >>>>> if (outNode.getIncomingEdges() == 0) { > >>>>> emptyList.add(outNode); > >>>>> } > >>>>> } > >>>>> return node.getProvider(); > >>>>> } > >>>>> public void remove() { > >>>>> throw new UnsupportedOperationException(); > >>>>> } > >>>>> > >>>>> } > >>>>> This is just my thought, I haven’t tested it yet. I don’t know if > there anything I need to re-do or improve? Please let me know your opinion. > >>>>> Thank you, > >>>>> Lang > >>>>> [1]: http://en.wikipedia.org/wiki/Directed_acyclic_graph > >>>>> [2]: http://en.wikipedia.org/wiki/Topological_sorting > >>>> > >>> > >> > > >
