Hypergraphs

xholonWorkbook.xml

<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Thu Apr 05 2018 08:21:13 GMT-0400 (EDT)-->
<XholonWorkbook>

<Notes><![CDATA[
Xholon
------
Title: Hypergraphs
Description: 
Url: http://www.primordion.com/Xholon/gwt/
InternalName: 9e9aa6d9283efb51abb1983f52fa6d55
Keywords: 

My Notes
--------
Dec 3, 2017

- hyperedges may allow for multiple containment
  - see Venn diagram in source (1)
- 

TODO
----
- a workbook based on examles/diagrams in source (1)

Dec 11, 2017

- in my Cell Model, possibly there are 2 types of hyperedge:
 1. each container is a hyperedge
   - a container is a circle (closed curve) around the nodes that are its children
 2. each PO (small molecule) is a hyperedge
   - a PO is a circle around all the AO that reference it
 - this is a type of multiple containment

- is it true that in a bipartite structure, either set could function as a hyperedge?
  - the elements of each set could be thought of as connecting the elements of the other set?

April 2, 2018

To test Hello -> HPort -> World  - do the following in Dev Tools
-------------------------------
var hello = temp1;
hello.port(0).msg(101, "testing", hello);

References
----------
(1) https://en.wikipedia.org/wiki/Hypergraph
    In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. Formally, a hypergraph {\displaystyle H} H is a pair {\displaystyle H=(X,E)} H = (X,E) where {\displaystyle X} X is a set of elements called nodes or vertices, and {\displaystyle E} E is a set of non-empty subsets of {\displaystyle X} X called hyperedges or edges. Therefore, {\displaystyle E} E is a subset of {\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}} \mathcal{P}(X) \setminus\{\emptyset\}, where {\displaystyle {\mathcal {P}}(X)} {\mathcal {P}}(X) is the power set of {\displaystyle X} X.
    Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs.
    Bipartite graph model
    A hypergraph H may be represented by a bipartite graph BG as follows: the sets X and E are the partitions of BG, and (x1, e1) are connected with an edge if and only if vertex x1 is contained in edge e1 in H. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.
    Hypergraph drawing
    Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.

(2) https://en.wikipedia.org/wiki/Incidence_structure
(3) https://en.wikipedia.org/wiki/Hypergraph_grammar
(4) https://www.encyclopediaofmath.org/index.php/Hypergraph

(5) http://gdea.informatik.uni-koeln.de/585/1/hypergraph.ps
    Sander, G. (2003), "Layout of directed hypergraphs with orthogonal hyperedges", Proc. 11th International Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science, 2912, Springer-Verlag, pp. 381–386.

(6) http://jgaa.info/accepted/2006/EschbachGuentherBecker2006.10.2.pdf
    Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Orthogonal hypergraph drawing for improved visibility" (PDF), Journal of Graph Algorithms and Applications, 10 (2): 141–157, doi:10.7155/jgaa.00122.

(7) http://wiki.cytoscape.org/HyperEdgeAPI
    for supporting HyperEdges in Cytoscape
    A HyperEdge is an Edge that connects two or more Nodes. A HyperEdge consists of a set of Edges and a special Node referred to as a ConnectorNode. The ConnectorNode is a generated Node that serves as one endpoint for all Edges contained by a HyperEdge.
    The use case for HyperEdges is for representing structures like reactions and protein complexes. A simple example might be to represent a reaction what has a Substrate, Product and Mediator (e.g, Citrate, Isocitrate, and Aconitase). Such a reaction could be represented as a HyperEdge that contains three Edges that make up the Substrate, Product, and Mediator of the reaction. Here's a larger example of the Krebs Cycle that contains several reactions.
  ) http://wiki.cytoscape.org/EditingBiochemicalReactions

(8) http://graphml.graphdrawing.org/specification/element_hyperedge.xsd.htm

