third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/DirectionTransformer.java

   1 /*
   2  * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3  * of California
   4  * All rights reserved.
   5  *
   6  * This software is open-source under the BSD license; see either
   7  * "license.txt" or
   8  * http://jung.sourceforge.net/license.txt for a description.
   9  */
  10 /*
  11  * Created on Apr 21, 2004
  12  */
  13 package edu.uci.ics.jung.algorithms.transformation;
  14
  15 import org.apache.commons.collections15.Factory;
  16
  17 import edu.uci.ics.jung.graph.DirectedGraph;
  18 import edu.uci.ics.jung.graph.Graph;
  19 import edu.uci.ics.jung.graph.UndirectedGraph;
  20 import edu.uci.ics.jung.graph.util.EdgeType;
  21 import edu.uci.ics.jung.graph.util.Pair;
  22
  23 /**
  24  * <p>Functions for transforming graphs into directed or undirected graphs.</p>
  25  *
  26  *
  27  * @author Danyel Fisher
  28  * @author Joshua O'Madadhain
  29  */
  30 public class DirectionTransformer
  31 {
  32
  33     /**
  34      * Transforms <code>graph</code> (which may be of any directionality)
  35      * into an undirected graph. (This may be useful for
  36      * visualization tasks).
  37      * Specifically:
  38      * <ul>
  39      * <li/>Vertices are copied from <code>graph</code>.
  40      * <li/>Directed edges are 'converted' into a single new undirected edge in the new graph.
  41      * <li/>Each undirected edge (if any) in <code>graph</code> is 'recreated' with a new undirected edge in the new
  42      * graph if <code>create_new</code> is true, or copied from <code>graph</code> otherwise.
  43      * </ul>
  44      *
  45      * @param graph     the graph to be transformed
  46      * @param create_new specifies whether existing undirected edges are to be copied or recreated
  47      * @param graph_factory used to create the new graph object
  48      * @param edge_factory used to create new edges
  49      * @return          the transformed <code>Graph</code>
  50      */
  51     public static <V,E> UndirectedGraph<V,E> toUndirected(Graph<V,E> graph,
  52                 Factory<UndirectedGraph<V,E>> graph_factory,
  53             Factory<E> edge_factory, boolean create_new)
  54     {
  55         UndirectedGraph<V,E> out = graph_factory.create();
  56
  57         for (V v : graph.getVertices())
  58             out.addVertex(v);
  59
  60         for (E e : graph.getEdges())
  61         {
  62             Pair<V> endpoints = graph.getEndpoints(e);
  63             V v1 = endpoints.getFirst();
  64             V v2 = endpoints.getSecond();
  65             E to_add;
  66             if (graph.getEdgeType(e) == EdgeType.DIRECTED || create_new)
  67                 to_add = edge_factory.create();
  68             else
  69                 to_add = e;
  70             out.addEdge(to_add, v1, v2, EdgeType.UNDIRECTED);
  71         }
  72         return out;
  73     }
  74
  75     /**
  76      * Transforms <code>graph</code> (which may be of any directionality)
  77      * into a directed graph.
  78      * Specifically:
  79      * <ul>
  80      * <li/>Vertices are copied from <code>graph</code>.
  81      * <li/>Undirected edges are 'converted' into two new antiparallel directed edges in the new graph.
  82      * <li/>Each directed edge (if any) in <code>graph</code> is 'recreated' with a new edge in the new
  83      * graph if <code>create_new</code> is true, or copied from <code>graph</code> otherwise.
  84      * </ul>
  85      *
  86      * @param graph     the graph to be transformed
  87      * @param create_new specifies whether existing directed edges are to be copied or recreated
  88      * @param graph_factory used to create the new graph object
  89      * @param edge_factory used to create new edges
  90      * @return          the transformed <code>Graph</code>
  91      */
  92     public static <V,E> Graph<V,E> toDirected(Graph<V,E> graph, Factory<DirectedGraph<V,E>> graph_factory,
  93             Factory<E> edge_factory, boolean create_new)
  94     {
  95         DirectedGraph<V,E> out = graph_factory.create();
  96
  97         for (V v : graph.getVertices())
  98             out.addVertex(v);
  99
 100         for (E e : graph.getEdges())
 101         {
 102             Pair<V> endpoints = graph.getEndpoints(e);
 103             if (graph.getEdgeType(e) == EdgeType.UNDIRECTED)
 104             {
 105                 V v1 = endpoints.getFirst();
 106                 V v2 = endpoints.getSecond();
 107                 out.addEdge(edge_factory.create(), v1, v2, EdgeType.DIRECTED);
 108                 out.addEdge(edge_factory.create(), v2, v1, EdgeType.DIRECTED);
 109             }
 110             else // if the edge is directed, just add it
 111             {
 112                 V source = graph.getSource(e);
 113                 V dest = graph.getDest(e);
 114                 E to_add = create_new ? edge_factory.create() : e;
 115                 out.addEdge(to_add, source, dest, EdgeType.DIRECTED);
 116             }
 117
 118         }
 119         return out;
 120     }
 121 }