X-Git-Url: http://wamblee.org/gitweb/?a=blobdiff_plain;f=system%2Fgeneral%2Fsrc%2Fmain%2Fjava%2Forg%2Fwamblee%2Fsystem%2Fgraph%2FGraph.java;h=9078b92014438ab69ded3e1d67c7f8147f1450de;hb=49ce7cb8387601982d5e6ef186ce206d38f6e3d7;hp=5d6e6ccddf06333425914dd6963eeacf8f7d8ebf;hpb=436718e7b7ee0bb9f37db496dbde5c011d5f84e3;p=utils diff --git a/system/general/src/main/java/org/wamblee/system/graph/Graph.java b/system/general/src/main/java/org/wamblee/system/graph/Graph.java index 5d6e6ccd..9078b920 100644 --- a/system/general/src/main/java/org/wamblee/system/graph/Graph.java +++ b/system/general/src/main/java/org/wamblee/system/graph/Graph.java @@ -1,5 +1,5 @@ /* - * Copyright 2008 the original author or authors. + * Copyright 2005-2010 the original author or authors. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -16,122 +16,263 @@ package org.wamblee.system.graph; import java.util.ArrayList; +import java.util.Iterator; import java.util.List; +/** + * Represents a graph consisting of nodes and edges. + * + * @author Erik Brakkee + */ public class Graph { + private List nodes; - private List _nodes; - private List _edges; + private List edges; + /** + * Constructs the graph. + */ public Graph() { - _nodes = new ArrayList(); - _edges = new ArrayList(); + nodes = new ArrayList(); + edges = new ArrayList(); } + /** + * Adds a node. + * + * @param aNode + * Node to add. + * + * @throws IllegalArgumentException + * In case the node already exists. Node equality is checked + * using equals. + */ public void addNode(Node aNode) { - if (_nodes.contains(aNode)) { - throw new IllegalArgumentException("Node '" + aNode.getName() - + "' already exists"); + if (nodes.contains(aNode)) { + throw new IllegalArgumentException("Node '" + aNode.getName() + + "' already exists"); } - _nodes.add(aNode); + + nodes.add(aNode); } - - public Node findNode(String aName) { - for (Node node: _nodes) { - if ( node.getName().equals(aName)) { - return node; + + /** + * Finds a node with the given name. + * + * @param aName + * Node name. + * + * @return Node or null if not found. + */ + public Node findNode(String aName) { + for (Node node : nodes) { + if (node.getName().equals(aName)) { + return node; } } - return null; + + return null; } + /** + * Removes a node. + * + * @param aNode + * Node to remove. + * + * @return True iff the node was removed. + * + * @throws IllegalArgumentException + * In case there are edges of which the node is a part. + */ public boolean removeNode(Node aNode) { if (!findOutgoing(aNode).isEmpty() || !findIncoming(aNode).isEmpty()) { - throw new IllegalArgumentException("Cannot remove node '" - + aNode.getName() - + "' because it is connected to one or more edges"); + throw new IllegalArgumentException("Cannot remove node '" + + aNode.getName() + + "' because it is connected to one or more edges"); } - return _nodes.remove(aNode); + + return nodes.remove(aNode); } + /** + * Adds a list of nodes. + * + * @param aNodes + * Nodes to add. + * + * @see #addNode(Node) + */ public void addNodes(List aNodes) { for (Node node : aNodes) { addNode(node); } } + /** + * Adds an edge. + * + * @param aEdge + * Edge to add. + * + * @throws IllegalArgumentException + * In case one of the nodes of the edges is not part of the + * graph or if the same edge (as determined by + * {@link #equals(Object)} is already a part of the graph. + */ public void addEdge(Edge aEdge) { - if (_edges.contains(aEdge)) { - throw new IllegalArgumentException("Edge '" + aEdge - + "' already exists"); + if (edges.contains(aEdge)) { + throw new IllegalArgumentException("Edge '" + aEdge + + "' already exists"); } - if (!_nodes.contains(aEdge.getFrom())) { - throw new IllegalArgumentException("From node '" + aEdge.getFrom() - + "' from edge '" + aEdge + "' is not part of the graph"); + + if (!nodes.contains(aEdge.getFrom())) { + throw new IllegalArgumentException("From node '" + aEdge.getFrom() + + "' from edge '" + aEdge + "' is not part of the graph"); } - if (!_nodes.contains(aEdge.getTo())) { - throw new IllegalArgumentException("To node '" + aEdge.getTo() - + "' from edge '" + aEdge + "' is not part of the graph"); + + if (!nodes.contains(aEdge.getTo())) { + throw new IllegalArgumentException("To node '" + aEdge.getTo() + + "' from edge '" + aEdge + "' is not part of the graph"); } - _edges.add(aEdge); + + edges.add(aEdge); } + /** + * Removes an edge. + * + * @param aEdge + * Edge to remove. + * + * @return True if the edge was removed. + */ public boolean removeEdge(Edge aEdge) { - return _edges.remove(aEdge); + return edges.remove(aEdge); } + /** + * Adds a number of edges. + * + * @param aEdges + * Edges to add. + */ public void addEdges(List aEdges) { for (Edge edge : aEdges) { addEdge(edge); } } + /** + * Gets the nodes. + * + * @return Copy of the list of nodes of the graph. + */ public List getNodes() { - return new ArrayList(_nodes); + return new ArrayList(nodes); } + /** + * Gets the edges. + * + * @return Copy of the list of edges of the graph. + */ public List getEdges() { - return new ArrayList(_edges); + return new ArrayList(edges); } + /** + * Extends the graph with edges using an edge factory. All combinations of + * nodes are passed to the factory which creates additional edges. + * + * @param aFactory + * Edge factory. + */ public void extend(EdgeFactory aFactory) { - for (Node from : _nodes) { - for (Node to : _nodes) { - _edges.addAll(aFactory.create(from, to)); + for (Node from : nodes) { + for (Node to : nodes) { + edges.addAll(aFactory.create(from, to)); + } + } + } + + /** + * Applies a filter to the graph for removing elements. + * + * @param aFilter + * Filter to apply. + */ + public void applyFilter(EdgeFilter aFilter) { + for (Iterator edge = edges.iterator(); edge.hasNext();) { + if (aFilter.isViolated(edge.next())) { + edge.remove(); } } } + /** + * Finds all outgoing edges of a node. More specifically, finds all edges + * e for which e.getFrom().getName() = + * aNode.getName(). + * + * @param aNode + * Node for which to find outgoing edges. + * + * @return List of outgoing edges. + */ public List findOutgoing(Node aNode) { List result = new ArrayList(); - for (Edge edge : _edges) { + + for (Edge edge : edges) { if (edge.getFrom().getName().equals(aNode.getName())) { result.add(edge); } } + return result; } + /** + * Finds all incoming edges of a node. More specifically, finds all edges + * e for which e.getTo().getName() = + * aNode.getName(). + * + * @param aNode + * Node for which to find incoming edges. + * + * @return List of incoming edges. + */ public List findIncoming(Node aNode) { List result = new ArrayList(); - for (Edge edge : _edges) { + + for (Edge edge : edges) { if (edge.getTo().getName().equals(aNode.getName())) { result.add(edge); } } + return result; } + /** + * Implements a visitor design pattern. This loops over all nodes and all + * edges and invokes the appropriate visit methods on the visitor. + * + * @param aVisitor + * Visitor. + */ public void accept(Visitor aVisitor) { - List nodes = getNodes(); // copy to make sure the visitor can - // modify the + List allNodes = getNodes(); // copy to make sure the visitor can + // modify the // list of nodes as part of the loop. - List edges = getEdges(); // copy ..... (see above). - for (Node node : nodes) { + List allEdges = getEdges(); // copy ..... (see above). + + for (Node node : allNodes) { aVisitor.visitNode(node); } - for (Edge edge : edges) { + + for (Edge edge : allEdges) { aVisitor.visitEdge(edge); } }