commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From d...@apache.org
Subject cvs commit: jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/decorator DDirectedGraph.java
Date Wed, 01 Jan 2003 02:19:03 GMT
dion        2002/12/31 18:19:03

  Modified:    graph2/src/java/org/apache/commons/graph/domain/uml
                        StateMachineFactory.java ModelFactory.java
               graph2/src/java/org/apache/commons/graph/algorithm/dataflow
                        DataFlowSolutions.java
               graph2/src/java/org/apache/commons/graph/algorithm/search
                        CostSearch.java DFS.java
               graph2/src/java/org/apache/commons/graph/domain/dependency/exception
                        CircularDependencyException.java
               graph2/src/java/org/apache/commons/graph WeightedGraph.java
               graph2/src/java/org/apache/commons/graph/domain/statemachine/exception
                        StateMachineException.java
               graph2/src/java/org/apache/commons/graph/domain/statemachine
                        StateMachine.java
               graph2/src/java/org/apache/commons/graph/domain/dependency
                        DependencyGraph.java
               graph2/src/java/org/apache/commons/graph/search
                        CostSearch.java DFS.java
               graph2/src/java/org/apache/commons/graph/decorator
                        DDirectedGraph.java
  Log:
  Clean up code/fix compile errors
  
  Revision  Changes    Path
  1.2       +237 -232  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/uml/StateMachineFactory.java
  
  Index: StateMachineFactory.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/uml/StateMachineFactory.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- StateMachineFactory.java	8 May 2002 17:43:20 -0000	1.1
  +++ StateMachineFactory.java	1 Jan 2003 02:19:02 -0000	1.2
  @@ -1,232 +1,237 @@
  -package org.apache.commons.graph.domain.uml;
  -
  -/**
  - * StateMachineFactory This class will build a State Machine from an NSUML Model
  - * which can be used for testing.
  - */
  -
  -import java.util.Set;
  -import java.util.Map;
  -import java.util.HashSet;
  -import java.util.HashMap;
  -import java.util.Iterator;
  -
  -import org.apache.commons.graph.domain.uml.exception.*;
  -
  -import org.apache.log4j.Category;
  -
  -import org.apache.commons.graph.exception.*;
  -import org.apache.commons.graph.domain.statemachine.*;
  -
  -import ru.novosoft.uml.foundation.data_types.*;
  -import ru.novosoft.uml.model_management.MModel;
  -import ru.novosoft.uml.foundation.core.*;
  -import ru.novosoft.uml.behavior.state_machines.*;
  -import ru.novosoft.uml.behavior.common_behavior.*;
  -
  -/**
  - * Description of the Class
  - */
  -public class StateMachineFactory
  -{
  -    private static Category log =
  -        Category.getInstance(org.apache.commons.graph.domain.uml.StateMachineFactory.class);
  -
  -    private MModel extent = null;
  -
  -    private Map stateNames = new HashMap();// MSTATEVERTEX X NAME
  -
  -    /**
  -     * Constructor for the StateMachineFactory object
  -     *
  -     * @param extent
  -     */
  -    public StateMachineFactory(MModel extent)
  -    {
  -        this.extent = extent;
  -    }
  -
  -    /**
  -     * Gets the name attribute of the StateMachineFactory object
  -     */
  -    private String getName(String namespace, MStateVertex msv)
  -    {
  -        if (msv.getName() != null)
  -        {
  -            return namespace + "/" + msv.getName();
  -        }
  -
  -        if (msv instanceof MPseudostate)
  -        {
  -            return namespace + "/_" +
  -                ((MPseudostate) msv).getKind().getName() + "_";
  -        }
  -
  -        if (msv instanceof MFinalState)
  -        {
  -            return namespace + "/_final_";
  -        }
  -
  -        return namespace + "/_unknown_";
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    private StateMachine makeStateMachine(String namespace,
  -                                          MCompositeState mcs)
  -        throws GraphException
  -    {
  -        log.debug("makeStateMachine(" + getName(namespace, mcs) + "): Entry");
  -        StateMachine RC = new StateMachine(namespace);
  -
  -        // Step 1 - Add States to the State Machine
  -        Iterator states =
  -            mcs.getSubvertices().iterator();
  -
  -        while (states.hasNext())
  -        {
  -            MStateVertex msv =
  -                (MStateVertex) states.next();
  -
  -            RC.addState(getName(namespace, msv));
  -
  -            stateNames.put(msv, getName(namespace, msv));
  -
  -            if (msv instanceof MPseudostate)
  -            {
  -                if (((MPseudostate) msv).getKind() ==
  -                    MPseudostateKind.INITIAL)
  -                {
  -                    RC.setStartState(RC.getState(getName(namespace, msv)));
  -                }
  -            }
  -
  -            if (msv instanceof MCompositeState)
  -            {
  -                StateMachine ssm = makeStateMachine(getName(namespace, msv),
  -                    (MCompositeState) msv);
  -                RC.getState(getName(namespace, msv)).setSubmachine(ssm);
  -            }
  -
  -            if (msv instanceof MFinalState)
  -            {
  -                RC.addFinalState(RC.getState(getName(namespace, msv)));
  -            }
  -        }
  -
  -        // Step 2 - Add Transitions to State Machine
  -        states = mcs.getSubvertices().iterator();
  -        while (states.hasNext())
  -        {
  -            MStateVertex msv = (MStateVertex) states.next();
  -            String msvName = getName(namespace, msv);
  -
  -            Iterator transes =
  -                msv.getIncomings().iterator();
  -            while (transes.hasNext())
  -            {
  -                MTransition trans =
  -                    (MTransition) transes.next();
  -                MEvent trigger = trans.getTrigger();
  -		MGuard guard = trans.getGuard();
  -
  -                String trigStr = null;
  -		String guardStr = null;
  -
  -		if (guard != null) {
  -		  guardStr = guard.getName();
  -		}
  -
  -                if (trigger != null)
  -                {
  -                    trigStr = trigger.getName();
  -                }
  -                else
  -                {
  -                    trigStr = Transition.EPSILON;
  -                }
  -
  -                String sourceName =
  -                    (String) stateNames.get(trans.getSource());
  -                String targetName =
  -                    (String) stateNames.get(trans.getTarget());
  -	       
  -                State source = RC.getState(sourceName);
  -                State target = RC.getState(targetName);
  -
  -		String transName = source + "-" + target + "/" + trigStr;
  -		if (guardStr != null) {
  -		  transName = transName + "[" + guardStr + "]";
  -		}
  -
  -                Transition tranx =
  -                    new Transition(transName,
  -                    source, target);
  -		tranx.setTrigger( trigStr );
  -		tranx.setGuard( guardStr );
  -
  -                RC.addTransition(tranx);
  -            }
  -        }
  -
  -        log.debug("makeStateMachine(" + getName(namespace, mcs) + "): Exit");
  -        return RC;
  -    }
  -
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public StateMachine makeStateMachine(String selector)
  -        throws GraphException, ModelNotFoundException
  -    {
  -        log.debug("makeStateMachine(" + selector + "):Enter");
  -        MStateMachine model = null;
  -        StateMachine RC = null;
  -
  -        Iterator owned =
  -            extent.getOwnedElements().iterator();
  -
  -        while (owned.hasNext())
  -        {
  -            Object next = owned.next();
  -            if (next instanceof
  -                ru.novosoft.uml.foundation.core.MClass)
  -            {
  -                MClass mClass = (MClass) next;
  -
  -                if (selector.equals(mClass.getName()))
  -                {
  -                    Iterator machines = mClass.getBehaviors().iterator();
  -                    if (machines.hasNext())
  -                    {
  -                        model = (MStateMachine) machines.next();
  -                        log.info("StateMachine Found: " + model);
  -                    }
  -                }
  -            }
  -        }
  -
  -        if (model == null)
  -        {
  -            throw new ModelNotFoundException("Cannot find StateMachine for " +
  -                selector);
  -        }
  -
  -        MState top = model.getTop();
  -        if (top instanceof MCompositeState)
  -        {
  -            RC = makeStateMachine(selector,
  -                (MCompositeState) top);
  -        }
  -        else
  -        {
  -            throw new ModelNotFoundException("Expecting CompositeState at top.");
  -        }
  -
  -        log.debug("makeStateMachine(" + selector + "):Exit");
  -        return RC;
  -    }
  -}
  -
  +package org.apache.commons.graph.domain.uml;
  +
  +/**
  + * StateMachineFactory This class will build a State Machine from an NSUML Model
  + * which can be used for testing.
  + */
  +
  +import java.util.HashMap;
  +import java.util.Iterator;
  +import java.util.Map;
  +
  +import org.apache.commons.graph.domain.statemachine.State;
  +import org.apache.commons.graph.domain.statemachine.StateMachine;
  +import org.apache.commons.graph.domain.statemachine.Transition;
  +import org.apache.commons.graph.domain.uml.exception.ModelNotFoundException;
  +import org.apache.commons.graph.exception.GraphException;
  +import org.apache.log4j.Category;
  +
  +import ru.novosoft.uml.behavior.state_machines.MCompositeState;
  +import ru.novosoft.uml.behavior.state_machines.MEvent;
  +import ru.novosoft.uml.behavior.state_machines.MFinalState;
  +import ru.novosoft.uml.behavior.state_machines.MGuard;
  +import ru.novosoft.uml.behavior.state_machines.MPseudostate;
  +import ru.novosoft.uml.behavior.state_machines.MState;
  +import ru.novosoft.uml.behavior.state_machines.MStateMachine;
  +import ru.novosoft.uml.behavior.state_machines.MStateVertex;
  +import ru.novosoft.uml.behavior.state_machines.MTransition;
  +import ru.novosoft.uml.foundation.core.MClass;
  +import ru.novosoft.uml.foundation.data_types.MPseudostateKind;
  +import ru.novosoft.uml.model_management.MModel;
  +
  +/**
  + * Description of the Class
  + */
  +public class StateMachineFactory
  +{
  +    private static Category log =
  +        Category.getInstance(org.apache.commons.graph.domain.uml.StateMachineFactory.class);
  +
  +    private MModel extent = null;
  +
  +    private Map stateNames = new HashMap();// MSTATEVERTEX X NAME
  +
  +    /**
  +     * Constructor for the StateMachineFactory object
  +     *
  +     * @param extent
  +     */
  +    public StateMachineFactory(MModel extent)
  +    {
  +        this.extent = extent;
  +    }
  +
  +    /**
  +     * Gets the name attribute of the StateMachineFactory object
  +     */
  +    private String getName(String namespace, MStateVertex msv)
  +    {
  +        if (msv.getName() != null)
  +        {
  +            return namespace + "/" + msv.getName();
  +        }
  +
  +        if (msv instanceof MPseudostate)
  +        {
  +            return namespace + "/_" +
  +                ((MPseudostate) msv).getKind().getName() + "_";
  +        }
  +
  +        if (msv instanceof MFinalState)
  +        {
  +            return namespace + "/_final_";
  +        }
  +
  +        return namespace + "/_unknown_";
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    private StateMachine makeStateMachine(String namespace,
  +                                          MCompositeState mcs)
  +        throws GraphException
  +    {
  +        log.debug("makeStateMachine(" + getName(namespace, mcs) + "): Entry");
  +        StateMachine RC = new StateMachine(namespace);
  +
  +        // Step 1 - Add States to the State Machine
  +        Iterator states =
  +            mcs.getSubvertices().iterator();
  +
  +        while (states.hasNext())
  +        {
  +            MStateVertex msv =
  +                (MStateVertex) states.next();
  +
  +            RC.addState(getName(namespace, msv));
  +
  +            stateNames.put(msv, getName(namespace, msv));
  +
  +            if (msv instanceof MPseudostate)
  +            {
  +                if (((MPseudostate) msv).getKind() ==
  +                    MPseudostateKind.INITIAL)
  +                {
  +                    RC.setStartState(RC.getState(getName(namespace, msv)));
  +                }
  +            }
  +
  +            if (msv instanceof MCompositeState)
  +            {
  +                StateMachine ssm = makeStateMachine(getName(namespace, msv),
  +                    (MCompositeState) msv);
  +                RC.getState(getName(namespace, msv)).setSubmachine(ssm);
  +            }
  +
  +            if (msv instanceof MFinalState)
  +            {
  +                RC.addFinalState(RC.getState(getName(namespace, msv)));
  +            }
  +        }
  +
  +        // Step 2 - Add Transitions to State Machine
  +        states = mcs.getSubvertices().iterator();
  +        while (states.hasNext())
  +        {
  +            MStateVertex msv = (MStateVertex) states.next();
  +            String msvName = getName(namespace, msv);
  +
  +            Iterator transes =
  +                msv.getIncomings().iterator();
  +            while (transes.hasNext())
  +            {
  +                MTransition trans =
  +                    (MTransition) transes.next();
  +                MEvent trigger = trans.getTrigger();
  +		MGuard guard = trans.getGuard();
  +
  +                String trigStr = null;
  +		String guardStr = null;
  +
  +		if (guard != null) {
  +		  guardStr = guard.getName();
  +		}
  +
  +                if (trigger != null)
  +                {
  +                    trigStr = trigger.getName();
  +                }
  +                else
  +                {
  +                    trigStr = Transition.EPSILON;
  +                }
  +
  +                String sourceName =
  +                    (String) stateNames.get(trans.getSource());
  +                String targetName =
  +                    (String) stateNames.get(trans.getTarget());
  +	       
  +                State source = RC.getState(sourceName);
  +                State target = RC.getState(targetName);
  +
  +		String transName = source + "-" + target + "/" + trigStr;
  +		if (guardStr != null) {
  +		  transName = transName + "[" + guardStr + "]";
  +		}
  +
  +                Transition tranx =
  +                    new Transition(transName,
  +                    source, target);
  +		tranx.setTrigger( trigStr );
  +		tranx.setGuard( guardStr );
  +
  +                RC.addTransition(tranx);
  +            }
  +        }
  +
  +        log.debug("makeStateMachine(" + getName(namespace, mcs) + "): Exit");
  +        return RC;
  +    }
  +
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public StateMachine makeStateMachine(String selector)
  +        throws GraphException, ModelNotFoundException
  +    {
  +        log.debug("makeStateMachine(" + selector + "):Enter");
  +        MStateMachine model = null;
  +        StateMachine RC = null;
  +
  +        Iterator owned =
  +            extent.getOwnedElements().iterator();
  +
  +        while (owned.hasNext())
  +        {
  +            Object next = owned.next();
  +            if (next instanceof
  +                ru.novosoft.uml.foundation.core.MClass)
  +            {
  +                MClass mClass = (MClass) next;
  +
  +                if (selector.equals(mClass.getName()))
  +                {
  +                    Iterator machines = mClass.getBehaviors().iterator();
  +                    if (machines.hasNext())
  +                    {
  +                        model = (MStateMachine) machines.next();
  +                        log.info("StateMachine Found: " + model);
  +                    }
  +                }
  +            }
  +        }
  +
  +        if (model == null)
  +        {
  +            throw new ModelNotFoundException("Cannot find StateMachine for " +
  +                selector);
  +        }
  +
  +        MState top = model.getTop();
  +        if (top instanceof MCompositeState)
  +        {
  +            RC = makeStateMachine(selector,
  +                (MCompositeState) top);
  +        }
  +        else
  +        {
  +            throw new ModelNotFoundException("Expecting CompositeState at top.");
  +        }
  +
  +        log.debug("makeStateMachine(" + selector + "):Exit");
  +        return RC;
  +    }
  +}
  +
  
  
  
  1.2       +92 -96    jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/uml/ModelFactory.java
  
  Index: ModelFactory.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/uml/ModelFactory.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- ModelFactory.java	8 May 2002 17:43:20 -0000	1.1
  +++ ModelFactory.java	1 Jan 2003 02:19:02 -0000	1.2
  @@ -1,96 +1,92 @@
  -package org.apache.commons.graph.domain.uml;
  -
  -import java.io.File;
  -import java.io.IOException;
  -import java.io.InputStream;
  -import java.io.FileInputStream;
  -import java.io.FileNotFoundException;
  -
  -import java.util.Enumeration;
  -
  -import java.util.zip.*;
  -
  -import org.xml.sax.InputSource;
  -
  -import org.apache.commons.graph.domain.uml.exception.*;
  -
  -import org.apache.log4j.Category;
  -
  -import ru.novosoft.uml.xmi.XMIReader;
  -import ru.novosoft.uml.model_management.MModel;
  -
  -/**
  - * Description of the Class
  - */
  -public class ModelFactory
  -{
  -    private XMIReader xmiReader = null;
  -    private final static String xmiVersion = "1.1";
  -    private static Category log =
  -        Category.getInstance(org.apache.commons.graph.domain.uml.ModelFactory.class);
  -
  -    /**
  -     * Constructor for the ModelFactory object
  -     *
  -     * @exception Exception
  -     */
  -    public ModelFactory()
  -        throws Exception
  -    {
  -        log.debug("ModelFactory.__init__()");
  -        try
  -        {
  -            xmiReader = new XMIReader();
  -        }
  -        catch (Exception e)
  -        {
  -            log.error(e);
  -            throw e;
  -        }
  -    }
  -
  -    /**
  -     * Gets the fromStream attribute of the ModelFactory object
  -     */
  -    public MModel getFromStream(InputStream stream)
  -    {
  -        log.debug("getFromStream");
  -        return xmiReader.parse(new InputSource(stream));
  -    }
  -
  -    /**
  -     * Gets the fromXMI attribute of the ModelFactory object
  -     */
  -    public MModel getFromXMI(File xmiFile)
  -        throws IOException
  -    {
  -        log.debug("getFromXMI(" + xmiFile.getName() + ")");
  -        return getFromStream(new FileInputStream(xmiFile));
  -    }
  -
  -    /**
  -     * Gets the fromZargo attribute of the ModelFactory object
  -     */
  -    public MModel getFromZargo(File zargoFile)
  -        throws IOException
  -    {
  -        log.debug("getFromZargo(" + zargoFile.getName() + ")");
  -        MModel RC = null;
  -
  -        ZipFile zargoZip = new ZipFile(zargoFile);
  -
  -        Enumeration entries = zargoZip.entries();
  -        while (entries.hasMoreElements())
  -        {
  -            ZipEntry entry = (ZipEntry) entries.nextElement();
  -
  -            if (entry.getName().endsWith(".xmi"))
  -            {
  -                log.debug("Zargo Entry: " + entry.getName());
  -                return getFromStream(zargoZip.getInputStream(entry));
  -            }
  -        }
  -        throw new FileNotFoundException();
  -    }
  -
  -}
  +package org.apache.commons.graph.domain.uml;
  +
  +import java.io.File;
  +import java.io.FileInputStream;
  +import java.io.FileNotFoundException;
  +import java.io.IOException;
  +import java.io.InputStream;
  +import java.util.Enumeration;
  +import java.util.zip.ZipEntry;
  +import java.util.zip.ZipFile;
  +
  +import org.apache.log4j.Category;
  +import org.xml.sax.InputSource;
  +
  +import ru.novosoft.uml.model_management.MModel;
  +import ru.novosoft.uml.xmi.XMIReader;
  +
  +/**
  + * Description of the Class
  + */
  +public class ModelFactory
  +{
  +    private XMIReader xmiReader = null;
  +    private final static String xmiVersion = "1.1";
  +    private static Category log =
  +        Category.getInstance(org.apache.commons.graph.domain.uml.ModelFactory.class);
  +
  +    /**
  +     * Constructor for the ModelFactory object
  +     *
  +     * @exception Exception
  +     */
  +    public ModelFactory()
  +        throws Exception
  +    {
  +        log.debug("ModelFactory.__init__()");
  +        try
  +        {
  +            xmiReader = new XMIReader();
  +        }
  +        catch (Exception e)
  +        {
  +            log.error(e);
  +            throw e;
  +        }
  +    }
  +
  +    /**
  +     * Gets the fromStream attribute of the ModelFactory object
  +     */
  +    public MModel getFromStream(InputStream stream)
  +    {
  +        log.debug("getFromStream");
  +        return xmiReader.parse(new InputSource(stream));
  +    }
  +
  +    /**
  +     * Gets the fromXMI attribute of the ModelFactory object
  +     */
  +    public MModel getFromXMI(File xmiFile)
  +        throws IOException
  +    {
  +        log.debug("getFromXMI(" + xmiFile.getName() + ")");
  +        return getFromStream(new FileInputStream(xmiFile));
  +    }
  +
  +    /**
  +     * Gets the fromZargo attribute of the ModelFactory object
  +     */
  +    public MModel getFromZargo(File zargoFile)
  +        throws IOException
  +    {
  +        log.debug("getFromZargo(" + zargoFile.getName() + ")");
  +        MModel RC = null;
  +
  +        ZipFile zargoZip = new ZipFile(zargoFile);
  +
  +        Enumeration entries = zargoZip.entries();
  +        while (entries.hasMoreElements())
  +        {
  +            ZipEntry entry = (ZipEntry) entries.nextElement();
  +
  +            if (entry.getName().endsWith(".xmi"))
  +            {
  +                log.debug("Zargo Entry: " + entry.getName());
  +                return getFromStream(zargoZip.getInputStream(entry));
  +            }
  +        }
  +        throw new FileNotFoundException();
  +    }
  +
  +}
  
  
  
  1.2       +0 -3      jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java
  
  Index: DataFlowSolutions.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- DataFlowSolutions.java	26 Jul 2002 14:53:53 -0000	1.1
  +++ DataFlowSolutions.java	1 Jan 2003 02:19:02 -0000	1.2
  @@ -6,9 +6,6 @@
   import java.util.Iterator;
   
   import org.apache.commons.graph.*;
  -import org.apache.commons.graph.exception.*;
  -import org.apache.commons.graph.domain.basic.*;
  -
   
   public class DataFlowSolutions
   {
  
  
  
  1.2       +291 -291  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/CostSearch.java
  
  Index: CostSearch.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/CostSearch.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- CostSearch.java	8 May 2002 17:34:09 -0000	1.1
  +++ CostSearch.java	1 Jan 2003 02:19:02 -0000	1.2
  @@ -1,291 +1,291 @@
  -package org.apache.commons.graph.algorithm.search;
  -
  -/* ====================================================================
  - * The Apache Software License, Version 1.1
  - *
  - * Copyright (c) 2001 The Apache Software Foundation.  All rights
  - * reserved.
  - *
  - * Redistribution and use in source and binary forms, with or without
  - * modification, are permitted provided that the following conditions
  - * are met:
  - *
  - * 1. Redistributions of source code must retain the above copyright
  - *    notice, this list of conditions and the following disclaimer.
  - *
  - * 2. Redistributions in binary form must reproduce the above copyright
  - *    notice, this list of conditions and the following disclaimer in
  - *    the documentation and/or other materials provided with the
  - *    distribution.
  - *
  - * 3. The end-user documentation included with the redistribution,
  - *    if any, must include the following acknowledgment:
  - *       "This product includes software developed by the
  - *        Apache Software Foundation (http://www.apache.org/)."
  - *    Alternately, this acknowledgment may appear in the software itself,
  - *    if and wherever such third-party acknowledgments normally appear.
  - *
  - * 4. The names "Apache" and "Apache Software Foundation" and
  - *    "Commons" must not be used to endorse or promote products
  - *    derived from this software without prior written permission. For
  - *    written permission, please contact apache@apache.org.
  - *
  - * 5. Products derived from this software may not be called "Apache",
  - *    "Commons", nor may "Apache" appear in their name, without
  - *    prior written permission of the Apache Software Foundation.
  - *
  - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  - * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  - * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  - * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  - * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  - * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  - * SUCH DAMAGE.
  - * ====================================================================
  - *
  - * This software consists of voluntary contributions made by many
  - * individuals on behalf of the Apache Software Foundation.  For more
  - * information on the Apache Software Foundation, please see
  - * <http://www.apache.org/>.
  - */
  -
  -/**
  - * This is a Cost searching algorithm. It will basically follow edges/paths with
  - * minimal cost first, and then go to the later costs.
  - */
  -
  -import java.util.Set;
  -import java.util.Map;
  -import java.util.HashMap;
  -import java.util.HashSet;
  -import java.util.Iterator;
  -
  -import org.apache.commons.graph.*;
  -
  -import org.apache.commons.collections.*;
  -
  -/**
  - * Description of the Class
  - */
  -public class CostSearch
  -{
  -    /**
  -     * Description of the Class
  -     */
  -    public class ComparableEdge
  -         implements Edge, Comparable
  -    {
  -        private Edge e;
  -        private double cost;
  -
  -        /**
  -         * Constructor for the ComparableEdge object
  -         *
  -         * @param e
  -         * @param cost
  -         */
  -        public ComparableEdge(Edge e, double cost)
  -        {
  -            this.e = e;
  -            this.cost = cost;
  -        }
  -
  -        /**
  -         * Gets the edge attribute of the ComparableEdge object
  -         */
  -        public Edge getEdge()
  -        {
  -            return e;
  -        }
  -
  -        /**
  -         * Gets the cost attribute of the ComparableEdge object
  -         */
  -        public double getCost()
  -        {
  -            return cost;
  -        }
  -
  -        /**
  -         * Description of the Method
  -         */
  -        public int compareTo(Object o)
  -        {
  -            ComparableVertex cv = (ComparableVertex) o;
  -            if (cv.cost > cost)
  -            {
  -                return 1;
  -            }
  -            if (cv.cost == cost)
  -            {
  -                return 0;
  -            }
  -            if (cv.cost < cost)
  -            {
  -                return -1;
  -            }
  -            return 0;
  -        }
  -    }
  -
  -    /**
  -     * Description of the Class
  -     */
  -    public class ComparableVertex
  -         implements Vertex, Comparable
  -    {
  -        private Vertex v;
  -        private double cost;
  -
  -        /**
  -         * Constructor for the ComparableVertex object
  -         *
  -         * @param v
  -         * @param cost
  -         */
  -        public ComparableVertex(Vertex v, double cost)
  -        {
  -            this.v = v;
  -            this.cost = cost;
  -        }
  -
  -        /**
  -         * Description of the Method
  -         */
  -        public int compareTo(Object o)
  -        {
  -            ComparableVertex cv = (ComparableVertex) o;
  -            if (cv.cost > cost)
  -            {
  -                return 1;
  -            }
  -            if (cv.cost == cost)
  -            {
  -                return 0;
  -            }
  -            if (cv.cost < cost)
  -            {
  -                return -1;
  -            }
  -            return 0;
  -        }
  -
  -        /**
  -         * Gets the vertex attribute of the ComparableVertex object
  -         */
  -        public Vertex getVertex()
  -        {
  -            return v;
  -        }
  -    }
  -
  -    private Map colors = new HashMap();// VERTEX X COLOR
  -    private PriorityQueue tasks = null;
  -
  -    private String WHITE = "white";
  -    private String BLACK = "black";
  -    private String GRAY = "gray";
  -
  -    /**
  -     * Constructor for the CostSearch object
  -     */
  -    public CostSearch()
  -    {
  -        tasks = new BinaryHeap(true);
  -    }
  -
  -    /**
  -     * Constructor for the CostSearch object
  -     *
  -     * @param isMin
  -     */
  -    public CostSearch(boolean isMin)
  -    {
  -        tasks = new BinaryHeap(isMin);
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public void visitVertex(WeightedGraph graph,
  -                            Vertex vertex,
  -                            double cost,
  -                            Visitor visitor)
  -    {
  -        colors.remove(vertex);
  -        colors.put(vertex, GRAY);
  -
  -        visitor.discoverVertex(vertex);
  -        Iterator edges = graph.getEdges(vertex).iterator();
  -        while (edges.hasNext())
  -        {
  -            Edge edge = (Edge) edges.next();
  -
  -            double edgeCost = graph.getWeight(edge);
  -            ComparableEdge wEdge =
  -                new ComparableEdge(edge, edgeCost + cost);
  -            tasks.insert(wEdge);
  -        }
  -
  -        visitor.finishVertex(vertex);
  -        colors.remove(vertex);
  -        colors.put(vertex, BLACK);
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public void visitEdge(WeightedGraph graph,
  -                          Edge e,
  -                          double cost,
  -                          Visitor visitor)
  -    {
  -        visitor.discoverEdge(e);
  -
  -        Iterator vertices = graph.getVertices(e).iterator();
  -        while (vertices.hasNext())
  -        {
  -            Vertex v = (Vertex) vertices.next();
  -            if (colors.get(v) == WHITE)
  -            {
  -                visitVertex(graph, v, cost, visitor);
  -            }
  -        }
  -
  -        visitor.finishEdge(e);
  -    }
  -
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public void visit(WeightedGraph graph,
  -                      Vertex root,
  -                      Visitor visitor)
  -    {
  -        Iterator vertices = graph.getVertices().iterator();
  -        while (vertices.hasNext())
  -        {
  -            colors.put(vertices.next(), WHITE);
  -        }
  -
  -        visitor.discoverGraph(graph);
  -
  -        visitVertex(graph, root, 0.0, visitor);
  -
  -        while (!tasks.isEmpty())
  -        {
  -            ComparableEdge wEdge = (ComparableEdge) tasks.pop();
  -            visitEdge(graph, wEdge.getEdge(), wEdge.getCost(), visitor);
  -        }
  -
  -        visitor.finishGraph(graph);
  -    }
  -}
  -
  -
  +package org.apache.commons.graph.algorithm.search;
  +
  +/* ====================================================================
  + * The Apache Software License, Version 1.1
  + *
  + * Copyright (c) 2001 The Apache Software Foundation.  All rights
  + * reserved.
  + *
  + * Redistribution and use in source and binary forms, with or without
  + * modification, are permitted provided that the following conditions
  + * are met:
  + *
  + * 1. Redistributions of source code must retain the above copyright
  + *    notice, this list of conditions and the following disclaimer.
  + *
  + * 2. Redistributions in binary form must reproduce the above copyright
  + *    notice, this list of conditions and the following disclaimer in
  + *    the documentation and/or other materials provided with the
  + *    distribution.
  + *
  + * 3. The end-user documentation included with the redistribution,
  + *    if any, must include the following acknowledgment:
  + *       "This product includes software developed by the
  + *        Apache Software Foundation (http://www.apache.org/)."
  + *    Alternately, this acknowledgment may appear in the software itself,
  + *    if and wherever such third-party acknowledgments normally appear.
  + *
  + * 4. The names "Apache" and "Apache Software Foundation" and
  + *    "Commons" must not be used to endorse or promote products
  + *    derived from this software without prior written permission. For
  + *    written permission, please contact apache@apache.org.
  + *
  + * 5. Products derived from this software may not be called "Apache",
  + *    "Commons", nor may "Apache" appear in their name, without
  + *    prior written permission of the Apache Software Foundation.
  + *
  + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  + * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  + * SUCH DAMAGE.
  + * ====================================================================
  + *
  + * This software consists of voluntary contributions made by many
  + * individuals on behalf of the Apache Software Foundation.  For more
  + * information on the Apache Software Foundation, please see
  + * <http://www.apache.org/>.
  + */
  +
  +/**
  + * This is a Cost searching algorithm. It will basically follow edges/paths with
  + * minimal cost first, and then go to the later costs.
  + */
  +
  +import java.util.HashMap;
  +import java.util.Iterator;
  +import java.util.Map;
  +
  +import org.apache.commons.collections.BinaryHeap;
  +import org.apache.commons.collections.PriorityQueue;
  +import org.apache.commons.graph.Edge;
  +import org.apache.commons.graph.Vertex;
  +import org.apache.commons.graph.WeightedGraph;
  +
  +/**
  + * Description of the Class
  + */
  +public class CostSearch
  +{
  +    /**
  +     * Description of the Class
  +     */
  +    public class ComparableEdge
  +         implements Edge, Comparable
  +    {
  +        private Edge e;
  +        private double cost;
  +
  +        /**
  +         * Constructor for the ComparableEdge object
  +         *
  +         * @param e
  +         * @param cost
  +         */
  +        public ComparableEdge(Edge e, double cost)
  +        {
  +            this.e = e;
  +            this.cost = cost;
  +        }
  +
  +        /**
  +         * Gets the edge attribute of the ComparableEdge object
  +         */
  +        public Edge getEdge()
  +        {
  +            return e;
  +        }
  +
  +        /**
  +         * Gets the cost attribute of the ComparableEdge object
  +         */
  +        public double getCost()
  +        {
  +            return cost;
  +        }
  +
  +        /**
  +         * Description of the Method
  +         */
  +        public int compareTo(Object o)
  +        {
  +            ComparableVertex cv = (ComparableVertex) o;
  +            if (cv.cost > cost)
  +            {
  +                return 1;
  +            }
  +            if (cv.cost == cost)
  +            {
  +                return 0;
  +            }
  +            if (cv.cost < cost)
  +            {
  +                return -1;
  +            }
  +            return 0;
  +        }
  +    }
  +
  +    /**
  +     * Description of the Class
  +     */
  +    public class ComparableVertex
  +         implements Vertex, Comparable
  +    {
  +        private Vertex v;
  +        private double cost;
  +
  +        /**
  +         * Constructor for the ComparableVertex object
  +         *
  +         * @param v
  +         * @param cost
  +         */
  +        public ComparableVertex(Vertex v, double cost)
  +        {
  +            this.v = v;
  +            this.cost = cost;
  +        }
  +
  +        /**
  +         * Description of the Method
  +         */
  +        public int compareTo(Object o)
  +        {
  +            ComparableVertex cv = (ComparableVertex) o;
  +            if (cv.cost > cost)
  +            {
  +                return 1;
  +            }
  +            if (cv.cost == cost)
  +            {
  +                return 0;
  +            }
  +            if (cv.cost < cost)
  +            {
  +                return -1;
  +            }
  +            return 0;
  +        }
  +
  +        /**
  +         * Gets the vertex attribute of the ComparableVertex object
  +         */
  +        public Vertex getVertex()
  +        {
  +            return v;
  +        }
  +    }
  +
  +    private Map colors = new HashMap();// VERTEX X COLOR
  +    private PriorityQueue tasks = null;
  +
  +    private String WHITE = "white";
  +    private String BLACK = "black";
  +    private String GRAY = "gray";
  +
  +    /**
  +     * Constructor for the CostSearch object
  +     */
  +    public CostSearch()
  +    {
  +        tasks = new BinaryHeap(true);
  +    }
  +
  +    /**
  +     * Constructor for the CostSearch object
  +     *
  +     * @param isMin
  +     */
  +    public CostSearch(boolean isMin)
  +    {
  +        tasks = new BinaryHeap(isMin);
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public void visitVertex(WeightedGraph graph,
  +                            Vertex vertex,
  +                            double cost,
  +                            Visitor visitor)
  +    {
  +        colors.remove(vertex);
  +        colors.put(vertex, GRAY);
  +
  +        visitor.discoverVertex(vertex);
  +        Iterator edges = graph.getEdges(vertex).iterator();
  +        while (edges.hasNext())
  +        {
  +            Edge edge = (Edge) edges.next();
  +
  +            double edgeCost = graph.getWeight(edge);
  +            ComparableEdge wEdge =
  +                new ComparableEdge(edge, edgeCost + cost);
  +            tasks.insert(wEdge);
  +        }
  +
  +        visitor.finishVertex(vertex);
  +        colors.remove(vertex);
  +        colors.put(vertex, BLACK);
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public void visitEdge(WeightedGraph graph,
  +                          Edge e,
  +                          double cost,
  +                          Visitor visitor)
  +    {
  +        visitor.discoverEdge(e);
  +
  +        Iterator vertices = graph.getVertices(e).iterator();
  +        while (vertices.hasNext())
  +        {
  +            Vertex v = (Vertex) vertices.next();
  +            if (colors.get(v) == WHITE)
  +            {
  +                visitVertex(graph, v, cost, visitor);
  +            }
  +        }
  +
  +        visitor.finishEdge(e);
  +    }
  +
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public void visit(WeightedGraph graph,
  +                      Vertex root,
  +                      Visitor visitor)
  +    {
  +        Iterator vertices = graph.getVertices().iterator();
  +        while (vertices.hasNext())
  +        {
  +            colors.put(vertices.next(), WHITE);
  +        }
  +
  +        visitor.discoverGraph(graph);
  +
  +        visitVertex(graph, root, 0.0, visitor);
  +
  +        while (!tasks.isEmpty())
  +        {
  +            ComparableEdge wEdge = (ComparableEdge) tasks.pop();
  +            visitEdge(graph, wEdge.getEdge(), wEdge.getCost(), visitor);
  +        }
  +
  +        visitor.finishGraph(graph);
  +    }
  +}
  +
  +
  
  
  
  1.3       +188 -190  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java
  
  Index: DFS.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- DFS.java	26 Jul 2002 12:36:05 -0000	1.2
  +++ DFS.java	1 Jan 2003 02:19:02 -0000	1.3
  @@ -1,190 +1,188 @@
  -package org.apache.commons.graph.algorithm.search;
  -
  -/* ====================================================================
  - * The Apache Software License, Version 1.1
  - *
  - * Copyright (c) 2001 The Apache Software Foundation.  All rights
  - * reserved.
  - *
  - * Redistribution and use in source and binary forms, with or without
  - * modification, are permitted provided that the following conditions
  - * are met:
  - *
  - * 1. Redistributions of source code must retain the above copyright
  - *    notice, this list of conditions and the following disclaimer.
  - *
  - * 2. Redistributions in binary form must reproduce the above copyright
  - *    notice, this list of conditions and the following disclaimer in
  - *    the documentation and/or other materials provided with the
  - *    distribution.
  - *
  - * 3. The end-user documentation included with the redistribution,
  - *    if any, must include the following acknowledgment:
  - *       "This product includes software developed by the
  - *        Apache Software Foundation (http://www.apache.org/)."
  - *    Alternately, this acknowledgment may appear in the software itself,
  - *    if and wherever such third-party acknowledgments normally appear.
  - *
  - * 4. The names "Apache" and "Apache Software Foundation" and
  - *    "Commons" must not be used to endorse or promote products
  - *    derived from this software without prior written permission. For
  - *    written permission, please contact apache@apache.org.
  - *
  - * 5. Products derived from this software may not be called "Apache",
  - *    "Commons", nor may "Apache" appear in their name, without
  - *    prior written permission of the Apache Software Foundation.
  - *
  - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  - * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  - * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  - * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  - * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  - * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  - * SUCH DAMAGE.
  - * ====================================================================
  - *
  - * This software consists of voluntary contributions made by many
  - * individuals on behalf of the Apache Software Foundation.  For more
  - * information on the Apache Software Foundation, please see
  - * <http://www.apache.org/>.
  - */
  -
  -/**
  - * This class does a Depth First Search. It visits all of the children nodes
  - * before moving to the siblling nodes.
  - */
  -
  -import java.util.Set;
  -import java.util.Map;
  -import java.util.HashSet;
  -import java.util.HashMap;
  -import java.util.Iterator;
  -
  -import org.apache.commons.graph.*;
  -
  -/**
  - * Description of the Class
  - */
  -public class DFS
  -{
  -    private Map colors = new HashMap();// VERTEX X COLOR
  -    /**
  -     * Description of the Field
  -     */
  -    public final static String WHITE = "white";
  -    /**
  -     * Description of the Field
  -     */
  -    public final static String BLACK = "black";
  -    /**
  -     * Description of the Field
  -     */
  -    public final static String GRAY = "gray";
  -
  -    /**
  -     * Constructor for the DFS object
  -     */
  -    public DFS() { }
  -
  -    /**
  -     * Gets the color attribute of the DFS object
  -     */
  -    public String getColor(Vertex v)
  -    {
  -        return (String) colors.get(v);
  -    }
  -
  -
  -    /**
  -     * Description of the Method
  -     */
  -    private void visitEdge(DirectedGraph graph,
  -                           Edge e,
  -                           Visitor visitor)
  -    {
  -        visitor.discoverEdge(e);
  -
  -        Vertex v = graph.getTarget(e);
  -
  -        if (colors.get(v) == WHITE)
  -        {
  -            visitVertex(graph, v, visitor);
  -        }
  -
  -        visitor.finishEdge(e);
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    private void visitVertex(DirectedGraph graph,
  -                             Vertex v,
  -                             Visitor visitor)
  -    {
  -        colors.remove(v);
  -        colors.put(v, GRAY);
  -
  -        visitor.discoverVertex(v);
  -
  -        Iterator edges = graph.getOutbound(v).iterator();
  -        while (edges.hasNext())
  -        {
  -            Edge e = (Edge) edges.next();
  -            visitEdge(graph, e, visitor);
  -        }
  -
  -        visitor.finishVertex(v);
  -
  -        colors.remove(v);
  -        colors.put(v, BLACK);
  -    }
  -
  -    /**
  -     * visit - Visits the graph
  -     */
  -    public void visit(DirectedGraph graph,
  -                      Vertex root,
  -                      Visitor visitor)
  -    {
  -        Iterator vertices = graph.getVertices().iterator();
  -        while (vertices.hasNext())
  -        {
  -            colors.put(vertices.next(), WHITE);
  -        }
  -
  -        visitor.discoverGraph(graph);
  -
  -        visitVertex(graph, root, visitor);
  -
  -        visitor.finishGraph(graph);
  -    }
  -
  -    /**
  -     * 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 );
  -	
  -	vertices = graph.getVertices().iterator();
  -	while (vertices.hasNext()) {
  -	    Vertex v = (Vertex) vertices.next();
  -
  -	    if (colors.get( v ) == WHITE) {
  -		visitVertex( graph, v, visitor );
  -	    }
  -	}
  -
  -	visitor.finishGraph( graph );
  -    }
  -}
  -
  +package org.apache.commons.graph.algorithm.search;
  +
  +/* ====================================================================
  + * The Apache Software License, Version 1.1
  + *
  + * Copyright (c) 2001 The Apache Software Foundation.  All rights
  + * reserved.
  + *
  + * Redistribution and use in source and binary forms, with or without
  + * modification, are permitted provided that the following conditions
  + * are met:
  + *
  + * 1. Redistributions of source code must retain the above copyright
  + *    notice, this list of conditions and the following disclaimer.
  + *
  + * 2. Redistributions in binary form must reproduce the above copyright
  + *    notice, this list of conditions and the following disclaimer in
  + *    the documentation and/or other materials provided with the
  + *    distribution.
  + *
  + * 3. The end-user documentation included with the redistribution,
  + *    if any, must include the following acknowledgment:
  + *       "This product includes software developed by the
  + *        Apache Software Foundation (http://www.apache.org/)."
  + *    Alternately, this acknowledgment may appear in the software itself,
  + *    if and wherever such third-party acknowledgments normally appear.
  + *
  + * 4. The names "Apache" and "Apache Software Foundation" and
  + *    "Commons" must not be used to endorse or promote products
  + *    derived from this software without prior written permission. For
  + *    written permission, please contact apache@apache.org.
  + *
  + * 5. Products derived from this software may not be called "Apache",
  + *    "Commons", nor may "Apache" appear in their name, without
  + *    prior written permission of the Apache Software Foundation.
  + *
  + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  + * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  + * SUCH DAMAGE.
  + * ====================================================================
  + *
  + * This software consists of voluntary contributions made by many
  + * individuals on behalf of the Apache Software Foundation.  For more
  + * information on the Apache Software Foundation, please see
  + * <http://www.apache.org/>.
  + */
  +
  +/**
  + * This class does a Depth First Search. It visits all of the children nodes
  + * before moving to the siblling nodes.
  + */
  +
  +import java.util.Map;
  +import java.util.HashMap;
  +import java.util.Iterator;
  +
  +import org.apache.commons.graph.*;
  +
  +/**
  + * Description of the Class
  + */
  +public class DFS
  +{
  +    private Map colors = new HashMap();// VERTEX X COLOR
  +    /**
  +     * Description of the Field
  +     */
  +    public final static String WHITE = "white";
  +    /**
  +     * Description of the Field
  +     */
  +    public final static String BLACK = "black";
  +    /**
  +     * Description of the Field
  +     */
  +    public final static String GRAY = "gray";
  +
  +    /**
  +     * Constructor for the DFS object
  +     */
  +    public DFS() { }
  +
  +    /**
  +     * Gets the color attribute of the DFS object
  +     */
  +    public String getColor(Vertex v)
  +    {
  +        return (String) colors.get(v);
  +    }
  +
  +
  +    /**
  +     * Description of the Method
  +     */
  +    private void visitEdge(DirectedGraph graph,
  +                           Edge e,
  +                           Visitor visitor)
  +    {
  +        visitor.discoverEdge(e);
  +
  +        Vertex v = graph.getTarget(e);
  +
  +        if (colors.get(v) == WHITE)
  +        {
  +            visitVertex(graph, v, visitor);
  +        }
  +
  +        visitor.finishEdge(e);
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    private void visitVertex(DirectedGraph graph,
  +                             Vertex v,
  +                             Visitor visitor)
  +    {
  +        colors.remove(v);
  +        colors.put(v, GRAY);
  +
  +        visitor.discoverVertex(v);
  +
  +        Iterator edges = graph.getOutbound(v).iterator();
  +        while (edges.hasNext())
  +        {
  +            Edge e = (Edge) edges.next();
  +            visitEdge(graph, e, visitor);
  +        }
  +
  +        visitor.finishVertex(v);
  +
  +        colors.remove(v);
  +        colors.put(v, BLACK);
  +    }
  +
  +    /**
  +     * visit - Visits the graph
  +     */
  +    public void visit(DirectedGraph graph,
  +                      Vertex root,
  +                      Visitor visitor)
  +    {
  +        Iterator vertices = graph.getVertices().iterator();
  +        while (vertices.hasNext())
  +        {
  +            colors.put(vertices.next(), WHITE);
  +        }
  +
  +        visitor.discoverGraph(graph);
  +
  +        visitVertex(graph, root, visitor);
  +
  +        visitor.finishGraph(graph);
  +    }
  +
  +    /**
  +     * 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 );
  +	
  +	vertices = graph.getVertices().iterator();
  +	while (vertices.hasNext()) {
  +	    Vertex v = (Vertex) vertices.next();
  +
  +	    if (colors.get( v ) == WHITE) {
  +		visitVertex( graph, v, visitor );
  +	    }
  +	}
  +
  +	visitor.finishGraph( graph );
  +    }
  +}
  +
  
  
  
  1.2       +38 -38    jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/exception/CircularDependencyException.java
  
  Index: CircularDependencyException.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/exception/CircularDependencyException.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- CircularDependencyException.java	8 May 2002 18:07:40 -0000	1.1
  +++ CircularDependencyException.java	1 Jan 2003 02:19:03 -0000	1.2
  @@ -1,38 +1,38 @@
  -package org.apache.commons.graph.dependency.exception;
  -
  -import org.apache.commons.graph.exception.*;
  -
  -/**
  - * Description of the Class
  - */
  -public class CircularDependencyException
  -     extends CycleException
  -{
  -    /**
  -     * Constructor for the CircularDependencyException object
  -     */
  -    public CircularDependencyException()
  -    {
  -        super();
  -    }
  -
  -    /**
  -     * Constructor for the CircularDependencyException object
  -     *
  -     * @param msg
  -     */
  -    public CircularDependencyException(String msg)
  -    {
  -        super(msg);
  -    }
  -
  -    /**
  -     * Constructor for the CircularDependencyException object
  -     *
  -     * @param cause
  -     */
  -    public CircularDependencyException(Throwable cause)
  -    {
  -        super(cause);
  -    }
  -}
  +package org.apache.commons.graph.domain.dependency.exception;
  +
  +import org.apache.commons.graph.exception.*;
  +
  +/**
  + * Description of the Class
  + */
  +public class CircularDependencyException
  +     extends CycleException
  +{
  +    /**
  +     * Constructor for the CircularDependencyException object
  +     */
  +    public CircularDependencyException()
  +    {
  +        super();
  +    }
  +
  +    /**
  +     * Constructor for the CircularDependencyException object
  +     *
  +     * @param msg
  +     */
  +    public CircularDependencyException(String msg)
  +    {
  +        super(msg);
  +    }
  +
  +    /**
  +     * Constructor for the CircularDependencyException object
  +     *
  +     * @param cause
  +     */
  +    public CircularDependencyException(Throwable cause)
  +    {
  +        super(cause);
  +    }
  +}
  
  
  
  1.3       +66 -68    jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/WeightedGraph.java
  
  Index: WeightedGraph.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/WeightedGraph.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- WeightedGraph.java	8 May 2002 17:47:32 -0000	1.2
  +++ WeightedGraph.java	1 Jan 2003 02:19:03 -0000	1.3
  @@ -1,68 +1,66 @@
  -package org.apache.commons.graph;
  -
  -/* ====================================================================
  - * The Apache Software License, Version 1.1
  - *
  - * Copyright (c) 2001 The Apache Software Foundation.  All rights
  - * reserved.
  - *
  - * Redistribution and use in source and binary forms, with or without
  - * modification, are permitted provided that the following conditions
  - * are met:
  - *
  - * 1. Redistributions of source code must retain the above copyright
  - *    notice, this list of conditions and the following disclaimer.
  - *
  - * 2. Redistributions in binary form must reproduce the above copyright
  - *    notice, this list of conditions and the following disclaimer in
  - *    the documentation and/or other materials provided with the
  - *    distribution.
  - *
  - * 3. The end-user documentation included with the redistribution,
  - *    if any, must include the following acknowledgment:
  - *       "This product includes software developed by the
  - *        Apache Software Foundation (http://www.apache.org/)."
  - *    Alternately, this acknowledgment may appear in the software itself,
  - *    if and wherever such third-party acknowledgments normally appear.
  - *
  - * 4. The names "Apache" and "Apache Software Foundation" and
  - *    "Commons" must not be used to endorse or promote products
  - *    derived from this software without prior written permission. For
  - *    written permission, please contact apache@apache.org.
  - *
  - * 5. Products derived from this software may not be called "Apache",
  - *    "Commons", nor may "Apache" appear in their name, without
  - *    prior written permission of the Apache Software Foundation.
  - *
  - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  - * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  - * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  - * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  - * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  - * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  - * SUCH DAMAGE.
  - * ====================================================================
  - *
  - * This software consists of voluntary contributions made by many
  - * individuals on behalf of the Apache Software Foundation.  For more
  - * information on the Apache Software Foundation, please see
  - * <http://www.apache.org/>.
  - */
  -
  -import java.util.Comparator;
  -
  -/**
  - * Description of the Interface
  - */
  -public interface WeightedGraph extends Graph
  -{
  -    /**
  -     * Gets the weight attribute of the WeightedGraph object
  -     */
  -    public double getWeight(Edge e);
  -}
  +package org.apache.commons.graph;
  +
  +/* ====================================================================
  + * The Apache Software License, Version 1.1
  + *
  + * Copyright (c) 2001 The Apache Software Foundation.  All rights
  + * reserved.
  + *
  + * Redistribution and use in source and binary forms, with or without
  + * modification, are permitted provided that the following conditions
  + * are met:
  + *
  + * 1. Redistributions of source code must retain the above copyright
  + *    notice, this list of conditions and the following disclaimer.
  + *
  + * 2. Redistributions in binary form must reproduce the above copyright
  + *    notice, this list of conditions and the following disclaimer in
  + *    the documentation and/or other materials provided with the
  + *    distribution.
  + *
  + * 3. The end-user documentation included with the redistribution,
  + *    if any, must include the following acknowledgment:
  + *       "This product includes software developed by the
  + *        Apache Software Foundation (http://www.apache.org/)."
  + *    Alternately, this acknowledgment may appear in the software itself,
  + *    if and wherever such third-party acknowledgments normally appear.
  + *
  + * 4. The names "Apache" and "Apache Software Foundation" and
  + *    "Commons" must not be used to endorse or promote products
  + *    derived from this software without prior written permission. For
  + *    written permission, please contact apache@apache.org.
  + *
  + * 5. Products derived from this software may not be called "Apache",
  + *    "Commons", nor may "Apache" appear in their name, without
  + *    prior written permission of the Apache Software Foundation.
  + *
  + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  + * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  + * SUCH DAMAGE.
  + * ====================================================================
  + *
  + * This software consists of voluntary contributions made by many
  + * individuals on behalf of the Apache Software Foundation.  For more
  + * information on the Apache Software Foundation, please see
  + * <http://www.apache.org/>.
  + */
  +
  +/**
  + * Description of the Interface
  + */
  +public interface WeightedGraph extends Graph
  +{
  +    /**
  +     * Gets the weight attribute of the WeightedGraph object
  +     */
  +    public double getWeight(Edge e);
  +}
  
  
  
  1.2       +38 -38    jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/statemachine/exception/StateMachineException.java
  
  Index: StateMachineException.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/statemachine/exception/StateMachineException.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- StateMachineException.java	8 May 2002 18:07:41 -0000	1.1
  +++ StateMachineException.java	1 Jan 2003 02:19:03 -0000	1.2
  @@ -1,38 +1,38 @@
  -package org.apache.commons.graph.statemachine.exception;
  -
  -import org.apache.commons.graph.exception.*;
  -
  -/**
  - * Description of the Class
  - */
  -public class StateMachineException
  -     extends GraphException
  -{
  -    /**
  -     * Constructor for the StateMachineException object
  -     */
  -    public StateMachineException()
  -    {
  -        super();
  -    }
  -
  -    /**
  -     * Constructor for the StateMachineException object
  -     *
  -     * @param msg
  -     */
  -    public StateMachineException(String msg)
  -    {
  -        super(msg);
  -    }
  -
  -    /**
  -     * Constructor for the StateMachineException object
  -     *
  -     * @param t
  -     */
  -    public StateMachineException(Throwable t)
  -    {
  -        super(t);
  -    }
  -}
  +package org.apache.commons.graph.domain.statemachine.exception;
  +
  +import org.apache.commons.graph.exception.GraphException;
  +
  +/**
  + * Description of the Class
  + */
  +public class StateMachineException
  +     extends GraphException
  +{
  +    /**
  +     * Constructor for the StateMachineException object
  +     */
  +    public StateMachineException()
  +    {
  +        super();
  +    }
  +
  +    /**
  +     * Constructor for the StateMachineException object
  +     *
  +     * @param msg
  +     */
  +    public StateMachineException(String msg)
  +    {
  +        super(msg);
  +    }
  +
  +    /**
  +     * Constructor for the StateMachineException object
  +     *
  +     * @param t
  +     */
  +    public StateMachineException(Throwable t)
  +    {
  +        super(t);
  +    }
  +}
  
  
  
  1.3       +5 -8      jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/statemachine/StateMachine.java
  
  Index: StateMachine.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/statemachine/StateMachine.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- StateMachine.java	23 Aug 2002 13:51:50 -0000	1.2
  +++ StateMachine.java	1 Jan 2003 02:19:03 -0000	1.3
  @@ -1,18 +1,15 @@
   package org.apache.commons.graph.domain.statemachine;
   
  -import java.util.Map;
  -import java.util.Set;
   import java.util.HashMap;
   import java.util.HashSet;
  -import java.util.Iterator;
  +import java.util.Map;
  +import java.util.Set;
   
  -import org.apache.commons.graph.*;
  -import org.apache.commons.graph.exception.*;
  -import org.apache.commons.graph.domain.basic.*;
  +import org.apache.commons.graph.MutableDirectedGraph;
   import org.apache.commons.graph.contract.Contract;
  -import org.apache.commons.graph.factory.GraphFactory;
   import org.apache.commons.graph.decorator.DDirectedGraph;
  -import org.apache.commons.graph.domain.statemachine.exception.*;
  +import org.apache.commons.graph.exception.GraphException;
  +import org.apache.commons.graph.factory.GraphFactory;
   
   /**
    * StateMachine -
  
  
  
  1.4       +1 -5      jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/DependencyGraph.java
  
  Index: DependencyGraph.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/DependencyGraph.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- DependencyGraph.java	26 Jul 2002 12:36:05 -0000	1.3
  +++ DependencyGraph.java	1 Jan 2003 02:19:03 -0000	1.4
  @@ -3,19 +3,15 @@
   import org.apache.commons.graph.*;
   import org.apache.commons.graph.contract.*;
   import org.apache.commons.graph.exception.*;
  -import org.apache.commons.graph.domain.basic.*;
   import org.apache.commons.graph.factory.GraphFactory;
   import org.apache.commons.graph.decorator.DDirectedGraph;
  -import org.apache.commons.graph.dependency.exception.*;
  +import org.apache.commons.graph.domain.dependency.exception.CircularDependencyException;
   
  -import java.util.ArrayList;
   import java.util.Collection;
   import java.util.HashMap;
  -import java.util.HashSet;
   import java.util.Iterator;
   import java.util.List;
   import java.util.Map;
  -import java.util.Set;
   
   /**
    * Description of the Class
  
  
  
  1.2       +6 -6      jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/search/CostSearch.java
  
  Index: CostSearch.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/search/CostSearch.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- CostSearch.java	17 Mar 2002 16:28:17 -0000	1.1
  +++ CostSearch.java	1 Jan 2003 02:19:03 -0000	1.2
  @@ -59,15 +59,15 @@
    * minimal cost first, and then go to the later costs.
    */
   
  -import java.util.Set;
  -import java.util.Map;
   import java.util.HashMap;
  -import java.util.HashSet;
   import java.util.Iterator;
  +import java.util.Map;
   
  -import org.apache.commons.graph.*;
  -
  -import org.apache.commons.collections.*;
  +import org.apache.commons.collections.BinaryHeap;
  +import org.apache.commons.collections.PriorityQueue;
  +import org.apache.commons.graph.Edge;
  +import org.apache.commons.graph.Vertex;
  +import org.apache.commons.graph.WeightedGraph;
   
   /**
    * Description of the Class
  
  
  
  1.2       +0 -2      jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/search/DFS.java
  
  Index: DFS.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/search/DFS.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- DFS.java	17 Mar 2002 16:28:16 -0000	1.1
  +++ DFS.java	1 Jan 2003 02:19:03 -0000	1.2
  @@ -59,9 +59,7 @@
    * before moving to the siblling nodes.
    */
   
  -import java.util.Set;
   import java.util.Map;
  -import java.util.HashSet;
   import java.util.HashMap;
   import java.util.Iterator;
   
  
  
  
  1.3       +246 -242  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/decorator/DDirectedGraph.java
  
  Index: DDirectedGraph.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/decorator/DDirectedGraph.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- DDirectedGraph.java	8 May 2002 17:35:42 -0000	1.2
  +++ DDirectedGraph.java	1 Jan 2003 02:19:03 -0000	1.3
  @@ -1,242 +1,246 @@
  -package org.apache.commons.graph.decorator;
  -
  -/* ====================================================================
  - * The Apache Software License, Version 1.1
  - *
  - * Copyright (c) 2001 The Apache Software Foundation.  All rights
  - * reserved.
  - *
  - * Redistribution and use in source and binary forms, with or without
  - * modification, are permitted provided that the following conditions
  - * are met:
  - *
  - * 1. Redistributions of source code must retain the above copyright
  - *    notice, this list of conditions and the following disclaimer.
  - *
  - * 2. Redistributions in binary form must reproduce the above copyright
  - *    notice, this list of conditions and the following disclaimer in
  - *    the documentation and/or other materials provided with the
  - *    distribution.
  - *
  - * 3. The end-user documentation included with the redistribution,
  - *    if any, must include the following acknowledgment:
  - *       "This product includes software developed by the
  - *        Apache Software Foundation (http://www.apache.org/)."
  - *    Alternately, this acknowledgment may appear in the software itself,
  - *    if and wherever such third-party acknowledgments normally appear.
  - *
  - * 4. The names "Apache" and "Apache Software Foundation" and
  - *    "Commons" must not be used to endorse or promote products
  - *    derived from this software without prior written permission. For
  - *    written permission, please contact apache@apache.org.
  - *
  - * 5. Products derived from this software may not be called "Apache",
  - *    "Commons", nor may "Apache" appear in their name, without
  - *    prior written permission of the Apache Software Foundation.
  - *
  - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  - * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  - * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  - * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  - * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  - * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  - * SUCH DAMAGE.
  - * ====================================================================
  - *
  - * This software consists of voluntary contributions made by many
  - * individuals on behalf of the Apache Software Foundation.  For more
  - * information on the Apache Software Foundation, please see
  - * <http://www.apache.org/>.
  - */
  -import java.util.Set;
  -import java.util.Map;
  -import java.util.HashSet;
  -import java.util.HashMap;
  -import java.util.Iterator;
  -
  -import org.apache.commons.graph.*;
  -import org.apache.commons.graph.exception.*;
  -import org.apache.commons.graph.domain.basic.*;
  -import org.apache.commons.graph.algorithm.path.*;
  -import org.apache.commons.graph.algorithm.spanning.*;
  -
  -/**
  - * Description of the Class
  - */
  -public class DDirectedGraph
  -     extends DirectedGraphWrapper
  -     implements DirectedGraph,
  -    WeightedGraph
  -{
  -    private WeightedGraph weighted;
  -    private Map weights = new HashMap();// EDGE X DOUBLE
  -    private static Map decoratedGraphs = new HashMap();// DGRAPH X DDGRAPH
  -    private AllPairsShortestPath allPaths = null;
  -
  -  protected DDirectedGraph() {
  -    super();
  -  }
  -
  -    /**
  -     * Constructor for the DDirectedGraph object
  -     *
  -     * @param impl
  -     */
  -    protected DDirectedGraph(DirectedGraph impl)
  -    {
  -        super(impl);
  -
  -        if (impl instanceof WeightedGraph)
  -        {
  -            weighted = (WeightedGraph) impl;
  -        }
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public static DDirectedGraph decorateGraph(DirectedGraph graph)
  -    {
  -        if (graph instanceof DDirectedGraph)
  -        {
  -            return (DDirectedGraph) graph;
  -        }
  -
  -        if (decoratedGraphs.containsKey(graph))
  -        {
  -            return (DDirectedGraph) decoratedGraphs.get(graph);
  -        }
  -
  -        DDirectedGraph RC = new DDirectedGraph(graph);
  -        decoratedGraphs.put(graph, RC);
  -        return RC;
  -    }
  -
  -    // WeightedGraph Implementation
  -    /**
  -     * Gets the weight attribute of the DDirectedGraph object
  -     */
  -    public double getWeight(Edge e)
  -    {
  -        if (weighted != null)
  -        {
  -            return weighted.getWeight(e);
  -        }
  -        else
  -        {
  -            if (weights.containsKey(e))
  -            {
  -                return ((Double) weights.get(e)).doubleValue();
  -            }
  -            else
  -            {
  -                return 1.0;
  -            }
  -        }
  -    }
  -
  -    /**
  -     * Sets the weight attribute of the DDirectedGraph object
  -     */
  -    public void setWeight(Edge e, double value)
  -        throws GraphException
  -    {
  -        if (weighted != null)
  -        {
  -            throw new GraphException("Unable to set weight.");
  -        }
  -
  -        weights.put(e, new Double(value));
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public DirectedGraph transpose()
  -        throws GraphException
  -    {
  -        try
  -        {
  -            DirectedGraphImpl RC = new DirectedGraphImpl();
  -            Set vertexSet = getVertices();
  -            Set edgeSet = getEdges();
  -
  -            Iterator vertices = vertexSet.iterator();
  -            while (vertices.hasNext())
  -            {
  -                RC.addVertex((Vertex) vertices.next());
  -            }
  -
  -            Iterator edges = edgeSet.iterator();
  -            while (edges.hasNext())
  -            {
  -                Edge edge = (Edge) edges.next();
  -
  -                RC.addEdge(edge,
  -                    getTarget(edge),
  -                    getSource(edge));
  -            }
  -
  -            return RC;
  -        }
  -        catch (GraphException e)
  -        {
  -            throw e;
  -        }
  -        catch (Exception e)
  -        {
  -            throw new GraphException(e);
  -        }
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public boolean hasConnection(Vertex start, Vertex end)
  -        throws GraphException
  -    {
  -        if (start == end)
  -        {
  -            return true;
  -        }
  -
  -        try
  -        {
  -            if (allPaths == null)
  -            {
  -                allPaths = new AllPairsShortestPath(this);
  -            }
  -            else
  -            {
  -                allPaths.update(this);
  -            }
  -
  -            WeightedPath path =
  -                allPaths.getShortestPath(start, end);
  -        }
  -        catch (GraphException ex)
  -        {
  -            return false;
  -        }
  -
  -        return true;
  -    }
  -
  -  public MinimumSpanningForest minimumSpanningForest() {
  -    return new MinimumSpanningForest( this );
  -  }
  -
  -  public MinimumSpanningForest maximumSpanningForest() {
  -    return new MinimumSpanningForest( false, this );
  -  }
  -
  -}
  -
  -
  -
  -
  +package org.apache.commons.graph.decorator;
  +
  +/* ====================================================================
  + * The Apache Software License, Version 1.1
  + *
  + * Copyright (c) 2001 The Apache Software Foundation.  All rights
  + * reserved.
  + *
  + * Redistribution and use in source and binary forms, with or without
  + * modification, are permitted provided that the following conditions
  + * are met:
  + *
  + * 1. Redistributions of source code must retain the above copyright
  + *    notice, this list of conditions and the following disclaimer.
  + *
  + * 2. Redistributions in binary form must reproduce the above copyright
  + *    notice, this list of conditions and the following disclaimer in
  + *    the documentation and/or other materials provided with the
  + *    distribution.
  + *
  + * 3. The end-user documentation included with the redistribution,
  + *    if any, must include the following acknowledgment:
  + *       "This product includes software developed by the
  + *        Apache Software Foundation (http://www.apache.org/)."
  + *    Alternately, this acknowledgment may appear in the software itself,
  + *    if and wherever such third-party acknowledgments normally appear.
  + *
  + * 4. The names "Apache" and "Apache Software Foundation" and
  + *    "Commons" must not be used to endorse or promote products
  + *    derived from this software without prior written permission. For
  + *    written permission, please contact apache@apache.org.
  + *
  + * 5. Products derived from this software may not be called "Apache",
  + *    "Commons", nor may "Apache" appear in their name, without
  + *    prior written permission of the Apache Software Foundation.
  + *
  + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  + * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  + * SUCH DAMAGE.
  + * ====================================================================
  + *
  + * This software consists of voluntary contributions made by many
  + * individuals on behalf of the Apache Software Foundation.  For more
  + * information on the Apache Software Foundation, please see
  + * <http://www.apache.org/>.
  + */
  +import java.util.HashMap;
  +import java.util.Iterator;
  +import java.util.Map;
  +import java.util.Set;
  +
  +import org.apache.commons.graph.DirectedGraph;
  +import org.apache.commons.graph.Edge;
  +import org.apache.commons.graph.Vertex;
  +import org.apache.commons.graph.WeightedGraph;
  +import org.apache.commons.graph.WeightedPath;
  +import org.apache.commons.graph.algorithm.path.AllPairsShortestPath;
  +import org.apache.commons.graph.algorithm.spanning.MinimumSpanningForest;
  +import org.apache.commons.graph.domain.basic.DirectedGraphImpl;
  +import org.apache.commons.graph.domain.basic.DirectedGraphWrapper;
  +import org.apache.commons.graph.exception.GraphException;
  +
  +/**
  + * Description of the Class
  + */
  +public class DDirectedGraph
  +     extends DirectedGraphWrapper
  +     implements DirectedGraph,
  +    WeightedGraph
  +{
  +    private WeightedGraph weighted;
  +    private Map weights = new HashMap();// EDGE X DOUBLE
  +    private static Map decoratedGraphs = new HashMap();// DGRAPH X DDGRAPH
  +    private AllPairsShortestPath allPaths = null;
  +
  +  protected DDirectedGraph() {
  +    super();
  +  }
  +
  +    /**
  +     * Constructor for the DDirectedGraph object
  +     *
  +     * @param impl
  +     */
  +    protected DDirectedGraph(DirectedGraph impl)
  +    {
  +        super(impl);
  +
  +        if (impl instanceof WeightedGraph)
  +        {
  +            weighted = (WeightedGraph) impl;
  +        }
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public static DDirectedGraph decorateGraph(DirectedGraph graph)
  +    {
  +        if (graph instanceof DDirectedGraph)
  +        {
  +            return (DDirectedGraph) graph;
  +        }
  +
  +        if (decoratedGraphs.containsKey(graph))
  +        {
  +            return (DDirectedGraph) decoratedGraphs.get(graph);
  +        }
  +
  +        DDirectedGraph RC = new DDirectedGraph(graph);
  +        decoratedGraphs.put(graph, RC);
  +        return RC;
  +    }
  +
  +    // WeightedGraph Implementation
  +    /**
  +     * Gets the weight attribute of the DDirectedGraph object
  +     */
  +    public double getWeight(Edge e)
  +    {
  +        if (weighted != null)
  +        {
  +            return weighted.getWeight(e);
  +        }
  +        else
  +        {
  +            if (weights.containsKey(e))
  +            {
  +                return ((Double) weights.get(e)).doubleValue();
  +            }
  +            else
  +            {
  +                return 1.0;
  +            }
  +        }
  +    }
  +
  +    /**
  +     * Sets the weight attribute of the DDirectedGraph object
  +     */
  +    public void setWeight(Edge e, double value)
  +        throws GraphException
  +    {
  +        if (weighted != null)
  +        {
  +            throw new GraphException("Unable to set weight.");
  +        }
  +
  +        weights.put(e, new Double(value));
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public DirectedGraph transpose()
  +        throws GraphException
  +    {
  +        try
  +        {
  +            DirectedGraphImpl RC = new DirectedGraphImpl();
  +            Set vertexSet = getVertices();
  +            Set edgeSet = getEdges();
  +
  +            Iterator vertices = vertexSet.iterator();
  +            while (vertices.hasNext())
  +            {
  +                RC.addVertex((Vertex) vertices.next());
  +            }
  +
  +            Iterator edges = edgeSet.iterator();
  +            while (edges.hasNext())
  +            {
  +                Edge edge = (Edge) edges.next();
  +
  +                RC.addEdge(edge,
  +                    getTarget(edge),
  +                    getSource(edge));
  +            }
  +
  +            return RC;
  +        }
  +        catch (GraphException e)
  +        {
  +            throw e;
  +        }
  +        catch (Exception e)
  +        {
  +            throw new GraphException(e);
  +        }
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public boolean hasConnection(Vertex start, Vertex end)
  +        throws GraphException
  +    {
  +        if (start == end)
  +        {
  +            return true;
  +        }
  +
  +        try
  +        {
  +            if (allPaths == null)
  +            {
  +                allPaths = new AllPairsShortestPath(this);
  +            }
  +            else
  +            {
  +                allPaths.update(this);
  +            }
  +
  +            WeightedPath path =
  +                allPaths.getShortestPath(start, end);
  +        }
  +        catch (GraphException ex)
  +        {
  +            return false;
  +        }
  +
  +        return true;
  +    }
  +
  +  public MinimumSpanningForest minimumSpanningForest() {
  +    return new MinimumSpanningForest( this );
  +  }
  +
  +  public MinimumSpanningForest maximumSpanningForest() {
  +    return new MinimumSpanningForest( false, this );
  +  }
  +
  +}
  +
  +
  +
  +
  
  
  

--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message