(9) http://www.math.nsc.ru/~ekonsta/Hypergraph%20theory.pdf
    CHEMICAL HYPERGRAPH THEORY, Elena Konstantinova
    Fig 19: (KSW thoughts)
      E1 is an edge that is shown encircling nodes 1,2,3,4
      each of E2,E3,E4 connect 2 nodes
      this seems to unify containment (place graph) and ports (link graph) within the concept of hypergraph/hyperedge
      both ports and containment are ways of enabling interaction
        ports can bind to create an edge or hyperedge
        a container can bind nodes that it contains
      multiple containment?

(10) https://ncatlab.org/nlab/show/hypergraph

(11) https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2673028/pdf/pcbi.1000385.pdf
    Hypergraphs and Cellular Networks, Steffen Klamt1, Utz-Uwe Haus2, Fabian Theis

(12) https://hal.archives-ouvertes.fr/file/index/docid/54578/filename/guillaume04ipl.pdf
    Bipartite Structure of all Complex Networks, Jean-Loup Guillaume and Matthieu Latapy

(13) BigraphER
    has a concept of multiple containment
    does the BigraphER literature mention hyperedges?
    does the overall Bigraph literature mention hyperedges?

(14) L.A. Paul, "A One Category Ontology"
    For the monocategorical theorist, spacetime consists of spatiotemporal relations, or properties,
    or of relational properties, suitably defined.
    The one category theorist holds that reality needs no such division between spatiotemporal regions and nonspatiotemporal qualities.
    These concrete particulars occupy spatiotemporal locations and display features we expect
    Of course, classical extensional mereology takes parts and wholes to be spatiotemporal parts and wholes,
    where parts are individuals that are—or are defined in terms of occupying—four-dimensional regions of spacetime. But
    we can apply the basic notion of parthood to other sorts of constituents,
    and define composition as a relation between these sorts of constituents,
    just as well as we can develop these notions so that they apply to spatiotemporal regions.
    the kind of parthood involved in qualitative parthood is different from the kind of parthood involved in spatiotemporal parthood
    My personal preference is for a contingent, pure mereological bundle theory where all things,
    including locations, are constructed from fusions of n-adic properties.

new April 1, 2018

(15) https://golem.ph.utexas.edu/category/2018/02/hypergraph_categories_of_cospa.html
    February 28, 2018
    Hypergraph Categories of Cospans
    Posted by John Baez
    guest post by Jonathan Lorand and Fabrizio Genovese

(16) https://web.eecs.umich.edu/~imarkov/pubs/book/part_survey.pdf
    Hypergraph Partitioning and Clustering, David A. Papa and Igor L. Markov, 2007?

(17) http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/Hypergraph.html
    A hypergraph, consisting of a set of vertices of type V and a set of hyperedges of type E which connect the vertices. This is the base interface for all JUNG graph types.

(18) https://www.bioconductor.org/packages/devel/bioc/vignettes/hyperdraw/inst/doc/hyperdraw.pdf
    R package
    How To use the hyperdraw package
    October 30, 2017
    1 Introduction
    The hyperdraw package provides a particular style of visualization for hypergraphs.
    A hypergraph differs from a normal graph in that each edge of a hypergraph may connect more than
    two nodes together (in a normal graph, an edge may only connect two nodes), which can present some
    difficulties for drawing the edges of a hypergraph.
    This package provides an algorithm for rendering hypergraphs.

(19) http://www.primordion.com/Xholon/gwt/XholonOpDSL.html?app=57e815d9de593c1a3d0fe155c3790067&src=gist&gui=none
    Operad examples
    especially example 3.1.3 from David Spivak's Pixel Array paper

]]></Notes> 

