Macaulay2 » Documentation
Packages » EdgeIdeals :: Constructor Overview
next | previous | forward | backward | up | index | toc

Constructor Overview -- a summary of the many ways of making graphs and hypergraphs

The following is separated into four sections:

Basic Constructors

The main way of constructing Graph and HyperGraph objects is to use the graph and hyperGraph methods. These methods are overridden to provide many ways of specifying edges.

For the purposes of the EdgeIdeals package, every graph and hypergraph is associated to a ring whose variables correspond to the vertices of the (hyper)graph. Thus, the most explicit way to make a graph or hypergraph is by graph(PolynomialRing,List) and hyperGraph(PolynomialRing,List).The list parameter must contain edges which themselves are lists of variables in the ring.

i1 : R = QQ[x,y,z,w];
i2 : G = graph(R, {{x,y},{x,z},{y,z},{x,w}})

o2 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}
           "ring" => R
           "vertices" => {x, y, z, w}

o2 : Graph
i3 : H = hyperGraph(R, {{x,y,z},{x,w}})

o3 = HyperGraph{"edges" => {{x, y, z}, {x, w}}}
                "ring" => R
                "vertices" => {x, y, z, w}

o3 : HyperGraph

Probably the most convenient way of specifying edges is as a list of monomials. Using the graph(List) and hyperGraph(List) methods implicitly defines the ring of the (hyper)graph to be the ring containing the monomials in the List. The following example gives the same hypergraphs as before.

i4 : R = QQ[x,y,z,w];
i5 : G = graph {x*y, x*z, y*z, x*w}

o5 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}
           "ring" => R
           "vertices" => {x, y, z, w}

o5 : Graph
i6 : H = hyperGraph {x*y*z, x*w}

o6 = HyperGraph{"edges" => {{x, y, z}, {x, w}}}
                "ring" => R
                "vertices" => {x, y, z, w}

o6 : HyperGraph

The graph and hyperGraph constructors can also be used to make (hyper)graphs from square-free monomial ideals.The minimal generators of the ideal become the edges of the (hyper)graph. The ideal must be generated by quadratics if the graph constructor is used.

i7 : G = graph ideal(x*y, x*z, y*z, x*w)

o7 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}
           "ring" => R
           "vertices" => {x, y, z, w}

o7 : Graph

Converting Types

In this section, we will see how to convert between SimplicialComplexes and HyperGraphs, as well as between Graphs and HyperGraphs.

The methods simplicialComplexToHyperGraph and hyperGraphToSimplicialComplex accomplish the former conversion in the following way. In simplicialComplexToHyperGraph facets of the simplicial complex become the edges of the hypergraph, while in hyperGraphToSimplicialComplex the edges of the hypergraph become the facets of the new simplicial complex.

i8 : R = QQ[x,y,z,w];
i9 : H = hyperGraph {x*y*z,x*w};
i10 : D = hyperGraphToSimplicialComplex H

o10 = simplicialComplex | xw xyz |

o10 : SimplicialComplex
i11 : simplicialComplexToHyperGraph D

o11 = HyperGraph{"edges" => {{x, y, z}, {x, w}}}
                 "ring" => R
                 "vertices" => {x, y, z, w}

o11 : HyperGraph

The conversion of a graph into a hypergraph and vice versa use the constructors graph and hyperGraph. Any graph can be converted to a hyperGraph, but when a hyperGraph is converted into a graph, a check is run to ensure that the edges are all of size two. An error will be produced if this is not the case.

i12 : R = QQ[x,y,z,w];
i13 : G = graph {x*y, x*z, y*z, x*w};
i14 : H = hyperGraph G

o14 = HyperGraph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}
                 "ring" => R
                 "vertices" => {x, y, z, w}

o14 : HyperGraph
i15 : graph H

o15 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o15 : Graph

