You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Tomasz Skutnik <To...@e-point.pl> on 2003/07/23 12:58:09 UTC
Graph2 DFS patch
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi!
Here's patch against HEAD version of DFS algorithm in
jakarta-commons-sandbox/graph2 package - it uses less memory, which is
important for very large graphs (as in my case). Additionally DFS now
can use lazy graph implementations without causing full, in-memory
vertex retrieval on search initialization.
All existing tests passed.
I've modified only org.apache.commons.graph.algorithm.search version,
didn't touch org.apache.commons.graph.search one - is it still used?
Whever responsible, please apply.
Scooter
- --
Tomasz Skutnik, R&D Director, www.e-point.pl
tel +48 (22) 853 48 30, mob +48 501 555 705, fax +48 (22) 853 48 30
e-point S.A., ul. Filona 16, 02-658 Warsaw, Poland
PGP/GPG public key: http://scooter.ext.e-point.pl/tomasz.skutnik.gpg
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQE/Hmo6ZH/nE/TPGGQRAso8AJ9YNfI8gOEbiIKKyp/DxVW60wj7UQCeLmlb
wwC3K22vkyCC+qOVYu9sj8A=
=h+1P
-----END PGP SIGNATURE-----
Re: Graph2 DFS patch
Posted by David Dixon-Peugh <di...@yahoo.com>.
Done. Thanks.
--- Tomasz Skutnik <To...@e-point.pl> wrote:
> David Dixon-Peugh wrote:
> > Scooter,
> >
> > I didn't see the patch in your email. Can you
> send
> > it again?
> >
>
> Sorry, something strange happend... I'll try
> unsigned, not compressed
> version.
>
> > Also, it turns out there are no DFS tests in the
> > project. (It is still in the sandbox after all.)
> > If you provide one, you will have our undying
> > grattitude.
>
> I don't have any DFS test written, however few tests
> in graph2 use it
> indirectly (e.g. AcyclicContractTest and
> DependencyTest), so it should
> be enough. I don't think I'll find some more time to
> write dedicated
> test for it.
>
>
>
> --
>
> Tomasz Skutnik, R&D Director, www.e-point.pl
> tel +48 (22) 853 48 30, mob +48 501 555 705, fax +48
> (22) 853 48 30
> e-point S.A., ul. Filona 16, 02-658 Warsaw, Poland
> PGP/GPG public key:
> http://scooter.ext.e-point.pl/tomasz.skutnik.gpg
> > Index:
>
src/java/org/apache/commons/graph/algorithm/search/DFS.java
>
===================================================================
> RCS file:
>
/home/cvspublic/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java,v
> retrieving revision 1.3
> diff -u -r1.3 DFS.java
> ---
>
src/java/org/apache/commons/graph/algorithm/search/DFS.java
> 1 Jan 2003 02:19:02 -0000 1.3
> +++
>
src/java/org/apache/commons/graph/algorithm/search/DFS.java
> 23 Jul 2003 10:37:53 -0000
> @@ -94,7 +94,8 @@
> */
> public String getColor(Vertex v)
> {
> - return (String) colors.get(v);
> + String color = (String)colors.get(v);
> + return color != null ? color : WHITE;
> }
>
>
> @@ -109,7 +110,7 @@
>
> Vertex v = graph.getTarget(e);
>
> - if (colors.get(v) == WHITE)
> + if (getColor(v) == WHITE)
> {
> visitVertex(graph, v, visitor);
> }
> @@ -124,7 +125,6 @@
> Vertex v,
> Visitor visitor)
> {
> - colors.remove(v);
> colors.put(v, GRAY);
>
> visitor.discoverVertex(v);
> @@ -138,7 +138,6 @@
>
> visitor.finishVertex(v);
>
> - colors.remove(v);
> colors.put(v, BLACK);
> }
>
> @@ -149,12 +148,7 @@
> Vertex root,
> Visitor visitor)
> {
> - Iterator vertices =
> graph.getVertices().iterator();
> - while (vertices.hasNext())
> - {
> - colors.put(vertices.next(), WHITE);
> - }
> -
> + colors.clear();
> visitor.discoverGraph(graph);
>
> visitVertex(graph, root, visitor);
> @@ -165,24 +159,21 @@
> /**
> * visit - Visits all nodes in the graph.
> */
> - public void visit( DirectedGraph graph, Visitor
> visitor ) {
> - Iterator vertices =
> graph.getVertices().iterator();
> - while (vertices.hasNext()) {
> - colors.put( vertices.next(), WHITE );
> - }
> -
> - visitor.discoverGraph( graph );
> + public void visit( DirectedGraph graph, Visitor
> visitor )
> + {
> + colors.clear();
> + visitor.discoverGraph( graph );
>
> - vertices = graph.getVertices().iterator();
> - while (vertices.hasNext()) {
> - Vertex v = (Vertex) vertices.next();
> -
> - if (colors.get( v ) == WHITE) {
> - visitVertex( graph, v, visitor );
> - }
> - }
> + Iterator vertices =
> graph.getVertices().iterator();
> + while (vertices.hasNext()) {
> + Vertex v = (Vertex) vertices.next();
> +
> + if (getColor( v ) == WHITE) {
> + visitVertex( graph, v, visitor );
> + }
> + }
>
> - visitor.finishGraph( graph );
> + visitor.finishGraph( graph );
> }
> }
>
>
> >
---------------------------------------------------------------------
> To unsubscribe, e-mail:
> commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail:
commons-dev-help@jakarta.apache.org
__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: Graph2 DFS patch
Posted by Tomasz Skutnik <To...@e-point.pl>.
David Dixon-Peugh wrote:
> Scooter,
>
> I didn't see the patch in your email. Can you send
> it again?
>
Sorry, something strange happend... I'll try unsigned, not compressed
version.
> Also, it turns out there are no DFS tests in the
> project. (It is still in the sandbox after all.)
> If you provide one, you will have our undying
> grattitude.
I don't have any DFS test written, however few tests in graph2 use it
indirectly (e.g. AcyclicContractTest and DependencyTest), so it should
be enough. I don't think I'll find some more time to write dedicated
test for it.
--
Tomasz Skutnik, R&D Director, www.e-point.pl
tel +48 (22) 853 48 30, mob +48 501 555 705, fax +48 (22) 853 48 30
e-point S.A., ul. Filona 16, 02-658 Warsaw, Poland
PGP/GPG public key: http://scooter.ext.e-point.pl/tomasz.skutnik.gpg
Re: Graph2 DFS patch
Posted by David Dixon-Peugh <di...@yahoo.com>.
Scooter,
I didn't see the patch in your email. Can you send
it again?
Also, it turns out there are no DFS tests in the
project. (It is still in the sandbox after all.)
If you provide one, you will have our undying
grattitude.
Thanks,
DDP
--- Tomasz Skutnik <To...@e-point.pl> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi!
>
> Here's patch against HEAD version of DFS algorithm
> in
> jakarta-commons-sandbox/graph2 package - it uses
> less memory, which is
> important for very large graphs (as in my case).
> Additionally DFS now
> can use lazy graph implementations without causing
> full, in-memory
> vertex retrieval on search initialization.
>
> All existing tests passed.
>
> I've modified only
> org.apache.commons.graph.algorithm.search version,
> didn't touch org.apache.commons.graph.search one -
> is it still used?
> Whever responsible, please apply.
>
> Scooter
>
> - --
>
> Tomasz Skutnik, R&D Director, www.e-point.pl
> tel +48 (22) 853 48 30, mob +48 501 555 705, fax +48
> (22) 853 48 30
> e-point S.A., ul. Filona 16, 02-658 Warsaw, Poland
> PGP/GPG public key:
> http://scooter.ext.e-point.pl/tomasz.skutnik.gpg
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.2 (GNU/Linux)
> Comment: Using GnuPG with Mozilla -
> http://enigmail.mozdev.org
>
>
iD8DBQE/Hmo6ZH/nE/TPGGQRAso8AJ9YNfI8gOEbiIKKyp/DxVW60wj7UQCeLmlb
> wwC3K22vkyCC+qOVYu9sj8A=
> =h+1P
> -----END PGP SIGNATURE-----
>
> >
---------------------------------------------------------------------
> To unsubscribe, e-mail:
> commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail:
commons-dev-help@jakarta.apache.org
__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org