Module org.jgrapht.core
Package org.jgrapht

Class Graphs

java.lang.Object
org.jgrapht.Graphs
public abstract class Graphs extends Object
A collection of utilities to assist with graph manipulation.
Author:
Barak Naveh

  • Constructor Summary

    Constructors
    Constructor
    Description
    Graphs()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V, E> boolean
    addAllEdges(Graph<? super V,? super E> destination, Graph<V,E> source, Collection<? extends E> edges)
    Adds a subset of the edges of the specified source graph to the specified destination graph.
    static <V, E> boolean
    addAllVertices(Graph<? super V,? super E> destination, Collection<? extends V> vertices)
    Adds all of the specified vertices to the destination graph.
    static <V, E> E
    addEdge(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
    Creates a new edge and adds it to the specified graph similarly to the Graph.addEdge(Object, Object) method.
    static <V, E> boolean
    addEdgeWithVertices(Graph<V,E> targetGraph, Graph<V,E> sourceGraph, E edge)
    Adds the specified edge to the graph, including its vertices if not already included.
    static <V, E> E
    addEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex)
    Adds the specified source and target vertices to the graph, if not already included, and creates a new edge and adds it to the specified graph similarly to the Graph.addEdge(Object, Object) method.
    static <V, E> E
    addEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
    Adds the specified source and target vertices to the graph, if not already included, and creates a new weighted edge and adds it to the specified graph similarly to the Graph.addEdge(Object, Object) method.
    static <V, E> boolean
    addGraph(Graph<? super V,? super E> destination, Graph<V,E> source)
    Adds all the vertices and all the edges of the specified source graph to the specified destination graph.
    static <V, E> void
    addGraphReversed(Graph<? super V,? super E> destination, Graph<V,E> source)
    Adds all the vertices and all the edges of the specified source digraph to the specified destination digraph, reversing all of the edges.
    static <V, E> void
    addIncomingEdges(Graph<V,E> graph, V target, Iterable<V> sources)
    Add edges from multiple source vertices to one target vertex.
    static <V, E> void
    addOutgoingEdges(Graph<V,E> graph, V source, Iterable<V> targets)
    Add edges from one source vertex to multiple target vertices.
    static <V, E> V
    getOppositeVertex(Graph<V,E> g, E e, V v)
    Gets the vertex opposite another vertex across an edge.
    static <V, E> VertexToIntegerMapping<V>
    getVertexToIntegerMapping(Graph<V,E> graph)
    Compute a new mapping from the vertices of a graph to the integer range $[0, n)$ where $n$ is the number of vertices in the graph.
    static <V, E> List<V>
    neighborListOf(Graph<V,E> g, V vertex)
    Returns a list of vertices that are the neighbors of a specified vertex.
    static <V, E> Set<V>
    neighborSetOf(Graph<V,E> g, V vertex)
    Returns a set of vertices that are neighbors of a specified vertex.
    static <V, E> List<V>
    predecessorListOf(Graph<V,E> g, V vertex)
    Returns a list of vertices that are the direct predecessors of a specified vertex.
    static <V, E> boolean
    removeVertexAndPreserveConnectivity(Graph<V,E> graph, Iterable<V> vertices)
    Removes all the given vertices from the given graph.
    static <V, E> boolean
    removeVertexAndPreserveConnectivity(Graph<V,E> graph, V vertex)
    Removes the given vertex from the given graph.
    static <V, E> boolean
    removeVerticesAndPreserveConnectivity(Graph<V,E> graph, Predicate<V> predicate)
    Filters vertices from the given graph and subsequently removes them.
    static <V, E> List<V>
    successorListOf(Graph<V,E> g, V vertex)
    Returns a list of vertices that are the direct successors of a specified vertex.
    static <V, E> boolean
    testIncidence(Graph<V,E> g, E e, V v)
    Tests whether an edge is incident to a vertex.
    static <V, E> Graph<V,E>
    undirectedGraph(Graph<V,E> g)
    Returns an undirected view of the specified graph.
    static <V, E> boolean
    vertexHasPredecessors(Graph<V,E> graph, V vertex)
    Check if a vertex has any direct predecessors.
    static <V, E> boolean
    vertexHasSuccessors(Graph<V,E> graph, V vertex)
    Check if a vertex has any direct successors.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Graphs

      public Graphs()

  • Method Details

    • addEdge

      public static <V, E> E addEdge(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
      Creates a new edge and adds it to the specified graph similarly to the Graph.addEdge(Object, Object) method.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph for which the edge to be added
      sourceVertex - source vertex of the edge
      targetVertex - target vertex of the edge
      weight - weight of the edge
      Returns:
      The newly created edge if added to the graph, otherwise null.
      Throws:
      UnsupportedOperationException - if the graph has no edge supplier
      See Also:

    • addEdgeWithVertices

      public static <V, E> E addEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex)
      Adds the specified source and target vertices to the graph, if not already included, and creates a new edge and adds it to the specified graph similarly to the Graph.addEdge(Object, Object) method.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph for which the specified edge to be added
      sourceVertex - source vertex of the edge
      targetVertex - target vertex of the edge
      Returns:
      The newly created edge if added to the graph, otherwise null.

    • addEdgeWithVertices

      public static <V, E> boolean addEdgeWithVertices(Graph<V,E> targetGraph, Graph<V,E> sourceGraph, E edge)
      Adds the specified edge to the graph, including its vertices if not already included.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      targetGraph - the graph for which the specified edge to be added
      sourceGraph - the graph in which the specified edge is already present
      edge - edge to add
      Returns:
      true if the target graph did not already contain the specified edge.

    • addEdgeWithVertices

      public static <V, E> E addEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
      Adds the specified source and target vertices to the graph, if not already included, and creates a new weighted edge and adds it to the specified graph similarly to the Graph.addEdge(Object, Object) method.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph for which the specified edge to be added
      sourceVertex - source vertex of the edge
      targetVertex - target vertex of the edge
      weight - weight of the edge
      Returns:
      The newly created edge if added to the graph, otherwise null.

    • addGraph

      public static <V, E> boolean addGraph(Graph<? super V,? super E> destination, Graph<V,E> source)
      Adds all the vertices and all the edges of the specified source graph to the specified destination graph. First all vertices of the source graph are added to the destination graph. Then every edge of the source graph is added to the destination graph. This method returns true if the destination graph has been modified as a result of this operation, otherwise it returns false.

      The behavior of this operation is undefined if any of the specified graphs is modified while operation is in progress.

      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      destination - the graph to which vertices and edges are added
      source - the graph used as source for vertices and edges to add
      Returns:
      true if and only if the destination graph has been changed as a result of this operation.

    • addGraphReversed

      public static <V, E> void addGraphReversed(Graph<? super V,? super E> destination, Graph<V,E> source)
      Adds all the vertices and all the edges of the specified source digraph to the specified destination digraph, reversing all of the edges. If you want to do this as a linked view of the source graph (rather than by copying to a destination graph), use EdgeReversedGraph instead.

      The behavior of this operation is undefined if any of the specified graphs is modified while operation is in progress.

      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      destination - the graph to which vertices and edges are added
      source - the graph used as source for vertices and edges to add
      See Also:

    • addAllEdges

      public static <V, E> boolean addAllEdges(Graph<? super V,? super E> destination, Graph<V,E> source, Collection<? extends E> edges)
      Adds a subset of the edges of the specified source graph to the specified destination graph. The behavior of this operation is undefined if either of the graphs is modified while the operation is in progress. addEdgeWithVertices(org.jgrapht.Graph<V, E>, V, V) is used for the transfer, so source vertexes will be added automatically to the target graph.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      destination - the graph to which edges are to be added
      source - the graph used as a source for edges to add
      edges - the edges to be added
      Returns:
      true if this graph changed as a result of the call

    • addAllVertices

      public static <V, E> boolean addAllVertices(Graph<? super V,? super E> destination, Collection<? extends V> vertices)
      Adds all of the specified vertices to the destination graph. The behavior of this operation is undefined if the specified vertex collection is modified while the operation is in progress. This method will invoke the Graph.addVertex(Object) method.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      destination - the graph to which edges are to be added
      vertices - the vertices to be added to the graph
      Returns:
      true if graph changed as a result of the call
      Throws:
      NullPointerException - if the specified vertices contains one or more null vertices, or if the specified vertex collection is null.
      See Also:

    • neighborListOf

      public static <V, E> List<V> neighborListOf(Graph<V,E> g, V vertex)
      Returns a list of vertices that are the neighbors of a specified vertex. If the graph is a multigraph vertices may appear more than once in the returned list.

      The method uses Graph.edgesOf(Object) to traverse the graph.

      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph to look for neighbors in
      vertex - the vertex to get the neighbors of
      Returns:
      a list of the vertices that are the neighbors of the specified vertex.

    • neighborSetOf

      public static <V, E> Set<V> neighborSetOf(Graph<V,E> g, V vertex)
      Returns a set of vertices that are neighbors of a specified vertex.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph to look for neighbors in
      vertex - the vertex to get the neighbors of
      Returns:
      a set of the vertices that are neighbors of the specified vertex

    • predecessorListOf

      public static <V, E> List<V> predecessorListOf(Graph<V,E> g, V vertex)
      Returns a list of vertices that are the direct predecessors of a specified vertex. If the graph is a multigraph, vertices may appear more than once in the returned list.

      The method uses Graph.incomingEdgesOf(Object) to traverse the graph.

      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph to look for predecessors in
      vertex - the vertex to get the predecessors of
      Returns:
      a list of the vertices that are the direct predecessors of the specified vertex.

    • successorListOf

      public static <V, E> List<V> successorListOf(Graph<V,E> g, V vertex)
      Returns a list of vertices that are the direct successors of a specified vertex. If the graph is a multigraph vertices may appear more than once in the returned list.

      The method uses Graph.outgoingEdgesOf(Object) to traverse the graph.

      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph to look for successors in
      vertex - the vertex to get the successors of
      Returns:
      a list of the vertices that are the direct successors of the specified vertex.

    • undirectedGraph

      public static <V, E> Graph<V,E> undirectedGraph(Graph<V,E> g)
      Returns an undirected view of the specified graph. If the specified graph is directed, returns an undirected view of it. If the specified graph is already undirected, just returns it.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - the graph for which an undirected view is to be returned
      Returns:
      an undirected view of the specified graph, if it is directed, or or the specified graph itself if it is already undirected.
      Throws:
      IllegalArgumentException - if the graph is neither directed nor undirected
      See Also:

    • testIncidence

      public static <V, E> boolean testIncidence(Graph<V,E> g, E e, V v)
      Tests whether an edge is incident to a vertex.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - graph containing e and v
      e - edge in g
      v - vertex in g
      Returns:
      true iff e is incident on v

    • getOppositeVertex

      public static <V, E> V getOppositeVertex(Graph<V,E> g, E e, V v)
      Gets the vertex opposite another vertex across an edge.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      g - graph containing e and v
      e - edge in g
      v - vertex in g
      Returns:
      vertex opposite to v across e

    • removeVertexAndPreserveConnectivity

      public static <V, E> boolean removeVertexAndPreserveConnectivity(Graph<V,E> graph, V vertex)
      Removes the given vertex from the given graph. If the vertex to be removed has one or more predecessors, the predecessors will be connected directly to the successors of the vertex to be removed.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - graph to be mutated
      vertex - vertex to be removed from this graph, if present
      Returns:
      true if the graph contained the specified vertex; false otherwise.

    • removeVerticesAndPreserveConnectivity

      public static <V, E> boolean removeVerticesAndPreserveConnectivity(Graph<V,E> graph, Predicate<V> predicate)
      Filters vertices from the given graph and subsequently removes them. If the vertex to be removed has one or more predecessors, the predecessors will be connected directly to the successors of the vertex to be removed.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - graph to be mutated
      predicate - a non-interfering stateless predicate to apply to each vertex to determine if it should be removed from the graph
      Returns:
      true if at least one vertex has been removed; false otherwise.

    • removeVertexAndPreserveConnectivity

      public static <V, E> boolean removeVertexAndPreserveConnectivity(Graph<V,E> graph, Iterable<V> vertices)
      Removes all the given vertices from the given graph. If the vertex to be removed has one or more predecessors, the predecessors will be connected directly to the successors of the vertex to be removed.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - to be mutated
      vertices - vertices to be removed from this graph, if present
      Returns:
      true if at least one vertex has been removed; false otherwise.

    • addOutgoingEdges

      public static <V, E> void addOutgoingEdges(Graph<V,E> graph, V source, Iterable<V> targets)
      Add edges from one source vertex to multiple target vertices. Whether duplicates are created depends on the underlying Graph implementation.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - graph to be mutated
      source - source vertex of the new edges
      targets - target vertices for the new edges

    • addIncomingEdges

      public static <V, E> void addIncomingEdges(Graph<V,E> graph, V target, Iterable<V> sources)
      Add edges from multiple source vertices to one target vertex. Whether duplicates are created depends on the underlying Graph implementation.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - graph to be mutated
      target - target vertex for the new edges
      sources - source vertices for the new edges

    • vertexHasSuccessors

      public static <V, E> boolean vertexHasSuccessors(Graph<V,E> graph, V vertex)
      Check if a vertex has any direct successors.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - the graph to look for successors
      vertex - the vertex to look for successors
      Returns:
      true if the vertex has any successors, false otherwise

    • vertexHasPredecessors

      public static <V, E> boolean vertexHasPredecessors(Graph<V,E> graph, V vertex)
      Check if a vertex has any direct predecessors.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - the graph to look for predecessors
      vertex - the vertex to look for predecessors
      Returns:
      true if the vertex has any predecessors, false otherwise

    • getVertexToIntegerMapping

      public static <V, E> VertexToIntegerMapping<V> getVertexToIntegerMapping(Graph<V,E> graph)
      Compute a new mapping from the vertices of a graph to the integer range $[0, n)$ where $n$ is the number of vertices in the graph.
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - the input graph
      Returns:
      the mapping as an object containing the vertexMap and the indexList
      Throws:
      NullPointerException - if graph is null
      See Also: