Package org.graph4j

Class GraphUtils

java.lang.Object
org.graph4j.GraphUtils
public class GraphUtils extends Object
Static utility methods that operate on or return graphs, either directed or undirected.
Author:
Cristian Frăsinaru

  • Constructor Details

    • GraphUtils

      public GraphUtils()

  • Method Details

    • createSupportGraph

      public static Graph createSupportGraph(Graph graph)
      Convenience method for obtaining the support graph of a digraph, multigraph or pseudograph. If the input graph is a simple, undirected graph, it returns the graph itself.
      Parameters:
      graph - a reference to a digraph, multigraph or pseudograph.
      Returns:
      the support graph.

    • disjointUnion

      public static Graph disjointUnion(Graph... graphs)
      Performs the disjoint union operation. The disjoint union of the specified graphs will have all their vertices and edges. The vertex sets of the graphs must be pairwise disjoint.
      Parameters:
      graphs - the graphs to perform disjoint union on.
      Returns:
      a new graph, representing the disjoint union of the graphs.

    • union

      public static Graph union(Graph... graphs)
      Performs the union of the specified graph. The union will have all the distinct vertices and the edges of the given graphs. Vertices with the same number are contracted. If the graphs have pairwise distinct vertex sets, union is the same as disjoint union.
      Parameters:
      graphs - the graphs to perform union on.
      Returns:
      a new graph, representing the union of the graphs.

    • join

      public static Graph join(Graph... graphs)
      Performs the join operation on the specified graphs. The join is the union of the graphs, together with all the edges joining vertices from each graph to each graph. The vertex sets of the graphs must be pairwise disjoint.
      Parameters:
      graphs - the first graphs to perform join on.
      Returns:
      a new graph, representing the join of the graphs.

    • toDigraph

      public static Digraph toDigraph(Graph graph)
      The corresponding directed graph of an undirected graph G has all the vertices of G and a pair of symmetrical arcs for each edge of G. If the input graph is a Multigraph it returns a DirectedMultigraph. If the input graph is a Pseudograph it returns a DirectedPseudograph.
      Parameters:
      graph - the input graph.
      Returns:
      a new digraph corresponding to the input graph.

    • toDirectedMultigraph

      public static DirectedMultigraph toDirectedMultigraph(Multigraph graph)

    • toDirectedPseudograph

      public static DirectedPseudograph toDirectedPseudograph(Pseudograph graph)

    • toNetwork

      public static Network toNetwork(Graph graph)
      Creates a network having the same vertices and edges as the specified graph.
      Parameters:
      graph - the input graph.
      Returns:
      a new network corresponding to the input digraph.

    • toNetwork

      public static Network toNetwork(Graph graph, int source, int sink)
      Creates a network having the same vertices and edges as the specified graph. The weights of the graphs become capacities in the resulting network.
      Parameters:
      graph - the input graph.
      source - the source vertex of the network.
      sink - the sink vertex of the network.
      Returns:
      a new network corresponding to the input digraph.

    • transpose

      public static Digraph transpose(Digraph digraph)
      Creates the transpose of a directed graph. The transpose of a directed graph G is another directed graph having the same set of vertices with all of the edges reversed compared to the orientation of the corresponding edges in G.
      Parameters:
      digraph - the input digraph.
      Returns:
      the transpose of the input digraph.

    • createLineGraph

      public static Graph<Edge,Object> createLineGraph(Graph graph)
      Creates the line graph of an undirected graph.
      Parameters:
      graph - the input graph.
      Returns:
      the line graph of the input graph.

    • createLineGraph

      public static Digraph<Edge,Object> createLineGraph(Digraph digraph)
      Creates the line graph of a directed graph.
      Parameters:
      digraph - the input digraph.
      Returns:
      the line graph of the input digraph.

    • createAcyclicOrientation

      public static Digraph createAcyclicOrientation(Graph graph)
      Creates the acyclic orientation of an undirected graph. An acyclic orientation of an undirected graph means assigning a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph (DAG). Every undirected graph has an acyclic orientation.
      Parameters:
      graph - an undirected graph.
      Returns:
      a directed acyclic graph, corresponding to the input graph.
      See Also:

    • computeEdgeConnectivity

      public static int computeEdgeConnectivity(Graph graph)
      Computes the edge connectivity number, that is the minimum size of a set of edges whose removal disconnects the graph. An upper bound of this number is the maximum degree of vertex.
      Parameters:
      graph - the input graph.
      Returns:
      the edge connectivity number.
      See Also:

    • computeVertexConnectivity

      public static int computeVertexConnectivity(Graph graph)
      Computes the vertex connectivity number, that is the minimum size of a set of vertices whose removal disconnects the graph. If the graph is complete, it returns n-1, where n is the number of vertices in the graph.
      Parameters:
      graph - the input graph.
      Returns:
      the vertex connectivity number.
      See Also:

    • rotate

      public static Graph rotate(Graph graph, int distance)
      Creates a new graph by rotating the vertex numbers in the input graph by a specified distance, while preserving the edges. The rotated graph is isomorphic with the original one.
      Parameters:
      graph - the input graph to be rotated.
      distance - the distance to rotate with.
      Returns:
      a new graph created by rotating the input graph.

    • shuffle

      public static Graph shuffle(Graph graph)
      Creates a new graph by shuffling the vertex numbers in the input graph, while preserving the edges. The shuffled graph is isomorphic with the original one.
      Parameters:
      graph - the input graph to be shuffled.
      Returns:
      a new graph created by shuffling the input graph.

    • mapVertexNumbers

      public static Graph mapVertexNumbers(Graph graph, int[] vertices)
      Creates a new graph by mapping the vertex numbers in the input graph to the specified values, while preserving the edges. The new graph is isomorphic with the original one.
      Parameters:
      graph - the input graph.
      vertices - a mapping between the indices of the graph and their new numbers.
      Returns:
      a new graph created by mapping the vertex numbers.

    • isPartitionValid

      public static boolean isPartitionValid(Graph graph, List<? extends VertexCollection> subsets)
      Checks if a vertex partition is valid, meaning the subsets are disjoint and cover all vertices in the graph.
      Parameters:
      graph - the graph whose vertices are partitioned.
      subsets - the subsets of the partition.
      Returns:
      true if the partition is valid, false otherwise.

    • createIntersectionGraph

      public static Graph createIntersectionGraph(List<Graph> graphs, boolean vertexLabeled)
      Creates the intersection graph of the vertex sets of the specified graphs.An intersection graph is a graph where each vertex corresponds to a set, and there is an edge between two vertices if and only if the corresponding sets intersect.
      Parameters:
      graphs - the input graphs for the operation.
      vertexLabeled - if true each vertex of the intersection graph is labeled with the corresponding input graph.
      Returns:
      the intersection graph of the vertex sets of the specified graphs.

    • getVertices

      public static VertexSet getVertices(Graph graph, Collection<Edge> edges)
      Determines the set of distinct vertices belonging to a collection of edges.
      Parameters:
      graph - the input graph.
      edges - a collection of edges.
      Returns:
      the vertices in the specified collection of edges.

    • computeWeight

      public static double computeWeight(Graph graph, Collection<Edge> edges)
      Computes the sum of the weights of the edges in a specified collection
      Parameters:
      graph - the input graph.
      edges - a collection of edges.
      Returns:
      the sum of the weights of the edges.