Package algs41

Class GraphGenerator

java.lang.Object
algs41.GraphGenerator
public class GraphGenerator extends Object

  • Constructor Details

  • Method Details

    • fromIn

      public static Graph fromIn(In in)
      Create a graph from input stream.

    • copy

      public static Graph copy(Graph G)

    • complete

      public static Graph complete(int V)

    • simple

      public static Graph simple(int V, int E)

    • simpleConnected

      public static Graph simpleConnected(int V, int E)

    • connected

      public static Graph connected(int V, int E)

    • random

      public static Graph random(int V, int E)

    • spanningTree

      public static Graph spanningTree(int V)

    • connected

      public static Graph connected(int V, int E, int c)

    • bipartite

      public static Graph bipartite(int V1, int V2, double p)
      Returns a random simple bipartite graph on V1 and V2 vertices, containing each possible edge with probability p.
      Parameters:
      V1 - the number of vertices in one partition
      V2 - the number of vertices in the other partition
      p - the probability that the graph contains an edge with one endpoint in either side
      Returns:
      a random simple bipartite graph on V1 and V2 vertices, containing each possible edge with probability p
      Throws:
      IllegalArgumentException - if probability is not between 0 and 1

    • path

      public static Graph path(int V)
      Returns a path graph on V vertices.
      Parameters:
      V - the number of vertices in the path
      Returns:
      a path graph on V vertices

    • binaryTree

      public static Graph binaryTree(int V)
      Returns a complete binary tree graph on V vertices.
      Parameters:
      V - the number of vertices in the binary tree
      Returns:
      a complete binary tree graph on V vertices

    • cycle

      public static Graph cycle(int V)
      Returns a cycle graph on V vertices.
      Parameters:
      V - the number of vertices in the cycle
      Returns:
      a cycle graph on V vertices

    • eulerianCycle

      public static Graph eulerianCycle(int V, int E)
      Returns an Eulerian cycle graph on V vertices.
      Parameters:
      V - the number of vertices in the cycle
      E - the number of edges in the cycle
      Returns:
      a graph that is an Eulerian cycle on V vertices and E edges
      Throws:
      IllegalArgumentException - if either V <= 0 or E <= 0

    • eulerianPath

      public static Graph eulerianPath(int V, int E)
      Returns an Eulerian path graph on V vertices.
      Parameters:
      V - the number of vertices in the path
      E - the number of edges in the path
      Returns:
      a graph that is an Eulerian path on V vertices and E edges
      Throws:
      IllegalArgumentException - if either V <= 0 or E < 0

    • wheel

      public static Graph wheel(int V)
      Returns a wheel graph on V vertices.
      Parameters:
      V - the number of vertices in the wheel
      Returns:
      a wheel graph on V vertices: a single vertex connected to every vertex in a cycle on V-1 vertices

    • star

      public static Graph star(int V)
      Returns a star graph on V vertices.
      Parameters:
      V - the number of vertices in the star
      Returns:
      a star graph on V vertices: a single vertex connected to every other vertex

    • regular

      public static Graph regular(int V, int k)
      Returns a uniformly random k-regular graph on V vertices (not necessarily simple). The graph is simple with probability only about e^(-k^2/4), which is tiny when k = 14.
      Parameters:
      V - the number of vertices in the graph
      k - degree of each vertex
      Returns:
      a uniformly random k-regular graph on V vertices.

    • tree

      public static Graph tree(int V)
      Returns a uniformly random tree on V vertices. This algorithm uses a Prufer sequence and takes time proportional to V log V.
      Parameters:
      V - the number of vertices in the tree
      Returns:
      a uniformly random tree on V vertices

    • print

      public static void print(Graph G, String filename)

    • main

      public static void main(String[] args)