| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| */ |
| package org.apache.openjpa.lib.graph; |
| |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.LinkedHashMap; |
| import java.util.Map; |
| |
| /** |
| * <p>Graph representation using the adjacency list form. See the book |
| * 'Introduction to Algorithms' by Cormen, Leiserson, and Rivest.</p> |
| * |
| * @author Abe White |
| * @since 1.0.0 |
| * @nojavadoc |
| */ |
| public class Graph { |
| |
| /** |
| * Map each node to list of edges from that node. |
| * Using a LinkedHashMap to ensure order of iterator processing. |
| */ |
| private final Map _nodes = new LinkedHashMap(); |
| |
| /** |
| * Clear the graph. |
| */ |
| public void clear() { |
| _nodes.clear(); |
| } |
| |
| /** |
| * Return true if the graph contains the given node. |
| */ |
| public boolean containsNode(Object node) { |
| return _nodes.containsKey(node); |
| } |
| |
| /** |
| * Return a view of all nodes in the graph. |
| */ |
| public Collection getNodes() { |
| return _nodes.keySet(); |
| } |
| |
| /** |
| * Add a node to the graph. Adding a node a second time has no effect. |
| */ |
| public void addNode(Object node) { |
| if (node == null) |
| throw new NullPointerException("node = null"); |
| if (!containsNode(node)) |
| _nodes.put(node, null); |
| } |
| |
| /** |
| * Remove a node from the graph. All edges to and from the node |
| * will be cleared. |
| * |
| * @return true if the node was removed, false otherwise |
| */ |
| public boolean removeNode(Object node) { |
| boolean rem = containsNode(node); |
| if (rem) { |
| Collection edges = getEdgesTo(node); |
| for (Iterator itr = edges.iterator(); itr.hasNext();) |
| removeEdge((Edge) itr.next()); |
| _nodes.remove(node); |
| } |
| return rem; |
| } |
| |
| /** |
| * Return all edges in the graph. |
| */ |
| public Collection getEdges() { |
| Collection all = new HashSet(); |
| Collection edges; |
| for (Iterator itr = _nodes.values().iterator(); itr.hasNext();) { |
| edges = (Collection) itr.next(); |
| if (edges != null) |
| all.addAll(edges); |
| } |
| return all; |
| } |
| |
| /** |
| * Return all the edges from a particular node. |
| */ |
| public Collection getEdgesFrom(Object node) { |
| Collection edges = (Collection) _nodes.get(node); |
| return (edges == null) ? Collections.EMPTY_LIST : edges; |
| } |
| |
| /** |
| * Return all the edges to a particular node. |
| */ |
| public Collection getEdgesTo(Object node) { |
| Collection edges = getEdges(); |
| Collection to = new ArrayList(); |
| Edge edge; |
| for (Iterator itr = edges.iterator(); itr.hasNext();) { |
| edge = (Edge) itr.next(); |
| if (edge.isTo(node)) |
| to.add(edge); |
| } |
| return to; |
| } |
| |
| /** |
| * Return all the edges from one node to another. |
| */ |
| public Collection getEdges(Object from, Object to) { |
| Collection edges = getEdgesFrom(from); |
| Collection matches = new ArrayList(edges.size()); |
| Edge edge; |
| for (Iterator itr = edges.iterator(); itr.hasNext();) { |
| edge = (Edge) itr.next(); |
| if (edge.isTo(to)) |
| matches.add(edge); |
| } |
| return matches; |
| } |
| |
| /** |
| * Add an edge to the graph. |
| */ |
| public void addEdge(Edge edge) { |
| if (!containsNode(edge.getTo())) |
| throw new IllegalArgumentException(edge.getTo().toString()); |
| if (!containsNode(edge.getFrom())) |
| throw new IllegalArgumentException(edge.getFrom().toString()); |
| |
| Collection from = (Collection) _nodes.get(edge.getFrom()); |
| if (from == null) { |
| from = new ArrayList(3); |
| _nodes.put(edge.getFrom(), from); |
| } |
| from.add(edge); |
| |
| if (!edge.isDirected() && !edge.getFrom().equals(edge.getTo())) { |
| Collection to = (Collection) _nodes.get(edge.getTo()); |
| if (to == null) { |
| to = new ArrayList(3); |
| _nodes.put(edge.getTo(), to); |
| } |
| to.add(edge); |
| } |
| } |
| |
| /** |
| * Remove an edge from the graph. |
| * |
| * @return true if the edge was removed, false if not in the graph |
| */ |
| public boolean removeEdge(Edge edge) { |
| Collection edges = (Collection) _nodes.get(edge.getFrom()); |
| if (edges == null) |
| return false; |
| boolean rem = edges.remove(edge); |
| if (rem && !edge.isDirected()) { |
| edges = (Collection) _nodes.get(edge.getTo()); |
| if (edges != null) |
| edges.remove(edge); |
| } |
| return rem; |
| } |
| |
| /** |
| * Clear all nodes and edges of the bookkeeping information from their |
| * last traversal. |
| */ |
| public void clearTraversal() { |
| Collection edges; |
| for (Iterator vals = _nodes.values().iterator(); vals.hasNext();) { |
| edges = (Collection) vals.next(); |
| if (edges != null) |
| for (Iterator ed = edges.iterator(); ed.hasNext();) |
| ((Edge) ed.next()).clearTraversal (); |
| } |
| } |
| } |