Problem Detail: 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.
Asked By : Wouter Lievens
Answered By : Joachim Breitner
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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41320 Ask a Question Download Related Notes/Documents
