Hi Francis, have no direct clue on how to solve the algo without holding the nodes in memory in order to track progress. Not a nice one. Any algo expert around here to have a better solution?
Cheers, /peter neubauer COO and Sales, Neo Technology GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://www.tinkerpop.com - Processing for Internet-scale graphs. http://www.thoughtmade.com - Scandinavias coolest Bring-a-Thing party. 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 > _______________________________________________ Neo mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