Since the Graph type is a subclass of HyperGraph, any method that takes a HyperGraph will also work on Graphs. So the conversion from graph to hypergraph is seldom needed; it is only needed when a method works differently on graphs than on hypergraphs (see complementGraph for an example).

On the other hand, the conversion from hypergraph to graph is very important as many methods are only defined on graphs. In the following example, we use the isChordal method which only applies to graphs and hence necessitates a conversion of types.

i16 : R = QQ[x,y,z,w];
i17 : D = simplicialComplex {x*y, x*z, y*z, x*w};
i18 : H = simplicialComplexToHyperGraph D

o18 = HyperGraph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}
                 "ring" => R
                 "vertices" => {x, y, z, w}

o18 : HyperGraph
i19 : G = graph H

o19 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o19 : Graph
i20 : isChordal G 

o20 = true

Special Graphs

In addition to the more general constructors, there a number of methods which produce certain special graphs.

Cycles can be constructed using cycle which, depending on the parameters, uses all or some of the variables in the ring to define a graph cycle.

i21 : R = QQ[x,y,z,w];
i22 : cycle R

o22 = Graph{"edges" => {{x, y}, {y, z}, {z, w}, {x, w}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o22 : Graph
i23 : cycle(R,3)

o23 = Graph{"edges" => {{x, y}, {y, z}, {x, z}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o23 : Graph
i24 : cycle {x,y,w} 

o24 = Graph{"edges" => {{x, y}, {y, w}, {x, w}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o24 : Graph

Anti-Cycles, the graph complements of cycles, can be constructed using antiCycle, which takes parameters similar to those of cycle.

i25 : R = QQ[x,y,z,w];
i26 : antiCycle R

o26 = Graph{"edges" => {{x, z}, {y, w}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o26 : Graph

Complete graphs can be constructed using completeGraph, which defines a graph with every possible edge between a given set a vertices.

i27 : R = QQ[x,y,z,w];
i28 : completeGraph R

o28 = Graph{"edges" => {{x, y}, {x, z}, {x, w}, {y, z}, {y, w}, {z, w}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o28 : Graph
i29 : completeGraph(R,3)

o29 = Graph{"edges" => {{x, y}, {x, z}, {y, z}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o29 : Graph
i30 : completeGraph {x,y,w} 

o30 = Graph{"edges" => {{x, y}, {x, w}, {y, w}}}
            "ring" => R
            "vertices" => {x, y, z, w}

o30 : Graph

Complete multipartite graphs can be constructed using completeMultiPartite, which defines a graph with every possible edge between certain partitions of the vertices. See completeMultiPartite for more details.

i31 : R = QQ[a,b,x,y];
i32 : completeMultiPartite(R,2,2)

o32 = Graph{"edges" => {{a, x}, {a, y}, {b, x}, {b, y}}}
            "ring" => R
            "vertices" => {a, b, x, y}

o32 : Graph

Random (Hyper)Graphs

Three methods are provided for the construction of random (hyper)graphs.

Each method allows you to specify the number of edges desired. For the random hypergraph methods, the sizes of the edges must also be specified.

i33 : R = QQ[x,y,z,u,v];
i34 : randomGraph(R,3)

o34 = Graph{"edges" => {{z, u}, {x, u}, {x, v}}}
            "ring" => R
            "vertices" => {x, y, z, u, v}

o34 : Graph
i35 : randomUniformHyperGraph(R,2,3)

o35 = HyperGraph{"edges" => {{y, u}, {x, u}, {x, y}}}
                 "ring" => R
                 "vertices" => {x, y, z, u, v}

o35 : HyperGraph
i36 : randomHyperGraph(R,{3,2,1})

o36 = HyperGraph{"edges" => {{x, y, z}, {z, u}, {v}}}
                 "ring" => R
                 "vertices" => {x, y, z, u, v}

o36 : HyperGraph

The randomHyperGraph method is not guaranteed to return a hypergraph; sometimes it returns null. Please see the documentation of this method for more details.

See also