<_-.XholonClass>
  <PhysicalSystem/>
  <Hypergraph>
    <OperadExample/>
  </Hypergraph>
  
  <!-- node types that can be used as the content of a Hyperedge -->
  <One/>
  <Two/>
  <Three/>
  
  <!-- Hyperedge used as a Xholon port -->
  <HPort superClass="Hyperedge"/>
  <Hello/>
  <World/>
  
  <!-- terminology use in wikipedia Hypergraph article -->
  <Vertex/> <!-- Vertex is already defined in Xholon, as a StateMachineEntity, but it works OK in this workbook -->
  <Edge superClass="Hyperedge"/>
  <Vertices/>
  <Edges/>
  
  <!-- biochemical reaction
  Note: Reaction is already used in the Petri Net mechanism; I can't reuse it here
  -->
  <ReactionH superClass="Hyperedge"/>  <!-- a Hyperarc -->
  <SmallMolecule superClass="Attribute_double"/>  <!-- substrate or product -->
  
  <!-- Hypergraph with reverse port instead of port; Note: cannot use "trop" for this purpose -->
  <VertexT/>
  
  <!-- David Spivak, Operad, Pixel Array 3.1.3, see ref[19] -->
  <Pack/>
  <Cable superClass="Hyperedge"/>
  
</_-.XholonClass>

<xholonClassDetails>
  <Hello xhType="XhtypePureActiveObject">
    <port name="port" index="0" connector="../HPort"/>
  </Hello>
  <HPort>
    <port name="port" index="0" connector="../World"/>
  </HPort>
  <VertexT xhType="XhtypePureActiveObject"/>
  <Pack xhType="XhtypePureActiveObject"/>
  <Avatar><Color>yellow</Color></Avatar>
</xholonClassDetails>

