# Terminology for a graph with ports on its nodes

A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain domain or application requires that edges don't merely connect vertices, but instead connect ports that exist on these vertices. In a directed graph, this would imply separation between input ports and output ports, wherein typically an edge starts at an output port and arrives at an input port.

Examples are easy to find: shader design tools, signal flow graphs in compiler theory, electronic schemas, high-level ETL scripting... all these tools require that vertices have named or distinct inputs and outputs.

Now for my question: is there any theory and nomenclature on these kinds of graphs, or is this considered to be an "implementation problem" of the engineering sciences? As you notice from my question, I can't quite pinpoint what this kind of thing is called ("A Graph With Node Ports"), and I'd love to see that answered.

• I am not sure whether there exists a specific terminology for what you are looking for, but to me it is also unclear what that is. Are you trying to capture a "labeling" of the ports, so that you can say that an edge connects "output port 1 of node A" with "input port 3 of node B" etc? If yes, then you could draw a graph with vertices representing ports (two types of vertices: "input ports" that have in-degree=1 and "output ports" with out-degree=1). What used to be a "vertex" is now a subgraph (on its input and output ports). Apr 13, 2015 at 6:52
• Yes, you can create an equivalent subgraph. Do subgraphs have more "serious" foundations in theory? Apr 13, 2015 at 6:54
• In the theory of graph rewriting they are called just like that: (multi-)graphs with ports. The ports are specific "labels" to distinguish the connections. Apr 13, 2015 at 8:03
• I didn't see any efforts to categorize and research this kind of graphs (where vertices can be graphs themselves), however I think they make sense - it looks like two-level algorithms would shine here. Anyway, it'd be good to see (in your question) some examples of problems you expect to solve on them. Welcome to the site! Apr 13, 2015 at 15:23