Jacopo, do you have the source for this available somewhere? It's hard to judge anything from the class files ...
Cheers, /peter neubauer 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://startupbootcamp.org/ - Öresund - Innovation happens HERE. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Wed, Mar 30, 2011 at 5:48 PM, Jacopo <jacopo.far...@email.it> wrote: > Ok, I wrote a class to do the work without changing the graph > http://dl.dropbox.com/u/7137905/SCC_neo4j_tarjan.jar > > It surely needs some improvements, for example it cannot manage too > large graphs (e.g. more than 10^6 nodes), but should work. > > A note: it looks for Strongly Connected Components, subsets of the graph > where any node can be reached by any other node of the set without going > out of the set itself. A SCC bigger than one node implies the existence > of at least one cycle. > > Cheers, > Jacopo > > P.S.: the code create a set of nodes called s, that is truncated when > it's sure it contains a SCC. Would be a good idea to remove > corresponding nodes from the maps indexes and lowlinks, since they will > never be used, in order to consume less memory. > > Il giorno mar, 29/03/2011 alle 10.19 +0200, Mattias Persson ha scritto: >> 2011/3/28 Jacopo <jacopo.far...@email.it> >> >> > Uh, I may create a node and use relationships with it instead of node >> > properties, to delete it after the work, but it doesn't sound a good >> > solution. >> > >> >> Letting a graph algorithm set temporary properties and creating other >> entities (thus holding write locks and memory) seems like a bad idead. Hold >> these things in a Set or Map instead. >> >> >> > Jacopo >> > Il giorno lun, 28/03/2011 alle 21.23 +0200, Jacopo ha scritto: >> > > There's no problem with it! >> > > The only issue is that it needs to add properties to visited nodes in >> > > order to be able to detect cycles. It's possible to delete them after >> > > the work, but in case the graph already uses that properties name or the >> > > program is interrupted before finishing it would be a problem. Is there >> > > a way to create temporary properties? >> > > >> > > Jacopo >> > > Il giorno lun, 28/03/2011 alle 10.16 +0200, Peter Neubauer ha scritto: >> > > > Cool! >> > > > >> > > > Would be great to maybe add this to the graph-algo package, if you >> > > > don't mind? Just fork and add it from >> > > > https://github.com/neo4j/graphdb/tree/master/graph-algo and do a merge >> > > > request ... >> > > > >> > > > Cheers, >> > > > >> > > > /peter neubauer >> > > > >> > > > 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://startupbootcamp.org/ - Öresund - Innovation happens HERE. >> > > > http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing >> > party. >> > > > >> > > > >> > > > >> > > > On Sun, Mar 27, 2011 at 10:56 PM, Jacopo <jacopo.far...@email.it> >> > wrote: >> > > > > In case you are interested, I implemented cycle detection by using >> > > > > Tarjan algorithm, not the traversal. >> > > > > The code is visible in the Italian Wikipedia, I hope it's >> > intelligible >> > > > > although the language. >> > > > > >> > http://it.wikipedia.org/wiki/Algoritmo_di_Tarjan_per_le_componenti_fortemente_connesse#Implementazione_in_Java >> > > > > >> > > > > >> > > > > Hi >> > > > > Jacopo Farina >> > > > > >> > > > > Il giorno ven, 25/03/2011 alle 13.51 +0100, Mattias Persson ha >> > scritto: >> > > > >> I think you could implement this using RELATIONSHIP_GLOBAL >> > uniqueness, like >> > > > >> (from the top of my head): >> > > > >> >> > > > >> Traversal.description().uniqueness( Uniqueness.RELATIONSHIP_GLOBAL >> > ) >> > > > >> .evaluator(new Evaluator() { >> > > > >> public Evaluation(Path path) { >> > > > >> return path.length() > 0 && >> > endNodeOccursPreviouslyInPath( >> > > > >> path ) ? >> > > > >> Evaluation.INCLUDE_AND_CONTINUE : >> > > > >> Evaluation.EXCLUDE_AND_CONTINUE; >> > > > >> } >> > > > >> >> > > > >> private boolean endNodeOccursPreviouslyInPath(Path path) { >> > > > >> Node endNode = path.endNode(); >> > > > >> int counter = 0; >> > > > >> for ( Node node : path.nodes() ) { >> > > > >> if ( counter++ < path.length() && node.equals( >> > endNode ) ) >> > > > >> return true; >> > > > >> } >> > > > >> return false; >> > > > >> } >> > > > >> } ).traverse(...); >> > > > >> >> > > > >> This should (if it even compiles :) ) return paths containing >> > cycles. >> > > > >> Something like this you're looking for? >> > > > >> >> > > > >> 2011/3/25 Wouter De Borger <w.debor...@gmail.com> >> > > > >> >> > > > >> > Hi all, >> > > > >> > >> > > > >> > I would like to detect all cycles in a traversal. >> > > > >> > >> > > > >> > I know the traversal framework has cycle avoidance built-in, but >> > there >> > > > >> > doesn't seem to be an API for cycle detection! >> > > > >> > >> > > > >> > Has anyone already implemented a cycle detector for traversals? >> > > > >> > >> > > > >> > Thanks in advance, >> > > > >> > Wouter >> > > > >> > _______________________________________________ >> > > > >> > Neo4j mailing list >> > > > >> > User@lists.neo4j.org >> > > > >> > https://lists.neo4j.org/mailman/listinfo/user >> > > > >> > >> > > > >> >> > > > >> >> > > > >> >> > > > > >> > > > > >> > > > > _______________________________________________ >> > > > > Neo4j mailing list >> > > > > User@lists.neo4j.org >> > > > > https://lists.neo4j.org/mailman/listinfo/user >> > > > > >> > > > _______________________________________________ >> > > > Neo4j mailing list >> > > > User@lists.neo4j.org >> > > > https://lists.neo4j.org/mailman/listinfo/user >> > > >> > > >> > > >> > > >> > > -- >> > > Caselle da 1GB, trasmetti allegati fino a 3GB e in piu' IMAP, POP3 e >> > SMTP autenticato? GRATIS solo con Email.it http://www.email.it/f >> > > >> > > Sponsor: >> > > A Pasqua scegli le offerte speciali di riccionefamilyhotels.it! >> > Animazione, parchi divertimento, escursioni, "caccia alluovo" >> > > Clicca qui: http://adv.email.it/cgi-bin/foclick.cgi?mid=11343&d=28-3 >> > > _______________________________________________ >> > > Neo4j mailing list >> > > User@lists.neo4j.org >> > > https://lists.neo4j.org/mailman/listinfo/user >> > >> > >> > >> > >> > -- >> > Caselle da 1GB, trasmetti allegati fino a 3GB e in piu' IMAP, POP3 e SMTP >> > autenticato? GRATIS solo con Email.it http://www.email.it/f >> > >> > Sponsor: >> > Miramare di Rimini - Hotel Due Mari 4 stelle, Prenota le Vacanze di Pasqua >> > entro il 30/3 >> > * con lo Speciale Sconto del 15%. Bimbi 0-4 anni Gratis; 5-14 Sconto 50%. >> > Clicca qui: http://adv.email.it/cgi-bin/foclick.cgi?mid=11354&d=28-3 >> > _______________________________________________ >> > Neo4j mailing list >> > User@lists.neo4j.org >> > https://lists.neo4j.org/mailman/listinfo/user >> > >> >> >> > > > _______________________________________________ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > _______________________________________________ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
