next | previous | forward | backward | up | top | index | toc | directory | Macaulay 2 web site

hyperGraph -- constructor for HyperGraph.

Synopsis

Description

The function hyperGraph is a constructor for HyperGraph. The user can input a hypergraph in a number of different ways, which we describe below. The information decribing the hypergraph is stored in a hash table. We require that there be no inclusion relations between the edges of a hypergraph; that is, that it be a clutter. The reason is that this package is designed for edge ideals, which would lose any information about edges that are supersets of other edges.

For the first possiblity, the user inputs a polynomial ring, which specifices the vertices of graph, and a list of the edges of the graph. The edges are represented as lists.
i1 : R = QQ[a..f]

o1 = R

o1 : PolynomialRing
i2 : E = {{a,b,c},{b,c,d},{c,d,e},{e,d,f}}

o2 = {{a, b, c}, {b, c, d}, {c, d, e}, {e, d, f}}

o2 : List
i3 : h = hyperGraph (R,E)

o3 = HyperGraph{edges => {{a, b, c}, {b, c, d}, {c, d, e}, {e, d, f}}}
                ring => R
                vertices => {a, b, c, d, e, f}

o3 : HyperGraph
Altenatively, if the polynomial ring has already been defined, it suffices to simply enter the list of the edges.
i4 : S = QQ[z_1..z_8]

o4 = S

o4 : PolynomialRing
i5 : E1 = {{z_1,z_2,z_3},{z_2,z_4,z_5,z_6},{z_4,z_7,z_8},{z_5,z_7,z_8}}

o5 = {{z , z , z }, {z , z , z , z }, {z , z , z }, {z , z , z }}
        1   2   3     2   4   5   6     4   7   8     5   7   8

o5 : List
i6 : E2 = {{z_2,z_3,z_4},{z_4,z_8},{z_7,z_6,z_8},{z_1,z_2}}

o6 = {{z , z , z }, {z , z }, {z , z , z }, {z , z }}
        2   3   4     4   8     7   6   8     1   2

o6 : List
i7 : h1 = hyperGraph E1

o7 = HyperGraph{edges => {{z , z , z }, {z , z , z , z }, {z , z , z }, {z , z , z }}}
                            1   2   3     2   4   5   6     4   7   8     5   7   8
                ring => S
                vertices => {z , z , z , z , z , z , z , z }
                              1   2   3   4   5   6   7   8

o7 : HyperGraph
i8 : h2 = hyperGraph E2

o8 = HyperGraph{edges => {{z , z }, {z , z , z }, {z , z }, {z , z , z }}}
                            1   2     2   3   4     4   8     6   7   8
                ring => S
                vertices => {z , z , z , z , z , z , z , z }
                              1   2   3   4   5   6   7   8

o8 : HyperGraph
The list of edges could also be entered as a list of square-free monomials.
i9 : T = QQ[w,x,y,z]

o9 = T

o9 : PolynomialRing
i10 : e = {w*x*y,w*x*z,w*y*z,x*y*z}

o10 = {w*x*y, w*x*z, w*y*z, x*y*z}

o10 : List
i11 : h = hyperGraph e

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

o11 : HyperGraph
Another option for defining an hypergraph is to use an ideal or monomialIdeal.
i12 : C = QQ[p_1..p_6]

o12 = C

o12 : PolynomialRing
i13 : i = monomialIdeal (p_1*p_2*p_3,p_3*p_4*p_5,p_3*p_6)

o13 = monomialIdeal (p p p , p p p , p p )
                      1 2 3   3 4 5   3 6

o13 : MonomialIdeal of C
i14 : hyperGraph i

o14 = HyperGraph{edges => {{p , p , p }, {p , p , p }, {p , p }}}
                             1   2   3     3   4   5     3   6
                 ring => C
                 vertices => {p , p , p , p , p , p }
                               1   2   3   4   5   6

o14 : HyperGraph
i15 : j = ideal (p_1*p_2,p_3*p_4*p_5,p_6)

o15 = ideal (p p , p p p , p )
              1 2   3 4 5   6

o15 : Ideal of C
i16 : hyperGraph j

o16 = HyperGraph{edges => {{p , p }, {p , p , p }, {p }}}
                             1   2     3   4   5     6
                 ring => C
                 vertices => {p , p , p , p , p , p }
                               1   2   3   4   5   6

o16 : HyperGraph
Since a graph is specific type of hypergraph, we can change the type of a graph to hypergraph.
i17 : D = QQ[r_1..r_5]

o17 = D

o17 : PolynomialRing
i18 : g = graph {r_1*r_2,r_2*r_4,r_3*r_5,r_5*r_4,r_1*r_5}

o18 = Graph{edges => {{r , r }, {r , r }, {r , r }, {r , r }, {r , r }}}
                        1   2     2   4     1   5     3   5     4   5
            ring => D
            vertices => {r , r , r , r , r }
                          1   2   3   4   5

o18 : Graph
i19 : h = hyperGraph g

o19 = HyperGraph{edges => {{r , r }, {r , r }, {r , r }, {r , r }, {r , r }}}
                             1   2     2   4     1   5     3   5     4   5
                 ring => D
                 vertices => {r , r , r , r , r }
                               1   2   3   4   5

o19 : HyperGraph
Some special care is needed it construct the empty hypergraph, that is, the hypergraph with no edges. In this case, the input cannot be a list (since the constructor does not know which ring to use). To define the empty graph, use a polynomial ring and (monomial) ideal.
i20 : E = QQ[m,n,o,p]

o20 = E

o20 : PolynomialRing
i21 : i = monomialIdeal(0_E)  -- the zero element of E (do not use 0)

o21 = 0

o21 : MonomialIdeal of E
i22 : hyperGraph i

o22 = HyperGraph{edges => {}             }
                 ring => E
                 vertices => {m, n, o, p}

o22 : HyperGraph
i23 : j = ideal (0_E)

o23 = 0

o23 : Ideal of E
i24 : hyperGraph j

o24 = HyperGraph{edges => {}             }
                 ring => E
                 vertices => {m, n, o, p}

o24 : HyperGraph

See also

Ways to use hyperGraph :