Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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.tuscany.sca.databinding.impl;
 
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
Directed, weighted graph

Parameters:
<V> The type of vertex object
<E> The type of edge object
Version:
$Rev: 919261 $ $Date: 2010-03-05 01:26:00 +0000 (Fri, 05 Mar 2010) $
 
 public class DirectedGraph<V, E> implements Cloneable {
     private final static Logger logger = Logger.getLogger(DirectedGraph.class.getName());
     private final Map<V, Vertexvertices = new HashMap<V, Vertex>();

    
Key for the shortest path cache
 
     private final class VertexPair {
         private Vertex source;
 
         private Vertex target;

        

Parameters:
source
target
 
         private VertexPair(Vertex sourceVertex target) {
             super();
             this. = source;
             this. = target;
         }
 
         @Override
         public boolean equals(Object object) {
             if (!VertexPair.class.isInstance(object)) {
                 return false;
             }
             VertexPair pair = (VertexPair)object;
             return  == pair.source &&  == pair.target;
         }
 
         @Override
         public int hashCode() {
             int x =  == null ? 0 : .hashCode();
             int y =  == null ? 0 : .hashCode();
             return x ^ y;
         }
 
     }
 
     // Fix for TUSCANY-2069, making the map concurrent
     private final Map<VertexPairPathpaths = new ConcurrentHashMap<VertexPairPath>();
     private final Path NULL_PATH = new Path();

    
Vertex of a graph
 
     public final class Vertex {
         private V value;
 
         // TODO: Do we want to support multiple edges for a vertex pair? If so,
         // we should use a List instead of Map
         private Map<VertexEdgeoutEdges = new HashMap<VertexEdge>();
         private Map<VertexEdgeinEdges = new HashMap<VertexEdge>();
 
         private Vertex(V value) {
             this. = value;
         }
 
         @Override
        public String toString() {
            return "(" +  + ")";
        }
        public V getValue() {
            return ;
        }
        public Map<VertexEdgegetOutEdges() {
            return ;
        }
        public Map<VertexEdgegetInEdges() {
            return ;
        }
    }

    
An Edge connects two vertices in one direction
    public final class Edge {
        private Vertex sourceVertex;
        private Vertex targetVertex;
        private E value;
        private int weight;
        private boolean pub = true;
        public Edge(Vertex sourceVertex target, E valueint weightboolean pub) {
            this. = source;
            this. = target;
            this. = value;
            this. = weight;
            this. = pub;
        }
        @Override
        public String toString() {
            return  + "->" +  + "[" +  + "," +  + "]";
        }
        public E getValue() {
            return ;
        }
        public void setValue(E value) {
            this. = value;
        }
        public Vertex getTargetVertex() {
            return ;
        }
        public void setTargetVertex(Vertex vertex) {
            this. = vertex;
        }
        public int getWeight() {
            return ;
        }
        public void setWeight(int weight) {
            this. = weight;
        }
        public Vertex getSourceVertex() {
            return ;
        }
        public void setSourceVertex(Vertex sourceVertex) {
            this. = sourceVertex;
        }
        public boolean isPublic() {
            return ;
        }
        public void setPublic(boolean pub) {
            this. = pub;
        }
    }
    private final class Node implements Comparable<Node> {
        private long distance = .;
        private Node previous// NOPMD by rfeng on 9/26/06 9:17 PM
        private Vertex vertex// NOPMD by rfeng on 9/26/06 9:17 PM
        private Node(Vertex vertex) {
            this. = vertex;
        }
        public int compareTo(Node o) {
            return ( > o.distance) ? 1 : (( == o.distance) ? 0 : -1);
        }
    }
    public void addEdge(V source, V target, E edgeValueint weightboolean publicEdge) {
        // Fix for TUSCANY-3456 
        // First check if we already has an edge
        Edge edge = getEdge(sourcetarget);
        if (edge != null) {
            // An existing edge has higher weight, let's replace it
            if (edge.weight > weight) {
                .fine("An edge exists with higher weight: " + edge);
                removeEdge(edge);
            } else {
                // Don't add this edge
                .fine("An edge exists with lower weight: " + edge);
                return;
            }
        }
        Vertex s = getVertex(source);
        if (s == null) {
            s = new Vertex(source);
            .put(sources);
        }
        Vertex t = getVertex(target);
        if (t == null) {
            t = new Vertex(target);
            .put(targett);
        }
        edge = new Edge(stedgeValueweightpublicEdge);
        s.outEdges.put(tedge);
        t.inEdges.put(sedge);
    }
    public void addEdge(V soure, V target) {
        addEdge(souretargetnull, 0, true);
    }
    public Vertex getVertex(V source) {
        Vertex s = .get(source);
        return s;
    }
    public boolean removeEdge(V source, V target) {
        Vertex s = getVertex(source);
        if (s == null) {
            return false;
        }
        Vertex t = getVertex(target);
        if (t == null) {
            return false;
        }
        return s.outEdges.remove(t) != null && t.inEdges.remove(s) != null;
    }
    public void removeEdge(Edge edge) {
        edge.sourceVertex.outEdges.remove(edge.targetVertex);
        edge.targetVertex.inEdges.remove(edge.sourceVertex);
    }
    public void removeVertex(Vertex vertex) {
        .remove(vertex.getValue());
        for (Edge e : new ArrayList<Edge>(vertex.outEdges.values())) {
            removeEdge(e);
        }
        for (Edge e : new ArrayList<Edge>(vertex.inEdges.values())) {
            removeEdge(e);
        }
    }
    public Edge getEdge(Vertex sourceVertex target) {
        return source.outEdges.get(target);
    }
    public Edge getEdge(V source, V target) {
        Vertex sv = getVertex(source);
        if (sv == null) {
            return null;
        }
        Vertex tv = getVertex(target);
        if (tv == null) {
            return null;
        }
        return getEdge(getVertex(source), getVertex(target));
    }

    
Get the shortest path from the source vertex to the target vertex using Dijkstra's algorithm. If there's no path, null will be returned. If the source is the same as the target, it returns a path with empty edges with weight 0.

Parameters:
sourceValue The value identifies the source
targetValue The value identifies the target
Returns:
The shortest path
    public Path getShortestPath(V sourceValue, V targetValue) {
        Vertex source = getVertex(sourceValue);
        if (source == null) {
            return null;
        }
        Vertex target = getVertex(targetValue);
        if (target == null) {
            return null;
        }
        VertexPair pair = new VertexPair(sourcetarget);
        Path path = null;
        if (.containsKey(pair)) {
            path = .get(pair);
            return path == nullpath;
        }
        // Check if there is a direct link, if yes, use it instead
        Edge direct = getEdge(sourcetarget);
        path = new Path();
        if (direct != null) {
            path.addEdge(direct);
            .put(pairpath);
            return path;
        }
        Map<VertexNodenodes = new HashMap<VertexNode>();
        for (Vertex v : .values()) {
            Node node = new Node(v);
            if (v == source) {
                node.distance = 0;
            }
            nodes.put(vnode);
        }
        Set<NodeotherNodes = new HashSet<Node>(nodes.values());
        Set<NodenodesOnPath = new HashSet<Node>();
        Node nextNode = null;
        while (!otherNodes.isEmpty()) {
            nextNode = extractMin(otherNodes);
            if (nextNode.vertex == target) {
                path = getPath(nextNode);
                .put(pairpath); // Cache it
                return path == nullpath;
            }
            nodesOnPath.add(nextNode);
            for (Edge edge : nextNode.vertex.outEdges.values()) {
                Node adjacentNode = nodes.get(edge.targetVertex);
                // The private edge can only be used if the edge connects to the target directly
                if (edge.isPublic() || edge.getTargetVertex() == target) {
                    if (nextNode.distance + edge.weight < adjacentNode.distance) {
                        adjacentNode.distance = nextNode.distance + edge.weight;
                        adjacentNode.previous = nextNode;
                    }
                }
            }
        }
        .put(pair); // Cache it
        return null;
    }

    
Searches for the vertex u in the vertex set Q that has the least d[u] value. That vertex is removed from the set Q and returned to the user.

Parameters:
nodes
Returns:
    private Node extractMin(Set<Nodenodes) {
        Node node = Collections.min(nodes);
        nodes.remove(node);
        return node;
    }

    
The path between two vertices
    public final class Path {
        private List<Edgeedges = new LinkedList<Edge>();
        private int weight;
        public int getWeight() {
            return ;
        }
        public List<EdgegetEdges() {
            return ;
        }
        public void addEdge(Edge edge) {
            .add(0, edge);
             += edge.weight;
        }
        @Override
        public String toString() {
            return  + ", " + ;
        }
    }
    private Path getPath(Node t) {
        if (t.distance == .) {
            return ;
        }
        Path path = new Path();
        Node u = t;
        while (u.previous != null) {
            Edge edge = getEdge(u.previous.vertexu.vertex);
            path.addEdge(edge);
            u = u.previous;
        }
        return path;
    }
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        for (Vertex v : .values()) {
            sb.append(v.outEdges.values()).append("\n");
        }
        return sb.toString();
    }
    public Map<V, VertexgetVertices() {
        return ;
    }
    public void addGraph(DirectedGraph<V, E> otherGraph) {
        for (Vertex v : otherGraph.vertices.values()) {
            for (Edge e : v.outEdges.values()) {
                addEdge(e.sourceVertex.valuee.targetVertex.valuee.valuee.weighttrue);
            }
        }
    }
    private Vertex getFirst() {
        for (Vertex v : .values()) {
            if (v.inEdges.isEmpty()) {
                return v;
            }
        }
        if (!.isEmpty()) {
            throw new IllegalArgumentException("Circular ordering has been detected: " + toString());
        } else {
            return null;
        }
    }
    public List<V> topologicalSort(boolean readOnly) {
        DirectedGraph<V, E> graph = (!readOnly) ? this : (DirectedGraph<V, E>)clone();
        List<V> list = new ArrayList<V>();
        while (true) {
            Vertex v = graph.getFirst();
            if (v == null) {
                break;
            }
            list.add(v.getValue());
            graph.removeVertex(v);
        }
        return list;
    }
    @Override
    public Object clone() {
        DirectedGraph<V, E> copy = new DirectedGraph<V, E>();
        copy.addGraph(this);
        return copy;
    }
New to GrepCode? Check out our FAQ X