9
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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). $\endgroup$
    – megas
    Apr 13, 2015 at 6:52
  • $\begingroup$ Yes, you can create an equivalent subgraph. Do subgraphs have more "serious" foundations in theory? $\endgroup$ Apr 13, 2015 at 6:54
  • $\begingroup$ 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. $\endgroup$ Apr 13, 2015 at 8:03
  • $\begingroup$ 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! $\endgroup$
    – HEKTO
    Apr 13, 2015 at 15:23

1 Answer 1

6
$\begingroup$

I was wondering the same thing. It seems that there are a number of publications revolving around this idea, most of them at the TERMGRAPH workshop. They are usually called “port graphs” there.

Tracing the related work of a random sample of papers yields that the following might be the prime paper that introduces this formalism:

Andrei, O. and H. Kirchner, A Rewriting Calculus for Multigraphs with Ports., in: Proceedings of RULE’07, Electronic Notes in Theoretical Computer Science 219, 2008, pp. 67–82.

One that I find particularly interesting is

Sandra Alves, Maribel Fernández, and Ian Mackie. A new graphical calculus of proofs. In TERMGRAPH, volume 48 of EPTCS, pages 69–84, 2011

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.