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