<PhysicalSystem>
  
  <!-- April 2, 2018  testing new Hyperedge.java class -->
  
  <Hypergraph roleName="hg1">
    <Hyperedge/>
    <One multiplicity="2"/>
  </Hypergraph>
  
  <Hypergraph roleName="hg2">
    <Hello/>
    <!-- HPort is a directed graph, as defined in ref[11].
    "directed graphs are special cases of directed hypergraphs where both T and H contain
    exactly one node limiting their scope to 1:1 relationships. In
    contrast, directed hypergraphs can represent arbitrary n:m relationships."
    T tail, start nodes
    H head, end nodes
    -->
    <HPort/>
    <World/>
  </Hypergraph>
  
  <!--
  The structure is based on an example in the wikipedia Hypergraph article.
  H = (X,E)
  X = {v1,v2,v3,v4,v5,v6,v8}
  E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3},{v3,v5,v6},{v4}}

  In addition to the structure, each vertex needs access to the attribute contained within one or more edges.
  I should only specify the ports between vertices and edges once, but I should be able to specify these starting from either edge or vertex.
   - maybe use "trop" if I specify them from the Edge?
  In this example, the edges don't really need to know which vertices are connected to them.
   - This is a bipartite structure, similar to a Petri Net.
  But in some other cases, it could be the opposite; for example, if edges are active objects (AO) and vertices are passive objects (PO), or if one or the other is a Container.
  I'm trying several things simultaneously here.
  
  This is an undirected hypergraph, as defined in ref[11].
  This is similar to David Spivak's concept of packs and cables, where a cable is a hyperedge.
  -->
  <Hypergraph roleName="H">
    <Vertices roleName="X">
      <Vertex roleName="v1">
        <port name="hypre" index="0" connector="../../Edges/Edge[@roleName='e1']/Attribute"/>
      </Vertex>
      <Vertex roleName="v2">
        <port name="hypre" index="0" connector="../../Edges/Edge[@roleName='e1']/Attribute"/>
        <port name="hypre" index="1" connector="../../Edges/Edge[@roleName='e2']/Attribute"/>
      </Vertex>
      <Vertex roleName="v3">
        <port name="hypre" index="0" connector="../../Edges/Edge[@roleName='e1']/Attribute"/>
        <port name="hypre" index="1" connector="../../Edges/Edge[@roleName='e2']/Attribute"/>
        <port name="hypre" index="2" connector="../../Edges/Edge[@roleName='e3']/Attribute"/>
      </Vertex>
      <Vertex roleName="v4">
        <port name="hypre" index="0" connector="../../Edges/Edge[@roleName='e4']/Attribute"/>
      </Vertex>
      <Vertex roleName="v5">
        <port name="hypre" index="0" connector="../../Edges/Edge[@roleName='e3']/Attribute"/>
      </Vertex>
      <Vertex roleName="v6">
        <port name="hypre" index="0" connector="../../Edges/Edge[@roleName='e3']/Attribute"/>
      </Vertex>
      <Vertex roleName="v7"/>
    </Vertices>
    <Edges roleName="E">
      <!-- unable to set or inc value of an Attribute_int -->
      <Edge roleName="e1">{v1,v2,v3}<Attribute_double>0</Attribute_double></Edge> <!-- {v1,v2,v3} -->
      <Edge roleName="e2">{v2,v3}<Attribute_double>0</Attribute_double></Edge> <!-- {v2,v3} -->
      <Edge roleName="e3">{v3,v5,v6}<Attribute_double>0</Attribute_double></Edge> <!-- {v3,v5,v6} -->
      <Edge roleName="e4">{v4}<Attribute_double>0</Attribute_double></Edge> <!-- {v4} -->
    </Edges>
  </Hypergraph>
  
  <!--
  biochemical reaction, directed hypergraph
  see ref[11, p.3]
  reaction network:
   A>B
   A+B>C+D
   D>E
  the reactions are the hyperedges
  
  stoichiometric reactions, coefficients
  see stoichiometric matrix, where positive numbers signify a product and negative numbers signify a substrate
  
       R1  R2  R3
     ____________
   A|  -1  -1   0
   B|   1  -1   0
   C|   0   1   0
   D|   0   1  -1
   E|   0   0   1
  
  -->
  <Hypergraph roleName="biochem">
    <ReactionH roleName="R1" stoich="-1,1">
      <port name="sm" index="0" connector="../SmallMolecule[@roleName='A']"/>
      <port name="sm" index="1" connector="../SmallMolecule[@roleName='B']"/>
    </ReactionH>
    <ReactionH roleName="R2" stoich="-1,-1,1,1">
      <port name="sm" index="0" connector="../SmallMolecule[@roleName='A']"/>
      <port name="sm" index="1" connector="../SmallMolecule[@roleName='B']"/>
      <port name="sm" index="2" connector="../SmallMolecule[@roleName='C']"/>
      <port name="sm" index="3" connector="../SmallMolecule[@roleName='D']"/>
    </ReactionH>
    <ReactionH roleName="R3" stoich="-1,1">
      <port name="sm" index="0" connector="../SmallMolecule[@roleName='D']"/>
      <port name="sm" index="1" connector="../SmallMolecule[@roleName='E']"/>
    </ReactionH>
    
    <SmallMolecule roleName="A">1000</SmallMolecule>
    <SmallMolecule roleName="B">1000</SmallMolecule>
    <SmallMolecule roleName="C">1000</SmallMolecule>
    <SmallMolecule roleName="D">1000</SmallMolecule>
    <SmallMolecule roleName="E">1000</SmallMolecule>
    <Plot/>
  </Hypergraph>
  
  <!-- Hypergraph with reverse ports -->
  <Hypergraph roleName="reverse">
    <VertexT roleName="v1"/>
    <VertexT roleName="v2"/>
    <VertexT roleName="v3"/>
    <Edge roleName="e1"><Attribute_double>123.4</Attribute_double>
      <!--NO <port name="trop" index="0" connector="../VertexT[@roleName='v1']"/>-->
      <!--
      Hyperedge.java should automatically treat this as a reverse port, because the encapsulated node is a PO (Attribute_double).
      The result should be that v1:VertexT has a port hypre[0] that refs this Edge's Attribute_double. Same for v2 and v3.
      Edge's ports should be deleted or set to null.
      -->
      <port name="hypre" index="0" connector="../VertexT[@roleName='v1']"/>
      <port name="noindex" connector="../VertexT[@roleName='v2']"/>
      <port name="port" index="0" connector="../VertexT[@roleName='v3']"/>
    </Edge>
  </Hypergraph>
  
  <!-- tweentree == true -->
  <Hypergraph roleName="tweentree">
    <Hello/>
    <HPort tweentree="true"/>
    <World/>
  </Hypergraph>
  
  
  <!-- Operad Example -->
  <OperadExample roleName="operad">
    <Pack roleName="P′">
      <port name="x′" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='x']"/>
      <port name="v′" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='v']"/>
      <port name="z′" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='z']"/>
      <Pack roleName="P1">
        <port name="x1" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='x']"/>
        <port name="y1" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='y']"/>
      </Pack>
      <Pack roleName="P2">
        <port name="u2" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='u']"/>
        <port name="v2" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='v']"/>
        <port name="w2" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='w']"/>
        <port name="y2" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='y']"/>
      </Pack>
      <Pack roleName="P3">
        <port name="u3" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='u']"/>
        <port name="y3" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='y']"/>
        <port name="z3" connector="ancestor::Chameleon/PhysicalSystem/OperadExample/Pack/Cable[@roleName='z']"/>
      </Pack>
      <Cable roleName="u"/>
      <Cable roleName="v"/>
      <Cable roleName="w"/>
      <Cable roleName="x"/>
      <Cable roleName="y"/>
      <Cable roleName="z"/>
    </Pack>
  </OperadExample>
  
