Class FoldingTransformer<V,E>

java.lang.Object
edu.uci.ics.jung.algorithms.transformation.FoldingTransformer<V,E>

public class FoldingTransformer<V,E> extends Object
Methods for creating a "folded" graph based on a k-partite graph or a hypergraph.

A "folded" graph is derived from a k-partite graph by identifying a partition of vertices which will become the vertices of the new graph, copying these vertices into the new graph, and then connecting those vertices whose original analogues were connected indirectly through elements of other partitions.

A "folded" graph is derived from a hypergraph by creating vertices based on either the vertices or the hyperedges of the original graph, and connecting vertices in the new graph if their corresponding vertices/hyperedges share a connection with a common hyperedge/vertex.

  • Constructor Summary

    Constructors
    Constructor
    Description
     
  • Method Summary

    Modifier and Type
    Method
    Description
    static <V, E> Graph<V,E>
    foldHypergraphEdges(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<V,E>> graph_factory, com.google.common.base.Supplier<E> edge_factory)
    Creates a Graph which is an edge-folded version of h, where hyperedges are replaced by k-cliques in the output graph.
    static <V, E> Graph<V,Collection<E>>
    foldHypergraphEdges(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<V,Collection<E>>> graph_factory)
    Creates a Graph which is an edge-folded version of h, where hyperedges are replaced by k-cliques in the output graph.
    static <V, E, F> Graph<E,F>
    foldHypergraphVertices(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<E,F>> graph_factory, com.google.common.base.Supplier<F> edge_factory)
    Creates a Graph which is a vertex-folded version of h, whose vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges in the input.
    foldHypergraphVertices(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<E,Collection<V>>> graph_factory)
    Creates a Graph which is a vertex-folded version of h, whose vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges in the input.
    static <V, E> Graph<V,E>
    foldKPartiteGraph(KPartiteGraph<V,E> g, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V,E>> graph_factory, com.google.common.base.Supplier<E> edge_factory)
    Converts g into a unipartite graph whose vertex set is the vertices of g's partition p.
    static <V, E> Graph<V,Collection<V>>
    foldKPartiteGraph(KPartiteGraph<V,E> g, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V,Collection<V>>> graph_factory)
    Converts g into a unipartite graph whose vertices are the vertices of g's partition p, and whose edges consist of collections of the intermediate vertices from other partitions.
    private static <S, T> void
    populateTarget(Graph<S,Collection<T>> target, T e, ArrayList<S> incident)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • FoldingTransformer

      public FoldingTransformer()
  • Method Details

    • foldKPartiteGraph

      public static <V, E> Graph<V,E> foldKPartiteGraph(KPartiteGraph<V,E> g, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V,E>> graph_factory, com.google.common.base.Supplier<E> edge_factory)
      Converts g into a unipartite graph whose vertex set is the vertices of g's partition p. For vertices a and b in this partition, the resultant graph will include the edge (a,b) if the original graph contains edges (a,c) and (c,b) for at least one vertex c.

      The vertices of the new graph are the same as the vertices of the appropriate partition in the old graph; the edges in the new graph are created by the input edge Factory.

      If there is more than 1 such vertex c for a given pair (a,b), the type of the output graph will determine whether it will contain parallel edges or not.

      This function will not create self-loops.

      Type Parameters:
      V - vertex type
      E - input edge type
      Parameters:
      g - input k-partite graph
      p - predicate specifying vertex partition
      graph_factory - Supplier used to create the output graph
      edge_factory - Supplier used to create the edges in the new graph
      Returns:
      a copy of the input graph folded with respect to the input partition
    • foldKPartiteGraph

      public static <V, E> Graph<V,Collection<V>> foldKPartiteGraph(KPartiteGraph<V,E> g, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V,Collection<V>>> graph_factory)
      Converts g into a unipartite graph whose vertices are the vertices of g's partition p, and whose edges consist of collections of the intermediate vertices from other partitions. For vertices a and b in this partition, the resultant graph will include the edge (a,b) if the original graph contains edges (a,c) and (c,b) for at least one vertex c.

      The vertices of the new graph are the same as the vertices of the appropriate partition in the old graph; the edges in the new graph are collections of the intermediate vertices c.

      This function will not create self-loops.

      Type Parameters:
      V - vertex type
      E - input edge type
      Parameters:
      g - input k-partite graph
      p - predicate specifying vertex partition
      graph_factory - Supplier used to create the output graph
      Returns:
      the result of folding g into unipartite graph whose vertices are those of the p partition of g
    • foldHypergraphEdges

      public static <V, E> Graph<V,Collection<E>> foldHypergraphEdges(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<V,Collection<E>>> graph_factory)
      Creates a Graph which is an edge-folded version of h, where hyperedges are replaced by k-cliques in the output graph.

      The vertices of the new graph are the same objects as the vertices of h, and a is connected to b in the new graph if the corresponding vertices in h are connected by a hyperedge. Thus, each hyperedge with k vertices in h induces a k-clique in the new graph.

      The edges of the new graph consist of collections of each hyperedge that connected the corresponding vertex pair in the original graph.

      Type Parameters:
      V - vertex type
      E - input edge type
      Parameters:
      h - hypergraph to be folded
      graph_factory - Supplier used to generate the output graph
      Returns:
      a copy of the input graph where hyperedges are replaced by cliques
    • foldHypergraphEdges

      public static <V, E> Graph<V,E> foldHypergraphEdges(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<V,E>> graph_factory, com.google.common.base.Supplier<E> edge_factory)
      Creates a Graph which is an edge-folded version of h, where hyperedges are replaced by k-cliques in the output graph.

      The vertices of the new graph are the same objects as the vertices of h, and a is connected to b in the new graph if the corresponding vertices in h are connected by a hyperedge. Thus, each hyperedge with k vertices in h induces a k-clique in the new graph.

      The edges of the new graph are generated by the specified edge Supplier.

      Type Parameters:
      V - vertex type
      E - input edge type
      Parameters:
      h - hypergraph to be folded
      graph_factory - Supplier used to generate the output graph
      edge_factory - Supplier used to create the new edges
      Returns:
      a copy of the input graph where hyperedges are replaced by cliques
    • foldHypergraphVertices

      public static <V, E, F> Graph<E,F> foldHypergraphVertices(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<E,F>> graph_factory, com.google.common.base.Supplier<F> edge_factory)
      Creates a Graph which is a vertex-folded version of h, whose vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges in the input.

      The vertices of the new graph are the same objects as the hyperedges of h, and a is connected to b in the new graph if the corresponding edges in h have a vertex in common. Thus, each vertex incident to k edges in h induces a k-clique in the new graph.

      The edges of the new graph are created by the specified Supplier.

      Type Parameters:
      V - vertex type
      E - input edge type
      F - output edge type
      Parameters:
      h - hypergraph to be folded
      graph_factory - Supplier used to generate the output graph
      edge_factory - Supplier used to generate the output edges
      Returns:
      a transformation of the input graph whose vertices correspond to the input's hyperedges and edges are induced by hyperedges sharing vertices in the input
    • foldHypergraphVertices

      public Graph<E,Collection<V>> foldHypergraphVertices(Hypergraph<V,E> h, com.google.common.base.Supplier<Graph<E,Collection<V>>> graph_factory)
      Creates a Graph which is a vertex-folded version of h, whose vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges in the input.

      The vertices of the new graph are the same objects as the hyperedges of h, and a is connected to b in the new graph if the corresponding edges in h have a vertex in common. Thus, each vertex incident to k edges in h induces a k-clique in the new graph.

      The edges of the new graph consist of collections of each vertex incident to the corresponding hyperedge pair in the original graph.

      Parameters:
      h - hypergraph to be folded
      graph_factory - Supplier used to generate the output graph
      Returns:
      a transformation of the input graph whose vertices correspond to the input's hyperedges and edges are induced by hyperedges sharing vertices in the input
    • populateTarget

      private static <S, T> void populateTarget(Graph<S,Collection<T>> target, T e, ArrayList<S> incident)
      Parameters:
      target -
      e -
      incident -