jgrapht-jdk1.6

16:37:51.814 INFO  jd.cli.Main - Decompiling jgrapht-jdk1.6.jar
package org.jgrapht;

import java.util.Set;

public abstract interface DirectedGraph<V, E>
  extends Graph<V, E>
{
  public abstract int inDegreeOf(V paramV);
  
  public abstract Set<E> incomingEdgesOf(V paramV);
  
  public abstract int outDegreeOf(V paramV);
  
  public abstract Set<E> outgoingEdgesOf(V paramV);
}

/* Location:
 * Qualified Name:     org.jgrapht.DirectedGraph
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

public abstract interface EdgeFactory<V, E>
{
  public abstract E createEdge(V paramV1, V paramV2);
}

/* Location:
 * Qualified Name:     org.jgrapht.EdgeFactory
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

import java.util.Collection;
import java.util.Set;

public abstract interface Graph<V, E>
{
  public abstract Set<E> getAllEdges(V paramV1, V paramV2);
  
  public abstract E getEdge(V paramV1, V paramV2);
  
  public abstract EdgeFactory<V, E> getEdgeFactory();
  
  public abstract E addEdge(V paramV1, V paramV2);
  
  public abstract boolean addEdge(V paramV1, V paramV2, E paramE);
  
  public abstract boolean addVertex(V paramV);
  
  public abstract boolean containsEdge(V paramV1, V paramV2);
  
  public abstract boolean containsEdge(E paramE);
  
  public abstract boolean containsVertex(V paramV);
  
  public abstract Set<E> edgeSet();
  
  public abstract Set<E> edgesOf(V paramV);
  
  public abstract boolean removeAllEdges(Collection<? extends E> paramCollection);
  
  public abstract Set<E> removeAllEdges(V paramV1, V paramV2);
  
  public abstract boolean removeAllVertices(Collection<? extends V> paramCollection);
  
  public abstract E removeEdge(V paramV1, V paramV2);
  
  public abstract boolean removeEdge(E paramE);
  
  public abstract boolean removeVertex(V paramV);
  
  public abstract Set<V> vertexSet();
  
  public abstract V getEdgeSource(E paramE);
  
  public abstract V getEdgeTarget(E paramE);
  
  public abstract double getEdgeWeight(E paramE);
}

/* Location:
 * Qualified Name:     org.jgrapht.Graph
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

@Deprecated
public abstract class GraphHelper
  extends Graphs
{}

/* Location:
 * Qualified Name:     org.jgrapht.GraphHelper
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

public abstract interface GraphMapping<V, E>
{
  public abstract V getVertexCorrespondence(V paramV, boolean paramBoolean);
  
  public abstract E getEdgeCorrespondence(E paramE, boolean paramBoolean);
}

/* Location:
 * Qualified Name:     org.jgrapht.GraphMapping
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

import java.util.List;

public abstract interface GraphPath<V, E>
{
  public abstract Graph<V, E> getGraph();
  
  public abstract V getStartVertex();
  
  public abstract V getEndVertex();
  
  public abstract List<E> getEdgeList();
  
  public abstract double getWeight();
}

/* Location:
 * Qualified Name:     org.jgrapht.GraphPath
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import org.jgrapht.graph.AsUndirectedGraph;

public abstract class Graphs
{
  public static <V, E> E addEdge(Graph<V, E> paramGraph, V paramV1, V paramV2, double paramDouble)
  {
    EdgeFactory localEdgeFactory = paramGraph.getEdgeFactory();
    Object localObject = localEdgeFactory.createEdge(paramV1, paramV2);
    assert ((paramGraph instanceof WeightedGraph)) : paramGraph.getClass();
    ((WeightedGraph)paramGraph).setEdgeWeight(localObject, paramDouble);
    return (E)(paramGraph.addEdge(paramV1, paramV2, localObject) ? localObject : null);
  }
  
  public static <V, E> E addEdgeWithVertices(Graph<V, E> paramGraph, V paramV1, V paramV2)
  {
    paramGraph.addVertex(paramV1);
    paramGraph.addVertex(paramV2);
    return (E)paramGraph.addEdge(paramV1, paramV2);
  }
  
  public static <V, E> boolean addEdgeWithVertices(Graph<V, E> paramGraph1, Graph<V, E> paramGraph2, E paramE)
  {
    Object localObject1 = paramGraph2.getEdgeSource(paramE);
    Object localObject2 = paramGraph2.getEdgeTarget(paramE);
    paramGraph1.addVertex(localObject1);
    paramGraph1.addVertex(localObject2);
    return paramGraph1.addEdge(localObject1, localObject2, paramE);
  }
  
  public static <V, E> E addEdgeWithVertices(Graph<V, E> paramGraph, V paramV1, V paramV2, double paramDouble)
  {
    paramGraph.addVertex(paramV1);
    paramGraph.addVertex(paramV2);
    return (E)addEdge(paramGraph, paramV1, paramV2, paramDouble);
  }
  
  public static <V, E> boolean addGraph(Graph<? super V, ? super E> paramGraph, Graph<V, E> paramGraph1)
  {
    boolean bool = addAllVertices(paramGraph, paramGraph1.vertexSet());
    bool |= addAllEdges(paramGraph, paramGraph1, paramGraph1.edgeSet());
    return bool;
  }
  
  public static <V, E> void addGraphReversed(DirectedGraph<? super V, ? super E> paramDirectedGraph, DirectedGraph<V, E> paramDirectedGraph1)
  {
    addAllVertices(paramDirectedGraph, paramDirectedGraph1.vertexSet());
    Iterator localIterator = paramDirectedGraph1.edgeSet().iterator();
    while (localIterator.hasNext())
    {
      Object localObject = localIterator.next();
      paramDirectedGraph.addEdge(paramDirectedGraph1.getEdgeTarget(localObject), paramDirectedGraph1.getEdgeSource(localObject));
    }
  }
  
  public static <V, E> boolean addAllEdges(Graph<? super V, ? super E> paramGraph, Graph<V, E> paramGraph1, Collection<? extends E> paramCollection)
  {
    boolean bool = false;
    Iterator localIterator = paramCollection.iterator();
    while (localIterator.hasNext())
    {
      Object localObject1 = localIterator.next();
      Object localObject2 = paramGraph1.getEdgeSource(localObject1);
      Object localObject3 = paramGraph1.getEdgeTarget(localObject1);
      paramGraph.addVertex(localObject2);
      paramGraph.addVertex(localObject3);
      bool |= paramGraph.addEdge(localObject2, localObject3, localObject1);
    }
    return bool;
  }
  
  public static <V, E> boolean addAllVertices(Graph<? super V, ? super E> paramGraph, Collection<? extends V> paramCollection)
  {
    boolean bool = false;
    Iterator localIterator = paramCollection.iterator();
    while (localIterator.hasNext())
    {
      Object localObject = localIterator.next();
      bool |= paramGraph.addVertex(localObject);
    }
    return bool;
  }
  
  public static <V, E> List<V> neighborListOf(Graph<V, E> paramGraph, V paramV)
  {
    ArrayList localArrayList = new ArrayList();
    Iterator localIterator = paramGraph.edgesOf(paramV).iterator();
    while (localIterator.hasNext())
    {
      Object localObject = localIterator.next();
      localArrayList.add(getOppositeVertex(paramGraph, localObject, paramV));
    }
    return localArrayList;
  }
  
  public static <V, E> List<V> predecessorListOf(DirectedGraph<V, E> paramDirectedGraph, V paramV)
  {
    ArrayList localArrayList = new ArrayList();
    Set localSet = paramDirectedGraph.incomingEdgesOf(paramV);
    Iterator localIterator = localSet.iterator();
    while (localIterator.hasNext())
    {
      Object localObject = localIterator.next();
      localArrayList.add(getOppositeVertex(paramDirectedGraph, localObject, paramV));
    }
    return localArrayList;
  }
  
  public static <V, E> List<V> successorListOf(DirectedGraph<V, E> paramDirectedGraph, V paramV)
  {
    ArrayList localArrayList = new ArrayList();
    Set localSet = paramDirectedGraph.outgoingEdgesOf(paramV);
    Iterator localIterator = localSet.iterator();
    while (localIterator.hasNext())
    {
      Object localObject = localIterator.next();
      localArrayList.add(getOppositeVertex(paramDirectedGraph, localObject, paramV));
    }
    return localArrayList;
  }
  
  public static <V, E> UndirectedGraph<V, E> undirectedGraph(Graph<V, E> paramGraph)
  {
    if ((paramGraph instanceof DirectedGraph)) {
      return new AsUndirectedGraph((DirectedGraph)paramGraph);
    }
    if ((paramGraph instanceof UndirectedGraph)) {
      return (UndirectedGraph)paramGraph;
    }
    throw new IllegalArgumentException("Graph must be either DirectedGraph or UndirectedGraph");
  }
  
  public static <V, E> boolean testIncidence(Graph<V, E> paramGraph, E paramE, V paramV)
  {
    return (paramGraph.getEdgeSource(paramE).equals(paramV)) || (paramGraph.getEdgeTarget(paramE).equals(paramV));
  }
  
  public static <V, E> V getOppositeVertex(Graph<V, E> paramGraph, E paramE, V paramV)
  {
    Object localObject1 = paramGraph.getEdgeSource(paramE);
    Object localObject2 = paramGraph.getEdgeTarget(paramE);
    if (paramV.equals(localObject1)) {
      return (V)localObject2;
    }
    if (paramV.equals(localObject2)) {
      return (V)localObject1;
    }
    throw new IllegalArgumentException("no such vertex");
  }
  
  public static <V, E> List<V> getPathVertexList(GraphPath<V, E> paramGraphPath)
  {
    Graph localGraph = paramGraphPath.getGraph();
    ArrayList localArrayList = new ArrayList();
    Object localObject1 = paramGraphPath.getStartVertex();
    localArrayList.add(localObject1);
    Iterator localIterator = paramGraphPath.getEdgeList().iterator();
    while (localIterator.hasNext())
    {
      Object localObject2 = localIterator.next();
      localObject1 = getOppositeVertex(localGraph, localObject2, localObject1);
      localArrayList.add(localObject1);
    }
    return localArrayList;
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.Graphs
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

import org.jgrapht.event.GraphListener;
import org.jgrapht.event.VertexSetListener;

public abstract interface ListenableGraph<V, E>
  extends Graph<V, E>
{
  public abstract void addGraphListener(GraphListener<V, E> paramGraphListener);
  
  public abstract void addVertexSetListener(VertexSetListener<V> paramVertexSetListener);
  
  public abstract void removeGraphListener(GraphListener<V, E> paramGraphListener);
  
  public abstract void removeVertexSetListener(VertexSetListener<V> paramVertexSetListener);
}

/* Location:
 * Qualified Name:     org.jgrapht.ListenableGraph
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

public abstract interface UndirectedGraph<V, E>
  extends Graph<V, E>
{
  public abstract int degreeOf(V paramV);
}

/* Location:
 * Qualified Name:     org.jgrapht.UndirectedGraph
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

public abstract interface VertexFactory<V>
{
  public abstract V createVertex();
}

/* Location:
 * Qualified Name:     org.jgrapht.VertexFactory
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht;

public abstract interface WeightedGraph<V, E>
  extends Graph<V, E>
{
  public static final double DEFAULT_EDGE_WEIGHT = 1.0D;
  
  public abstract void setEdgeWeight(E paramE, double paramDouble);
}

/* Location:
 * Qualified Name:     org.jgrapht.WeightedGraph
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.jgrapht.Graph;
import org.jgrapht.Graphs;

abstract class AbstractPathElement<V, E>
{
  protected int nHops;
  protected E prevEdge;
  protected AbstractPathElement<V, E> prevPathElement;
  private V vertex;
  
  protected AbstractPathElement(Graph<V, E> paramGraph, AbstractPathElement<V, E> paramAbstractPathElement, E paramE)
  {
    vertex = Graphs.getOppositeVertex(paramGraph, paramE, paramAbstractPathElement.getVertex());
    prevEdge = paramE;
    prevPathElement = paramAbstractPathElement;
    nHops = (paramAbstractPathElement.getHopCount() + 1);
  }
  
  protected AbstractPathElement(AbstractPathElement<V, E> paramAbstractPathElement)
  {
    nHops = nHops;
    prevEdge = prevEdge;
    prevPathElement = prevPathElement;
    vertex = vertex;
  }
  
  protected AbstractPathElement(V paramV)
  {
    vertex = paramV;
    prevEdge = null;
    prevPathElement = null;
    nHops = 0;
  }
  
  public List<E> createEdgeListPath()
  {
    ArrayList localArrayList = new ArrayList();
    for (AbstractPathElement localAbstractPathElement = this; localAbstractPathElement.getPrevEdge() != null; localAbstractPathElement = localAbstractPathElement.getPrevPathElement()) {
      localArrayList.add(localAbstractPathElement.getPrevEdge());
    }
    Collections.reverse(localArrayList);
    return localArrayList;
  }
  
  public int getHopCount()
  {
    return nHops;
  }
  
  public E getPrevEdge()
  {
    return (E)prevEdge;
  }
  
  public AbstractPathElement<V, E> getPrevPathElement()
  {
    return prevPathElement;
  }
  
  public V getVertex()
  {
    return (V)vertex;
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.AbstractPathElement
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.AbstractList;
import java.util.ArrayList;
import org.jgrapht.Graph;
import org.jgrapht.Graphs;

abstract class AbstractPathElementList<V, E, T extends AbstractPathElement<V, E>>
  extends AbstractList<T>
{
  protected Graph<V, E> graph;
  protected int maxSize;
  protected ArrayList<T> pathElements = new ArrayList();
  protected V vertex;
  
  protected AbstractPathElementList(Graph<V, E> paramGraph, int paramInt, AbstractPathElementList<V, E, T> paramAbstractPathElementList, E paramE)
  {
    if (paramInt <= 0) {
      throw new IllegalArgumentException("maxSize is negative or 0");
    }
    if (paramAbstractPathElementList == null) {
      throw new NullPointerException("elementList is null");
    }
    if (paramE == null) {
      throw new NullPointerException("edge is null");
    }
    graph = paramGraph;
    maxSize = paramInt;
    vertex = Graphs.getOppositeVertex(paramGraph, paramE, paramAbstractPathElementList.getVertex());
  }
  
  protected AbstractPathElementList(Graph<V, E> paramGraph, int paramInt, T paramT)
  {
    if (paramInt <= 0) {
      throw new IllegalArgumentException("maxSize is negative or 0");
    }
    if (paramT == null) {
      throw new NullPointerException("pathElement is null");
    }
    if (paramT.getPrevEdge() != null) {
      throw new IllegalArgumentException("path must be empty");
    }
    graph = paramGraph;
    maxSize = paramInt;
    vertex = paramT.getVertex();
    pathElements.add(paramT);
  }
  
  protected AbstractPathElementList(Graph<V, E> paramGraph, int paramInt, V paramV)
  {
    if (paramInt <= 0) {
      throw new IllegalArgumentException("maxSize is negative or 0");
    }
    graph = paramGraph;
    maxSize = paramInt;
    vertex = paramV;
  }
  
  public T get(int paramInt)
  {
    return (AbstractPathElement)pathElements.get(paramInt);
  }
  
  public V getVertex()
  {
    return (V)vertex;
  }
  
  public int size()
  {
    return pathElements.size();
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.AbstractPathElementList
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import org.jgrapht.DirectedGraph;
import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.UndirectedGraph;

class BellmanFordIterator<V, E>
  implements Iterator<List<V>>
{
  protected static final String NEGATIVE_UNDIRECTED_EDGE = "Negativeedge-weights are not allowed in an unidrected graph!";
  protected Graph<V, E> graph;
  protected V startVertex;
  private List<V> prevImprovedVertices = new ArrayList();
  private Map<V, BellmanFordPathElement<V, E>> prevVertexData;
  private boolean startVertexEncountered = false;
  private Map<V, BellmanFordPathElement<V, E>> vertexData;
  private double epsilon;
  
  protected BellmanFordIterator(Graph<V, E> paramGraph, V paramV, double paramDouble)
  {
    assertBellmanFordIterator(paramGraph, paramV);
    graph = paramGraph;
    startVertex = paramV;
    epsilon = paramDouble;
  }
  
  public BellmanFordPathElement<V, E> getPathElement(V paramV)
  {
    return getSeenData(paramV);
  }
  
  public boolean hasNext()
  {
    if (!startVertexEncountered) {
      encounterStartVertex();
    }
    return !prevImprovedVertices.isEmpty();
  }
  
  public List<V> next()
  {
    if (!startVertexEncountered) {
      encounterStartVertex();
    }
    if (hasNext())
    {
      ArrayList localArrayList = new ArrayList();
      for (int i = prevImprovedVertices.size() - 1; i >= 0; i--)
      {
        Object localObject1 = prevImprovedVertices.get(i);
        Iterator localIterator = edgesOfIterator(localObject1);
        while (localIterator.hasNext())
        {
          Object localObject2 = localIterator.next();
          Object localObject3 = Graphs.getOppositeVertex(graph, localObject2, localObject1);
          if (getPathElement(localObject3) != null)
          {
            boolean bool = relaxVertexAgain(localObject3, localObject2);
            if (bool) {
              localArrayList.add(localObject3);
            }
          }
          else
          {
            relaxVertex(localObject3, localObject2);
            localArrayList.add(localObject3);
          }
        }
      }
      savePassData(localArrayList);
      return localArrayList;
    }
    throw new NoSuchElementException();
  }
  
  public void remove()
  {
    throw new UnsupportedOperationException();
  }
  
  protected void assertValidEdge(E paramE)
  {
    if (((graph instanceof UndirectedGraph)) && (graph.getEdgeWeight(paramE) < 0.0D)) {
      throw new IllegalArgumentException("Negativeedge-weights are not allowed in an unidrected graph!");
    }
  }
  
  protected double calculatePathCost(V paramV, E paramE)
  {
    Object localObject = Graphs.getOppositeVertex(graph, paramE, paramV);
    BellmanFordPathElement localBellmanFordPathElement = getPrevSeenData(localObject);
    double d = graph.getEdgeWeight(paramE);
    if (!localBellmanFordPathElement.getVertex().equals(startVertex)) {
      d += localBellmanFordPathElement.getCost();
    }
    return d;
  }
  
  protected Iterator<E> edgesOfIterator(V paramV)
  {
    if ((graph instanceof DirectedGraph)) {
      return ((DirectedGraph)graph).outgoingEdgesOf(paramV).iterator();
    }
    return graph.edgesOf(paramV).iterator();
  }
  
  protected BellmanFordPathElement<V, E> getPrevSeenData(V paramV)
  {
    return (BellmanFordPathElement)prevVertexData.get(paramV);
  }
  
  protected BellmanFordPathElement<V, E> getSeenData(V paramV)
  {
    return (BellmanFordPathElement)vertexData.get(paramV);
  }
  
  protected boolean isSeenVertex(V paramV)
  {
    return vertexData.containsKey(paramV);
  }
  
  protected BellmanFordPathElement<V, E> putPrevSeenData(V paramV, BellmanFordPathElement<V, E> paramBellmanFordPathElement)
  {
    if (prevVertexData == null) {
      prevVertexData = new HashMap();
    }
    return (BellmanFordPathElement)prevVertexData.put(paramV, paramBellmanFordPathElement);
  }
  
  protected BellmanFordPathElement<V, E> putSeenData(V paramV, BellmanFordPathElement<V, E> paramBellmanFordPathElement)
  {
    if (vertexData == null) {
      vertexData = new HashMap();
    }
    return (BellmanFordPathElement)vertexData.put(paramV, paramBellmanFordPathElement);
  }
  
  private void assertBellmanFordIterator(Graph<V, E> paramGraph, V paramV)
  {
    if (!paramGraph.containsVertex(paramV)) {
      throw new IllegalArgumentException("Graph must contain the start vertex!");
    }
  }
  
  private BellmanFordPathElement<V, E> createSeenData(V paramV, E paramE, double paramDouble)
  {
    BellmanFordPathElement localBellmanFordPathElement1 = getPrevSeenData(Graphs.getOppositeVertex(graph, paramE, paramV));
    BellmanFordPathElement localBellmanFordPathElement2 = new BellmanFordPathElement(graph, localBellmanFordPathElement1, paramE, paramDouble, epsilon);
    return localBellmanFordPathElement2;
  }
  
  private void encounterStartVertex()
  {
    BellmanFordPathElement localBellmanFordPathElement = new BellmanFordPathElement(startVertex, epsilon);
    prevImprovedVertices.add(startVertex);
    putSeenData(startVertex, localBellmanFordPathElement);
    putPrevSeenData(startVertex, localBellmanFordPathElement);
    startVertexEncountered = true;
  }
  
  private void relaxVertex(V paramV, E paramE)
  {
    assertValidEdge(paramE);
    double d = calculatePathCost(paramV, paramE);
    BellmanFordPathElement localBellmanFordPathElement = createSeenData(paramV, paramE, d);
    putSeenData(paramV, localBellmanFordPathElement);
  }
  
  private boolean relaxVertexAgain(V paramV, E paramE)
  {
    assertValidEdge(paramE);
    double d = calculatePathCost(paramV, paramE);
    BellmanFordPathElement localBellmanFordPathElement1 = getPrevSeenData(Graphs.getOppositeVertex(graph, paramE, paramV));
    BellmanFordPathElement localBellmanFordPathElement2 = getSeenData(paramV);
    return localBellmanFordPathElement2.improve(localBellmanFordPathElement1, paramE, d);
  }
  
  private void savePassData(List<V> paramList)
  {
    Iterator localIterator = paramList.iterator();
    while (localIterator.hasNext())
    {
      Object localObject = localIterator.next();
      BellmanFordPathElement localBellmanFordPathElement1 = getSeenData(localObject);
      BellmanFordPathElement localBellmanFordPathElement2 = new BellmanFordPathElement(localBellmanFordPathElement1);
      putPrevSeenData(localObject, localBellmanFordPathElement2);
    }
    prevImprovedVertices = paramList;
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BellmanFordIterator
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import org.jgrapht.Graph;

final class BellmanFordPathElement<V, E>
  extends AbstractPathElement<V, E>
{
  private double cost = 0.0D;
  private double epsilon;
  
  protected BellmanFordPathElement(Graph<V, E> paramGraph, BellmanFordPathElement<V, E> paramBellmanFordPathElement, E paramE, double paramDouble1, double paramDouble2)
  {
    super(paramGraph, paramBellmanFordPathElement, paramE);
    cost = paramDouble1;
    epsilon = paramDouble2;
  }
  
  BellmanFordPathElement(BellmanFordPathElement<V, E> paramBellmanFordPathElement)
  {
    super(paramBellmanFordPathElement);
    cost = cost;
    epsilon = epsilon;
  }
  
  protected BellmanFordPathElement(V paramV, double paramDouble)
  {
    super(paramV);
    cost = 0.0D;
    epsilon = paramDouble;
  }
  
  public double getCost()
  {
    return cost;
  }
  
  protected boolean improve(BellmanFordPathElement<V, E> paramBellmanFordPathElement, E paramE, double paramDouble)
  {
    if (paramDouble < getCost() - epsilon)
    {
      prevPathElement = paramBellmanFordPathElement;
      prevEdge = paramE;
      cost = paramDouble;
      nHops = (paramBellmanFordPathElement.getHopCount() + 1);
      return true;
    }
    return false;
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BellmanFordPathElement
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.List;
import java.util.Set;
import org.jgrapht.Graph;

public class BellmanFordShortestPath<V, E>
{
  private static final double DEFAULT_EPSILON = 1.0E-9D;
  protected Graph<V, E> graph;
  protected V startVertex;
  private BellmanFordIterator<V, E> iter;
  private int nMaxHops;
  private int passNumber;
  private double epsilon;
  
  public BellmanFordShortestPath(Graph<V, E> paramGraph, V paramV)
  {
    this(paramGraph, paramV, paramGraph.vertexSet().size() - 1);
  }
  
  public BellmanFordShortestPath(Graph<V, E> paramGraph, V paramV, int paramInt)
  {
    this(paramGraph, paramV, paramInt, 1.0E-9D);
  }
  
  public BellmanFordShortestPath(Graph<V, E> paramGraph, V paramV, int paramInt, double paramDouble)
  {
    startVertex = paramV;
    nMaxHops = paramInt;
    graph = paramGraph;
    passNumber = 1;
    epsilon = paramDouble;
  }
  
  public double getCost(V paramV)
  {
    assertGetPath(paramV);
    lazyCalculate();
    BellmanFordPathElement localBellmanFordPathElement = iter.getPathElement(paramV);
    if (localBellmanFordPathElement == null) {
      return Double.POSITIVE_INFINITY;
    }
    return localBellmanFordPathElement.getCost();
  }
  
  public List<E> getPathEdgeList(V paramV)
  {
    assertGetPath(paramV);
    lazyCalculate();
    BellmanFordPathElement localBellmanFordPathElement = iter.getPathElement(paramV);
    if (localBellmanFordPathElement == null) {
      return null;
    }
    return localBellmanFordPathElement.createEdgeListPath();
  }
  
  private void assertGetPath(V paramV)
  {
    if (paramV.equals(startVertex)) {
      throw new IllegalArgumentException("The end vertex is the same as the start vertex!");
    }
    if (!graph.containsVertex(paramV)) {
      throw new IllegalArgumentException("Graph must contain the end vertex!");
    }
  }
  
  private void lazyCalculate()
  {
    if (iter == null) {
      iter = new BellmanFordIterator(graph, startVertex, epsilon);
    }
    while ((passNumber <= nMaxHops) && (iter.hasNext()))
    {
      iter.next();
      passNumber += 1;
    }
  }
  
  public static <V, E> List<E> findPathBetween(Graph<V, E> paramGraph, V paramV1, V paramV2)
  {
    BellmanFordShortestPath localBellmanFordShortestPath = new BellmanFordShortestPath(paramGraph, paramV1);
    return localBellmanFordShortestPath.getPathEdgeList(paramV2);
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BellmanFordShortestPath
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import org.jgrapht.UndirectedGraph;

public class BiconnectivityInspector<V, E>
{
  private BlockCutpointGraph<V, E> blockCutpointGraph;
  
  public BiconnectivityInspector(UndirectedGraph<V, E> paramUndirectedGraph)
  {
    blockCutpointGraph = new BlockCutpointGraph(paramUndirectedGraph);
  }
  
  public Set<Set<V>> getBiconnectedVertexComponents()
  {
    HashSet localHashSet = new HashSet();
    Iterator localIterator = blockCutpointGraph.vertexSet().iterator();
    while (localIterator.hasNext())
    {
      UndirectedGraph localUndirectedGraph = (UndirectedGraph)localIterator.next();
      if (!localUndirectedGraph.edgeSet().isEmpty()) {
        localHashSet.add(localUndirectedGraph.vertexSet());
      }
    }
    return localHashSet;
  }
  
  public Set<Set<V>> getBiconnectedVertexComponents(V paramV)
  {
    HashSet localHashSet = new HashSet();
    Iterator localIterator = getBiconnectedVertexComponents().iterator();
    while (localIterator.hasNext())
    {
      Set localSet = (Set)localIterator.next();
      if (localSet.contains(paramV)) {
        localHashSet.add(localSet);
      }
    }
    return localHashSet;
  }
  
  public Set<V> getCutpoints()
  {
    return blockCutpointGraph.getCutpoints();
  }
  
  public boolean isBiconnected()
  {
    return blockCutpointGraph.vertexSet().size() == 1;
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BiconnectivityInspector
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import org.jgrapht.graph.DefaultEdge;

class BlockCutpointGraph$BCGEdge
  extends DefaultEdge
{
  private static final long serialVersionUID = -5115006161815760059L;
  private V source;
  private V target;
  
  public BlockCutpointGraph$BCGEdge(V paramV1, V paramV2)
  {
    source = paramV2;
    Object localObject;
    target = localObject;
  }
  
  public V getSource()
  {
    return (V)source;
  }
  
  public V getTarget()
  {
    return (V)target;
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BlockCutpointGraph.BCGEdge
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.Set;
import org.jgrapht.graph.MaskFunctor;

class BlockCutpointGraph$VertexComponentForbiddenFunction
  implements MaskFunctor<V, E>
{
  private Set<V> vertexComponent;
  
  public BlockCutpointGraph$VertexComponentForbiddenFunction(Set<V> paramSet)
  {
    Set localSet;
    vertexComponent = localSet;
  }
  
  public boolean isEdgeMasked(E paramE)
  {
    return false;
  }
  
  public boolean isVertexMasked(V paramV)
  {
    return !vertexComponent.contains(paramV);
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BlockCutpointGraph.VertexComponentForbiddenFunction
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import org.jgrapht.DirectedGraph;
import org.jgrapht.Graphs;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.MaskFunctor;
import org.jgrapht.graph.SimpleDirectedGraph;
import org.jgrapht.graph.SimpleGraph;
import org.jgrapht.graph.UndirectedMaskSubgraph;

public class BlockCutpointGraph<V, E>
  extends SimpleGraph<UndirectedGraph<V, E>, DefaultEdge>
{
  private static final long serialVersionUID = -9101341117013163934L;
  private Set<V> cutpoints = new HashSet();
  private DirectedGraph<V, DefaultEdge> dfsTree;
  private UndirectedGraph<V, E> graph;
  private int numOrder;
  private Deque<BlockCutpointGraph<V, E>.BCGEdge> stack = new ArrayDeque();
  private Map<V, Set<UndirectedGraph<V, E>>> vertex2biconnectedSubgraphs = new HashMap();
  private Map<V, UndirectedGraph<V, E>> vertex2block = new HashMap();
  private Map<V, Integer> vertex2numOrder = new HashMap();
  
  public BlockCutpointGraph(UndirectedGraph<V, E> paramUndirectedGraph)
  {
    super(DefaultEdge.class);
    graph = paramUndirectedGraph;
    dfsTree = new SimpleDirectedGraph(DefaultEdge.class);
    Object localObject1 = paramUndirectedGraph.vertexSet().iterator().next();
    dfsTree.addVertex(localObject1);
    dfsVisit(localObject1, localObject1);
    if (dfsTree.edgesOf(localObject1).size() > 1) {
      cutpoints.add(localObject1);
    } else {
      cutpoints.remove(localObject1);
    }
    Iterator localIterator1 = cutpoints.iterator();
    while (localIterator1.hasNext())
    {
      Object localObject2 = localIterator1.next();
      SimpleGraph localSimpleGraph = new SimpleGraph(graph.getEdgeFactory());
      localSimpleGraph.addVertex(localObject2);
      vertex2block.put(localObject2, localSimpleGraph);
      addVertex(localSimpleGraph);
      Set localSet = getBiconnectedSubgraphs(localObject2);
      Iterator localIterator2 = localSet.iterator();
      while (localIterator2.hasNext())
      {
        UndirectedGraph localUndirectedGraph = (UndirectedGraph)localIterator2.next();
        assert (vertexSet().contains(localUndirectedGraph));
        addEdge(localSimpleGraph, localUndirectedGraph);
      }
    }
  }
  
  public UndirectedGraph<V, E> getBlock(V paramV)
  {
    if (!graph.vertexSet().contains(paramV)) {
      throw new IllegalArgumentException("No such vertex in the graph!");
    }
    return (UndirectedGraph)vertex2block.get(paramV);
  }
  
  public Set<V> getCutpoints()
  {
    return cutpoints;
  }
  
  public boolean isCutpoint(V paramV)
  {
    if (!graph.vertexSet().contains(paramV)) {
      throw new IllegalArgumentException("No such vertex in the graph!");
    }
    return cutpoints.contains(paramV);
  }
  
  private void biconnectedComponentFinished(V paramV1, V paramV2)
  {
    cutpoints.add(paramV1);
    HashSet localHashSet1 = new HashSet();
    HashSet localHashSet2 = new HashSet();
    for (BCGEdge localBCGEdge = (BCGEdge)stack.removeLast(); (getNumOrder(localBCGEdge.getSource()) >= getNumOrder(paramV2)) && (!stack.isEmpty()); localBCGEdge = (BCGEdge)stack.removeLast())
    {
      localHashSet2.add(localBCGEdge);
      localHashSet1.add(localBCGEdge.getSource());
      localHashSet1.add(localBCGEdge.getTarget());
    }
    localHashSet2.add(localBCGEdge);
    localHashSet1.add(localBCGEdge.getSource());
    localHashSet1.add(localBCGEdge.getTarget());
    VertexComponentForbiddenFunction localVertexComponentForbiddenFunction = new VertexComponentForbiddenFunction(localHashSet1);
    UndirectedMaskSubgraph localUndirectedMaskSubgraph = new UndirectedMaskSubgraph(graph, localVertexComponentForbiddenFunction);
    Iterator localIterator = localHashSet1.iterator();
    while (localIterator.hasNext())
    {
      Object localObject = localIterator.next();
      vertex2block.put(localObject, localUndirectedMaskSubgraph);
      getBiconnectedSubgraphs(localObject).add(localUndirectedMaskSubgraph);
    }
    addVertex(localUndirectedMaskSubgraph);
  }
  
  private int dfsVisit(V paramV1, V paramV2)
  {
    numOrder += 1;
    int i = numOrder;
    setNumOrder(paramV1, numOrder);
    Iterator localIterator = graph.edgesOf(paramV1).iterator();
    while (localIterator.hasNext())
    {
      Object localObject1 = localIterator.next();
      Object localObject2 = Graphs.getOppositeVertex(graph, localObject1, paramV1);
      BCGEdge localBCGEdge;
      if (getNumOrder(localObject2) == 0)
      {
        dfsTree.addVertex(localObject2);
        localBCGEdge = new BCGEdge(paramV1, localObject2);
        dfsTree.addEdge(paramV1, localObject2, localBCGEdge);
        stack.add(localBCGEdge);
        int j = dfsVisit(localObject2, paramV1);
        i = Math.min(j, i);
        if (j >= getNumOrder(paramV1)) {
          biconnectedComponentFinished(paramV1, localObject2);
        }
      }
      else if ((getNumOrder(localObject2) < getNumOrder(paramV1)) && (!localObject2.equals(paramV2)))
      {
        localBCGEdge = new BCGEdge(paramV1, localObject2);
        stack.add(localBCGEdge);
        i = Math.min(getNumOrder(localObject2), i);
      }
    }
    return i;
  }
  
  private Set<UndirectedGraph<V, E>> getBiconnectedSubgraphs(V paramV)
  {
    Object localObject = (Set)vertex2biconnectedSubgraphs.get(paramV);
    if (localObject == null)
    {
      localObject = new HashSet();
      vertex2biconnectedSubgraphs.put(paramV, localObject);
    }
    return (Set<UndirectedGraph<V, E>>)localObject;
  }
  
  private int getNumOrder(V paramV)
  {
    assert (paramV != null);
    Integer localInteger = (Integer)vertex2numOrder.get(paramV);
    if (localInteger == null) {
      return 0;
    }
    return localInteger.intValue();
  }
  
  private void setNumOrder(V paramV, int paramInt)
  {
    vertex2numOrder.put(paramV, Integer.valueOf(paramInt));
  }
  
  private class VertexComponentForbiddenFunction
    implements MaskFunctor<V, E>
  {
    private Set<V> vertexComponent;
    
    public VertexComponentForbiddenFunction()
    {
      Set localSet;
      vertexComponent = localSet;
    }
    
    public boolean isEdgeMasked(E paramE)
    {
      return false;
    }
    
    public boolean isVertexMasked(V paramV)
    {
      return !vertexComponent.contains(paramV);
    }
  }
  
  private class BCGEdge
    extends DefaultEdge
  {
    private static final long serialVersionUID = -5115006161815760059L;
    private V source;
    private V target;
    
    public BCGEdge(V paramV)
    {
      source = paramV;
      Object localObject;
      target = localObject;
    }
    
    public V getSource()
    {
      return (V)source;
    }
    
    public V getTarget()
    {
      return (V)target;
    }
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BlockCutpointGraph
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import org.jgrapht.Graph;

public class BronKerboschCliqueFinder<V, E>
{
  private final Graph<V, E> graph;
  private Collection<Set<V>> cliques;
  
  public BronKerboschCliqueFinder(Graph<V, E> paramGraph)
  {
    graph = paramGraph;
  }
  
  public Collection<Set<V>> getAllMaximalCliques()
  {
    cliques = new ArrayList();
    ArrayList localArrayList1 = new ArrayList();
    ArrayList localArrayList2 = new ArrayList();
    ArrayList localArrayList3 = new ArrayList();
    localArrayList2.addAll(graph.vertexSet());
    findCliques(localArrayList1, localArrayList2, localArrayList3);
    return cliques;
  }
  
  public Collection<Set<V>> getBiggestMaximalCliques()
  {
    getAllMaximalCliques();
    int i = 0;
    ArrayList localArrayList = new ArrayList();
    Iterator localIterator = cliques.iterator();
    Set localSet;
    while (localIterator.hasNext())
    {
      localSet = (Set)localIterator.next();
      if (i < localSet.size()) {
        i = localSet.size();
      }
    }
    localIterator = cliques.iterator();
    while (localIterator.hasNext())
    {
      localSet = (Set)localIterator.next();
      if (i == localSet.size()) {
        localArrayList.add(localSet);
      }
    }
    return localArrayList;
  }
  
  private void findCliques(List<V> paramList1, List<V> paramList2, List<V> paramList3)
  {
    ArrayList localArrayList1 = new ArrayList(paramList2);
    if (!end(paramList2, paramList3))
    {
      Iterator localIterator1 = localArrayList1.iterator();
      while (localIterator1.hasNext())
      {
        Object localObject1 = localIterator1.next();
        ArrayList localArrayList2 = new ArrayList();
        ArrayList localArrayList3 = new ArrayList();
        paramList1.add(localObject1);
        paramList2.remove(localObject1);
        Iterator localIterator2 = paramList2.iterator();
        Object localObject2;
        while (localIterator2.hasNext())
        {
          localObject2 = localIterator2.next();
          if (graph.containsEdge(localObject1, localObject2)) {
            localArrayList2.add(localObject2);
          }
        }
        localIterator2 = paramList3.iterator();
        while (localIterator2.hasNext())
        {
          localObject2 = localIterator2.next();
          if (graph.containsEdge(localObject1, localObject2)) {
            localArrayList3.add(localObject2);
          }
        }
        if ((localArrayList2.isEmpty()) && (localArrayList3.isEmpty())) {
          cliques.add(new HashSet(paramList1));
        } else {
          findCliques(paramList1, localArrayList2, localArrayList3);
        }
        paramList3.add(localObject1);
        paramList1.remove(localObject1);
      }
    }
  }
  
  private boolean end(List<V> paramList1, List<V> paramList2)
  {
    boolean bool = false;
    Iterator localIterator1 = paramList2.iterator();
    while (localIterator1.hasNext())
    {
      Object localObject1 = localIterator1.next();
      int i = 0;
      Iterator localIterator2 = paramList1.iterator();
      while (localIterator2.hasNext())
      {
        Object localObject2 = localIterator2.next();
        if (graph.containsEdge(localObject1, localObject2)) {
          i++;
        }
      }
      if (i == paramList1.size()) {
        bool = true;
      }
    }
    return bool;
  }
}

/* Location:
 * Qualified Name:     org.jgrapht.alg.BronKerboschCliqueFinder
 * Java Class Version: 6 (50.0)
 * JD-Core Version:    0.7.1
 */
package org.jgrapht.alg;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.util.VertexDegreeComparator;
import org.jgrapht.graph.UndirectedSubgraph;

public abstract class ChromaticNumber
{
  public static <V, E> int findGreedyChromaticNumber(UndirectedGraph<V, E> paramUndirectedGraph)
  {
    Map localMap = findGreedyColoredGroups(paramUndirectedGraph);
    return localMap
1 2 3 4 5 6 7 8 9 10 11 12 13

Further reading...

For more information on Java 1.5 Tiger, you may find Java 1.5 Tiger, A developer's Notebook by D. Flanagan and B. McLaughlin from O'Reilly of interest.

New!JAR listings


Copyright 2006-2017. Infinite Loop Ltd