</PhysicalSystem>

<Hyperedgebehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
const SIG_TEST = -3898; // SIG_TEST = ISignal.SIGNAL_MIN_XHOLON_SERVICE + 101; // -3898
const SIG_CONTENT = -3897;
const SIG_RESPONSE = -3798;
var me, testing, beh = {
postConfigure: function() {
  testing = Math.floor(Math.random() * 10);
  me = this.cnode.parent();
  $wnd.xh.root().append(this.cnode.remove());
},
act: function() {
  me.println(this.toString());
  me.msg(SIG_TEST, "Hyper about graphs", me); // testing
  var rmsg = me.call(SIG_TEST, "calling all hyperedges", me);
  me.println(rmsg.data + " sig: " + rmsg.signal);
  rmsg = me.call(SIG_CONTENT, "<Two></Two>", me);
  me.println(rmsg.data + " sig: " + rmsg.signal);
  var one = me.next();
  if (one) {
    rmsg = me.call(SIG_CONTENT, one, me);
    me.println(rmsg.data + " sig: " + rmsg.signal);
  }
},
toString: function() {
  return "testing:" + testing;
}
}
//# sourceURL=Hyperedgebehavior.js
]]></Hyperedgebehavior>

<Worldbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
var me, beh = {
postConfigure: function() {
  me = this.cnode.parent();
  //$wnd.xh.root().append(this.cnode.remove()); // forwarder will fail if this behavior is moved
},
processReceivedMessage: function(msg) {
  me.println(me.name() + " received msg " + msg.signal + " from " + msg.sender.name());
}
}
//# sourceURL=Worldbehavior.js
]]></Worldbehavior>

<Vertexbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
var me, beh = {
postConfigure: function() {
  me = this.cnode.parent();
  $wnd.xh.root().append(this.cnode.remove());
},
act: function() {
  if (me.hypre && me.hypre.length) {
    for (var i = 0; i < me.hypre.length; i++) {
      me.hypre[i].inc(1);
    }
  }
}
}
//# sourceURL=Vertexbehavior.js
]]></Vertexbehavior>

<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>Hyperedge</title>
    <rect id="PhysicalSystem/Hypergraph/Hyperedge" fill="#98FB98" height="50" width="50" x="25" y="0"/>
    <g>
      <title>HPort</title>
      <rect id="PhysicalSystem/Hypergraph[2]/HPort" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
    </g>
  </g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>

</XholonWorkbook>