/* | |
* 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 (); | |
} | |
} | |
} |