Hi, Sorry for the much delayed response.
First a disclaimer: Neo4j makes no claim to magically make P=NP (the problem of finding a minimal dominating set is NP-hard), it would be cool if Neo4j could be used to prove such a thing, but I am not going to spend the rest of my life attempting it. I would suggest that you try to find a small dominating set rather than the minimal dominating set. Even then I cant think of a solution that doesn't require having all Nodes sorted by their degree in memory. If you want to do this with the kind of numbers of Nodes we consider normal (from several millions to billions), you would run into a lot of trouble. The code you have written looks like it might instantiate the collections you use for storing your result multiple times. But I cant tell without the full source code. Cheers, Tobias On Sun, Mar 28, 2010 at 3:01 PM, francis adediran <adedi...@gmail.com>wrote: > Hi, > I have been trying to solve the problem of minimal dominating set > using Neo4j but to no avail. The algorithm > to solve this problem is correct but implementing it using Neo4j is > becoming a pain or maybe i'm not yet familiar > with Neo as i thought i was. > > The minimal dominating set in a graph is a set of nodes such that > every node in the network graph > is a neighbor of at least one element of the set. In social networking > terms, they are the set of people > who collectively are friends with every one in the network. > More info on dominating set here > http://en.wikipedia.org/wiki/Dominating_set > so for example,given this bi-directional graph network > A > \ > \ > B > / \ > / \ > C D > \ / > E > B and C are the minimal dominating set. Also,the sets {B,E} and {B,D} > are possible candidates depending on > your algorithm. but the most important thing to get a set with minimal > number of nodes > > the best algorithm know so far, is Chvatal algorithm. it basically > selects the node > which brings the most new nodes into the dominated set. > In our graph above, the dominating set S is {B,C) and dominated set V > is{A,D,E} > B is selected because it brings in A,C and D > C is selected because it brings in E > > The dominating set can be useful to marketers and even spammers as it > provide an indirect way to reach an entire network > > I've tried implementing this in Neo4j,but the problem is since we need > to keep track of the dominating and dominated sets > neo4j keeps re-instantiating them in the Returnable Evaluator while > traversing the network > is there a better way to do this Neo4j? > > Traverser friendsTraverser = startNode.traverse(Order.BREADTH_FIRST, > > StopEvaluator.END_OF_GRAPH, > new > myReturnableEvaluator(){ > private ArrayList <Node> DM = new ArrayList<Node>(); > //Dominating set > private ArrayList <Node> V = new ArrayList<Node>(); //dominated set > @Override > public boolean isReturnableNode(TraversalPosition pos) { > int > numberof_new_users=this.getNodesDegree(pos.currentNode()); > if(!(DM.isEmpty())) > { > //get node's conns > Iterable<Relationship> relationships = > pos.currentNode().getRelationships(Direction.OUTGOING); > //get all there end nodes > for(Relationship r:relationships) > { > Node end = r.getEndNode(); > ..... > _______________________________________________ > Neo mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Tobias Ivarsson <tobias.ivars...@neotechnology.com> Hacker, Neo Technology www.neotechnology.com Cellphone: +46 706 534857 _______________________________________________ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
