What is the name of a graph structure with 'ports'?

Question

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me about this structure is that it can be used to give edges between nodes an orientation within the local neighborhood, for example to say that some nodes are "above" other nodes or "to the right of" other nodes. In some cases (eg Euclidean lattice graphs) this extends to a global orientation, in others (eg toroidal or spherical graphs) it doesn't. I plan to use graphs with ports to describe data structure shapes (eg 1-D array, 2-D array, circular buffer) in the context of considering data structures as graphs.

If 'port' is not the most standard name, please enlighten me. I have seen this name used with this or a similar meaning used in some applications.

First, i will provide examples. At the bottom of this post, i will provide what i think is a formalization of the concept.

Examples

Example: 1-D lattice

For example, consider a lattice graph whose nodes are labeled 0, 1, 2, .., and with edges 0-1, 1-2, etc.

Now, call each connection of a node to an edge a 'port', and to each port assign a locally unique label, which i call a 'port label'. Formally, we can consider a port a pair (node, edge) such that 'edge' must be incident on 'node'.

For example, consider the above graph, where to port at the node 0 and the edge 0-1, we assign the label 'successor'; to the port at the node 1 and the edge 0-1, we assign the port label 'predecessor'; to the port at the node 1 and the edge 1-2, we assign the port label 'successor', etc:

0-successor---predecessor-1-successor---predecessor-2-successor-- ...

Note that for any given node and edge incident upon that node, there is a port, and that port has a port label assigned to it, meaning that there is a function nel that given a node and an edge, looks up the label of the port at the 'connection' between that node and that edge.

Note that for any given node and any given port label, there is at most one port of that port label (the property i called 'locally unique'), meaning that there is a function that given a node and a port_label, looks up the port of that label at that node, if any: nlp(node, port_label) = port_or_null, whose range is the set of ports unioned with NULL, such that if f(N, PT) = P, then P is of the form (N, __) where __ is some edge incident upon N.

Example: 2-D lattice

For another example, consider a 2-D lattice graph with nodes (0,0), (0,1), (0,2), ..., (1,0), (2,0), ... (1,1), ... etc, and edges such as (0,0)-(0,1), (1,0)-(1,1), and port labels 'up-one-from', 'down-one-from', 'left-one-from', and 'down-one-from':

(0,0)-right---left-(0,1)-right---left-(0,2)-right--- ...
  | down             | down             | down
  |                  |                  |
  | up               | up               |
(1,0)-right---left-(1,1)-right---left-(1,2)-right--- ...
  | down             | down             | down
 ...                ...                ...              

Example: 2-D 'spherical' graph with 6 nodes

For another example, consider a 'spherical' graph with six nodes (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), and nine edges (0,0)-(0,1), (0,1)-(0,2), (0-2)-(0,0), (1,0)-(1,1), (1,1)-(1,2), (1-2)-(0,0), (0,0)-(1,0), (0,1)-(1,1), (0,2)-(1,2), and port labels 'up-one-from', 'down-one-from', 'left-one-from', and 'down-one-from'.

         (wraparound)       (wraparound)       (wraparound)
              | up               | up               | up
(wrap)-left-(0,0)-right---left-(0,1)-right---left-(0,2)-right--(wrap)
              | down             | down             | down
              |                  |                  |
              | up               | up               |
(wrap)-left-(1,0)-right---left-(1,1)-right---left-(1,2)-right--(wrap)
              | down             | down             | down
              |                  |                  |
         (wraparound)       (wraparound)       (wraparound)

Example: irregular graph motivated by computer networking

website1         website2
   | downstream     | downstream
    \               /
     \             / 
      \ u1        / u2
          ISP
           | downstream
           | 
           | upstream
       LAN_router
      / d1        \ d2
     /             \
    / upstream      \ upstream
 desktop1          desktop2

Here, we have nodes labeled website1, website2, ISP, LAN_router, desktop1, desktop2; edges between both websites and the ISP, between ISP and the LAN_router, and between the LAN_router and both desktops. Port labels include downstream, upstream, d1, d2, u1, u2.

In this case we might want to group the port labels into 'types'; for example, we could define the types 'downstream-type' and 'upstream-type' and say that the type 'downstream-type' includes the labels 'downstream', 'd1', 'd2', 'u1', 'u2', and the type 'upstream-type' includes the label 'upstream'.

Formalization

Formally, i think the structure i have in mind is a graph with labeled nodes with the additional structure provided by one constant, one set and two functions:

• the constant 'null' (assumed to be distinct from every pair)
• the set port_label of port labels
• the function nel: (node, edge) $\to$ port_label, defined where 'edge' is incident upon 'node'
• the function nlp: (node, port_label) $\to$ ((node, edge) $\cup$ null)

with the constraints:

• if nlp(n1, t) = (n2, e), then n1 = n2 and e is incident upon n1
• if nel(n,e) = t, then nlp(n, t) = (n,e)
• if nlp(n, t) = (n, e), then nel(n,e) = t
• if nlp(n, t) = null, then there is no edge e such that nel(n,e) = t

and optionally, a function 'lt' that assigns to each port label a 'type'.

Answer 1

Amazingly enough, this type of graph is called a port graph. On Google Scholar, you'll even finding an existing research literature. Port graphs are commonly used in “graph rewriting systems” but have many applications, including modeling local causal interactions among groups of different kinds of things; see “bond graph”.

Port graphs are typically formalized something like this:

• A port graph is a tuple $(V, E)$ where:
• $V$ is a set of vertices (nodes);
• $E$ is a set of pairs (unordered two-element sets) $\{(v_1, p_1), (v_2, p_2)\}$ where $v_1,v_2 \in V$ and $p_1, p_2$ are “port labels”.

In other words, each edge connects nodes only via port labels associated with the nodes. The only difference from simplicial graphs is that in simplicial graphs, $E$ is defined as a set of pairs $\{v_1, v_2\}$, i.e. no ports.

There are many small variations in the exact definition. For example, $E$ could be a multiset, self-linking might be disallowed, edges might be directed, there might be a limited set of port labels, there might be rules restricting which port labels can connect to which, etc. All are called “port graphs”, so in formal writing you’ll need to spell out a precise definition of exactly which flavor you have in mind.