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 [EMAIL PROTECTED]
- *
- * 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 [EMAIL PROTECTED]
+ *
+ * 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 [EMAIL PROTECTED]
- *
- * 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 [EMAIL PROTECTED]
+ *
+ * 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 [EMAIL PROTECTED]
- *
- * 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 [EMAIL PROTECTED]
+ *
+ * 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 [EMAIL PROTECTED]
- *
- * 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 [EMAIL PROTECTED]
+ *
+ * 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:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
