View Javadoc

1   /*
2    * Grapht, an open source dependency injector.
3    * Copyright 2014-2015 various contributors (see CONTRIBUTORS.txt)
4    * Copyright 2010-2014 Regents of the University of Minnesota
5    *
6    * This program is free software; you can redistribute it and/or modify
7    * it under the terms of the GNU Lesser General Public License as
8    * published by the Free Software Foundation; either version 2.1 of the
9    * License, or (at your option) any later version.
10   *
11   * This program is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13   * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14   * details.
15   *
16   * You should have received a copy of the GNU General Public License along with
17   * this program; if not, write to the Free Software Foundation, Inc., 51
18   * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19   */
20  package org.grouplens.grapht.graph;
21  
22  import com.google.common.base.Function;
23  import com.google.common.base.Predicate;
24  import org.apache.commons.lang3.builder.HashCodeBuilder;
25  
26  import javax.annotation.Nonnull;
27  import javax.annotation.Nullable;
28  import java.io.Serializable;
29  
30  /**
31   * Edges in DAGs.  These arise from building nodes with a {@link DAGNodeBuilder}.
32   *
33   * <p>Two edges are equal if they connect the same pair of nodes and have the same label.
34   *
35   * @param <V> The type of node labels.
36   * @param <E> The type of edge labels.
37   * @see DAGNode
38   * @since 0.7.0
39   * @author <a href="http://www.grouplens.org">GroupLens Research</a>
40   */
41  public class DAGEdge<V,E> implements Serializable {
42      private static final long serialVersionUID = 1L;
43  
44      @Nonnull
45      private final DAGNode<V,E> head;
46      @Nonnull
47      private final DAGNode<V,E> tail;
48      @Nonnull
49      @SuppressWarnings("squid:S1948") // serializable warning; edge is serializable iff its label type is
50      private final E label;
51      private transient volatile int hashCode;
52  
53      public static <V,E> DAGEdge<V,E> create(DAGNode<V,E> head, DAGNode<V,E> tail, E label) {
54          return new DAGEdge<V,E>(head, tail, label);
55      }
56  
57      DAGEdge(DAGNode<V,E> hd, DAGNode<V,E> tl, E lbl) {
58          assert hd != null;
59          assert tl != null;
60          assert lbl != null;
61          head = hd;
62          tail = tl;
63          label = lbl;
64      }
65  
66      /**
67       * Get the edge's head (starting node).
68       * @return The edge's head.
69       */
70      @Nonnull
71      public DAGNode<V,E> getHead() {
72          return head;
73      }
74  
75      /**
76       * Get the edge's tail (ending node).
77       * @return The edge's tail.
78       */
79      @Nonnull
80      public DAGNode<V,E> getTail() {
81          return tail;
82      }
83  
84      /**
85       * Get the edge's label.
86       * @return The edge's label.
87       */
88      @Nonnull
89      public E getLabel() {
90          return label;
91      }
92  
93      @Override
94      public int hashCode() {
95          if (hashCode == 0) {
96              hashCode = new HashCodeBuilder().append(head).append(tail).append(label).toHashCode();
97          }
98          return hashCode;
99      }
100 
101     @Override
102     public boolean equals(Object o) {
103         if (o == this) {
104             return true;
105         } else if (o instanceof DAGEdge) {
106             DAGEdge<?,?> oe = (DAGEdge<?,?>) o;
107             return head.equals(oe.getHead())
108                    && tail.equals(oe.getTail())
109                    && label.equals(oe.getLabel());
110         } else {
111             return false;
112         }
113     }
114 
115     @Override
116     public String toString() {
117         StringBuilder sb = new StringBuilder();
118         sb.append("edge ")
119           .append(label)
120           .append(" from ")
121           .append(head)
122           .append(" to ")
123           .append(tail);
124         return sb.toString();
125     }
126 
127     public static <E> Predicate<DAGEdge<?,E>> labelMatches(final Predicate<? super E> pred) {
128         return new Predicate<DAGEdge<?, E>>() {
129             @Override
130             public boolean apply(@Nullable DAGEdge<?, E> input) {
131                 E label = input == null ? null : input.getLabel();
132                 return pred.apply(label);
133             }
134         };
135     }
136 
137     public static <V,E> Predicate<DAGEdge<V,E>> tailMatches(final Predicate<? super DAGNode<V,E>> pred) {
138         return new Predicate<DAGEdge<V, E>>() {
139             @Override
140             public boolean apply(@Nullable DAGEdge<V, E> input) {
141                 DAGNode<V,E> tail = input == null ? null : input.getTail();
142                 return pred.apply(tail);
143             }
144         };
145     }
146 
147     public static <V,E> Function<DAGEdge<V,E>,DAGNode<V,E>> extractTail() {
148         return new Function<DAGEdge<V, E>, DAGNode<V, E>>() {
149             @Nullable
150             @Override
151             public DAGNode<V, E> apply(@Nullable DAGEdge<V, E> input) {
152                 return input == null ? null : input.getTail();
153             }
154         };
155     }
156 
157     public static <V,E> Predicate<DAGEdge<V,E>> headMatches(final Predicate<? super DAGNode<V,E>> pred) {
158         return new Predicate<DAGEdge<V, E>>() {
159             @Override
160             public boolean apply(@Nullable DAGEdge<V, E> input) {
161                 DAGNode<V,E> head = input == null ? null : input.getHead();
162                 return pred.apply(head);
163             }
164         };
165     }
166 
167     public static <V,E> Function<DAGEdge<V,E>,DAGNode<V,E>> extractHead() {
168         return new Function<DAGEdge<V, E>, DAGNode<V, E>>() {
169             @Nullable
170             @Override
171             public DAGNode<V, E> apply(@Nullable DAGEdge<V, E> input) {
172                 return input == null ? null : input.getHead();
173             }
174         };
175     }
176 
177     /**
178      * Transform an edge.  This function does not further transform the nodes, so if the edge is
179      * known as the outgoing edge of a node, that won't be fixed.  Mostly useful for bulk operations
180      * on a bunch of edges, if you have them lying around.
181      *
182      * @param func The node transformation function.  If this function returns null, that is treated
183      *             as equivalent to the identity function.
184      * @param <V> The type of vertices.
185      * @param <E> The type of edges.
186      * @return A function over edges.
187      */
188     public static <V,E> Function<DAGEdge<V,E>,DAGEdge<V,E>> transformNodes(final Function<? super DAGNode<V,E>,? extends DAGNode<V,E>> func) {
189         return new Function<DAGEdge<V, E>, DAGEdge<V, E>>() {
190             @Nullable
191             @Override
192             public DAGEdge<V, E> apply(@Nullable DAGEdge<V, E> input) {
193                 if (input == null) {
194                     return null;
195                 }
196                 DAGNode<V,E> nt, nh;
197                 nt = func.apply(input.getTail());
198                 nh = func.apply(input.getHead());
199                 if (nt == null) {
200                     nt = input.getTail();
201                 }
202                 if (nh == null) {
203                     nh = input.getHead();
204                 }
205                 if (!nt.equals(input.getTail()) || !nh.equals(input.getHead())) {
206                     return create(nh, nt, input.getLabel());
207                 } else {
208                     return input;
209                 }
210             }
211         };
212     }
213 }