This software can model second order graphs, that is, graphs whose vertices are also graphs. It can also use graphs to model various types of mappings. This page shows the approach I am taking to these things.
Second order graphs seems to be related to 2-category structures (see wiki page) and there may be other equivalent structures:
- As a graph whose elements are themselves graphs, where the outer graph can see inside (has arrows between the nodes of) the inner graph.
- As a set of graphs with mappings between them, where the whole system is treated as a graph.
- As a graph which also has arrows between the arrows.
To show how I have implemented this I have written the following example. We construct 4 graphs of type INNER := DirectedGraph(String). Then we construct an OUTER graph over these INNER graphs.
(1) -> INNER := DirectedGraph(String)
(1) DirectedGraph(String)
Type: Type
(2) -> P := directedGraph(["a","b","c","d"])$INNER
(2) "a","b","c","d"
Type: DirectedGraph(String)
(3) -> addArrow!(P,"alpha",1,2)
(3) "a","b","c","d"|"alpha":"a"->"b"
Type: DirectedGraph(String)
(4) -> addArrow!(P,"beta",1,3)
(4) "a","b","c","d"|"alpha":"a"->"b","beta":"a"->"c"
Type: DirectedGraph(String)
(5) -> addArrow!(P,"gamma",2,4)
(5) "a","b","c","d"|"alpha":"a"->"b","beta":"a"->"c",
"gamma":"b"->"d"
Type: DirectedGraph(String)
(6) -> addArrow!(P,"delta",3,4)
(6)
"a","b","c","d"|"alpha":"a"->"b","beta":"a"->"c",
"gamma":"b"->"d","delta":"c"->"d"
Type: DirectedGraph(String)
(7) -> Q := directedGraph(["x","y"])$INNER
(7) "x","y"
Type: DirectedGraph(String)
(8) -> addArrow!(Q,"alpha",1,2)
(8) "x","y"|"alpha":"x"->"y"
Type: DirectedGraph(String)
(9) -> R := directedGraph(["1","2"])$INNER
(9) "1","2"
Type: DirectedGraph(String)
(10) -> addArrow!(R,"alpha",1,2)
(10) "1","2"|"alpha":"1"->"2"
Type: DirectedGraph(String)
(11) -> S := directedGraph(["t"])$INNER
(11) "t"
Type: DirectedGraph(String)
(12) -> OUTER := DirectedGraph(INNER)
(12) DirectedGraph(DirectedGraph(String))
Type: Type
(13) -> ML := directedGraph([P,Q,R,S])$OUTER
(13) 1,2,3,4
Type: DirectedGraph(DirectedGraph(String))
(14) -> addArrow!(ML,"alpha",1,2)
(14) 1,2,3,4|"alpha":1->2
Type: DirectedGraph(DirectedGraph(String))
(15) -> addArrow!(ML,"beta",1,3)
(15) 1,2,3,4|"alpha":1->2,"beta":1->3
Type: DirectedGraph(DirectedGraph(String))
(16) -> addArrow!(ML,"gamma",2,4)
(16) 1,2,3,4|"alpha":1->2,"beta":1->3,"gamma":2->4
Type: DirectedGraph(DirectedGraph(String))
(17) -> addArrow!(ML,"delta",3,4)
(17) 1,2,3,4|"alpha":1->2,"beta":1->3,"gamma":2->4,"delta":3->4
Type: DirectedGraph(DirectedGraph(String))
(18) -> diagramSvg("testGraph/testGraphml1.svg",ML,false)
Type: Void |
| As you can see this OUTER graph is hard to display in text format on the command line. However its easier to see what's going on when we look at the diagram it produces here: |  |
So far the above diagram does not show how individual vertices in one inner graph map to the individual vertices in another inner graph. To do this we need to define these maps, this is done by using a 'List NNI' where the 'nth entry in the list represents the 'from' index and its value represents the 'to' index. We put this map as the last entry in the 'addArrow!' calls below. To display this information we use a variant of 'diagramSvg' called 'deepDiagramSvg' which looks inside the arrows to see how individual inner vertices map as follows:
(19) -> ML2 := directedGraph([P,Q,R,S])$OUTER
(19) 1,2,3,4
Type: DirectedGraph(DirectedGraph(String))
(20) -> addArrow!(ML2,"alpha",1,2,[1,2,1,2])
(20) 1,2,3,4|"alpha":1->2
Type: DirectedGraph(DirectedGraph(String))
(21) -> addArrow!(ML2,"beta",1,3,[1,2,1,2])
(21) 1,2,3,4|"alpha":1->2,"beta":1->3
Type: DirectedGraph(DirectedGraph(String))
(22) -> addArrow!(ML2,"gamma",2,4,[1,1])
(22) 1,2,3,4|"alpha":1->2,"beta":1->3,"gamma":2->4
Type: DirectedGraph(DirectedGraph(String))
(23) -> addArrow!(ML2,"delta",3,4,[1,1])
(23) 1,2,3,4|"alpha":1->2,"beta":1->3,"gamma":2->4,"delta":3->4
Type: DirectedGraph(DirectedGraph(String))
(24) -> deepDiagramSvg("testGraph/testGraphml2.svg",ML2,false)
Type: Void |
| So the arrows now know about both the inner and the outer graphs. The diagram can now 'see' inside the inner graphs. |  |
We can now try the 'flatten' function. This takes a second order graph, such as the one that we have already constructed and flatten it into a first order graph.
(25) -> ML3 := flatten(ML2)$INNER
(25)
"a","b","c","d","x","y","1","2","t"|"alpha":"a"->"b",
"beta":"a"->"c","gamma":"b"->"d","delta":"c"->"d",
"alpha":"x"->"y","alpha":"1"->"2","alpha":"a"->"x",
"alpha":"b"->"y","alpha":"c"->"x","alpha":"d"->"y",
"beta":"a"->"1","beta":"b"->"2","beta":"c"->"1",
"beta":"d"->"2","gamma":"x"->"t","gamma":"y"->"t",
"delta":"1"->"t","delta":"2"->"t"
Type: DirectedGraph(String)
(26) -> diagramSvg("testGraph/testGraphml3.svg",ML3,false)
Type: Void |
| The first order graph that we have constructed includes the arrows from both the inner and the outer graphs: |  |
As it stands there are a lot of limitations with the above code (it is not completely general).
- It only works if the outer graph is of type 'DirectedGraph(DirectedGraph(String))' it would be better if it could be more general such as any implementation of 'FiniteGraph(FiniteGraph(SetCategory))'.
- The code also makes certain assumptions about the coordinate ranges of the inner graphs and if this is not valid then the inner diagrams may overlap the circles.
Other Design Issues
Other design issues are discussed here.