Documentation

Overview

    Package product implements graph product functions.

    All the graph products in this package are graphs with order n₁n₂ where n₁ and n₂ are the orders of the input graphs. This is the order of the set of the Cartesian product of the two input graphs' nodes.

    The nodes of the product hold the original input graphs' nodes in the A and B fields in product.Nodes. This allows a mapping between the input graphs and their products.

    See https://en.wikipedia.org/wiki/Graph_product for more details about graph products.

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    func Cartesian

    func Cartesian(dst graph.Builder, a, b graph.Graph)

      Cartesian constructs the Cartesian product of a and b in dst.

      The Cartesian product of G₁ and G₂, G₁□G₂ has edges (u₁, u₂)~(v₁, v₂) when (u₁=v₁ and u₂~v₂) or (u₁~v₁ and u₂=v₂). The Cartesian product has size m₂n₁+m₁n₂ where m is the size of the input graphs and n is their order.

      func CoNormal

      func CoNormal(dst graph.Builder, a, b graph.Graph)

        CoNormal constructs the Co-normal product of a and b in dst.

        The Co-normal product of G₁ and G₂, G₁*G₂ (or G₁[G₂]) has edges (u₁, u₂)~(v₁, v₂) when u₁~v₁ or u₂~v₂. The Co-normal product is non-commutative.

        func Lexicographical

        func Lexicographical(dst graph.Builder, a, b graph.Graph)

          Lexicographical constructs the Lexicographical product of a and b in dst.

          The Lexicographical product of G₁ and G₂, G₁·G₂ has edges (u₁, u₂)~(v₁, v₂) when u₁~v₁ or (u₁=v₁ and u₂~v₂). The Lexicographical product has size m₂n₁+m₁n₂² where m is the size of the input graphs and n is their order.

          func Modular

          func Modular(dst graph.Builder, a, b graph.Graph)

            Modular constructs the Modular product of a and b in dst.

            The Modular product of G₁ and G₂, G₁◊G₂ has edges (u₁, u₂)~(v₁, v₂) when (u₁~v₁ and u₂~v₂) or (u₁≁v₁ and u₂≁v₂), and (u₁≠v₁ and u₂≠v₂).

            Modular is O(n^2) time where n is the order of the Cartesian product of a and b.

            Example (SubgraphIsomorphism)
            Output:
            
              Adenine   Guanine
             Atom  Pos Atom  Pos
                N    3    N    3
                N    7    N    7
                N   10    O   10
                C    6    C    6
                C    2    C    2
                C    8    C    8
                C    5    C    5
                N    9    N    9
                N    1    N    1
                C    4    C    4
            

            func ModularExt

            func ModularExt(dst graph.Builder, a, b graph.Graph, agree func(eA, eB graph.Edge) bool)

              ModularExt constructs the Modular product of a and b in dst with additional control over assessing edge agreement.

              In addition to the modular product conditions, agree(u₁v₁, u₂v₂) must return true when (u₁~v₁ and u₂~v₂) for an edge to be added between (u₁, u₂) and (v₁, v₂) in dst. If agree is nil, Modular is called.

              ModularExt is O(n^2) time where n is the order of the Cartesian product of a and b.

              Example (SubgraphIsomorphism)
              Output:
              
              Person — Relationship position:
               Cleopatra — A
               Mark Antony — B
               Octavia — C
              
               Cleopatra — A
               Mark Antony — B
               Fulvia — C
              

              func Strong

              func Strong(dst graph.Builder, a, b graph.Graph)

                Strong constructs the Strong product of a and b in dst.

                The Strong product of G₁ and G₂, G₁⊠G₂ has edges (u₁, u₂)~(v₁, v₂) when (u₁=v₁ and u₂~v₂) or (u₁~v₁ and u₂=v₂) or (u₁~v₁ and u₂~v₂). The Strong product has size n₁m₂+n₂m₁+2m₁m₂ where m is the size of the input graphs and n is their order.

                func Tensor

                func Tensor(dst graph.Builder, a, b graph.Graph)

                  Tensor constructs the Tensor product of a and b in dst.

                  The Tensor product of G₁ and G₂, G₁⨯G₂ has edges (u₁, u₂)~(v₁, v₂) when u₁~v₁ and u₂~v₂. The Tensor product has size 2m₁m₂ where m is the size of the input graphs.

                  Types

                  type Node

                  type Node struct {
                  	UID int64
                  
                  	// A and B hold the nodes from graph a and b in a
                  	// graph product constructed by a product function.
                  	A, B graph.Node
                  }

                    Node is a product of two graph nodes. All graph products return this type directly via relevant graph.Graph method call, or indirectly via calls to graph.Edge methods from returned edges.

                    func (Node) ID

                    func (n Node) ID() int64

                      ID implements the graph.Node interface.

                      Source Files