This is a continuation of the tutorial for the graph theory code which starts here. If you have not already installed and loaded the code from 'graph.spad' then you first need to follow the instructions on that page.
The previous page showed how to construct graphs, this page goes on to demonstrate ways to look at graphs. This includes:
- SVG graphical output
- Matrix representations:
- about whole graph:
- about specific nodes
- arrowName -- the name of arrow a->b
- inDegree -- the number of arrows leading in to node 'a' in graph 's'
- outDegree -- the number of arrows leading out of node 'a' in graph 's'
- nodeFromNode -- index of all nodes with a direct arrow leading in to node 'a' in graph 's'
- nodeToNode -- index of all nodes with a direct arrow leading out of node 'a' in graph 's'
- arrowsFromNode -- index of all arrows leading to a given node
- arrowsToNode -- index of all arrows leading from a given node
- nodeFromArrow -- index of all nodes with a direct arrow leading in to arrow 'a' in graph 's'
- nodeToArrow -- index of all nodes with a direct arrow leading out of arrow 'a' in graph 's'
- arrowsFromArrow -- index of all arrows leading to a given arrow
- arrowsToArrow -- index of all arrows leading from a given arrow
- min and max can be over whole graph or over a subset of nodes
Tutorial
First we construct a graph to work with :
(1) -> GS := DirectedGraph(String)
(1) DirectedGraph(String)
Type: Type
(2) -> hs1 := cycleOpen(["a","b","c"],"a")$GS
(2) "a,b,c|a1:a->b,a2:b->c"
Type: DirectedGraph(String)
(3) -> hs2 := cycleClosed(["1","2","3"],"b")$GS
(3) "1,2,3|b1:1->2,b2:2->3,b3:3->1"
Type: DirectedGraph(String)
(4) -> hs3 := closedTensor(hs1,hs2,concat)$GS
(4)
"a1,a2,a3,b1,b2,b3,c1,c2,c3|a1*b1:a1->b2,
a1*b2:a2->b3,a1*b3:a3->b1,a2*b1:b1->
c2,a2*b2:b2->c3,a2*b3:b3->c1"
Type: DirectedGraph(String)
(5) -> diagramSvg("testGraph3s1.svg",hs3,true)
Type: Void |
 |
Some functions use index numbers to specify vertices, so to make this clearer I have modified the above diagram by hand (using Inkscape) to add the green numbers (which are the index numbers of the objects) and the red numbers (which are the index numbers of the arrows). |
SVG graphical output
In line 5 we generated the graphical display of the graph. This is done by calling 'diagramSvg' like this:
diagramSvg("testGraph3s1.svg",hs3,true)
where
- "testGraph3s1.svg" is the filename that will be generated.
- hs3 is the graph that we wish to draw
- true is a boolean value which, when set to true will draw the arrow names in addition to the vertex names.
Matrix Representations
In addition to outputting to a diagram we can also output other information about the graph in matrix form:
Incidence Matrix
The incidence matrix represents the graph by a matrix of size |V| by |E| see this wiki page
where:
- V=number of vertices
- E=number of edges
- entry [vertex, arrow] = arrow endpoint
- data (simplest case: 1 - incident, 0 - not incident).
(6) -> incidenceMatrix(hs3)
+1 0 0 0 0 0 0 0 0+
|0 1 0 0 0 0 0 0 0|
(6) |0 0 1 0 0 0 0 0 0|
|0 0 0 1 0 0 0 0 0|
|0 0 0 0 1 0 0 0 0|
+0 0 0 0 0 1 0 0 0+
Type: Matrix(NonNegativeInteger) |
Adjacency Matrix
The adjacency matrix is an n by n matrix A, where n is the number of vertices in the graph. If there is an arrow from a vertex x to a vertex y, then the element ax,y is 1 (or in general the number of xy edges), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph. see this wiki page
(7) -> adjacencyMatrix(hs3)
+0 0 0 0 0 0 0 0 0+
|0 0 0 0 0 0 0 0 0|
|0 0 0 0 0 0 0 0 0|
|0 0 1 0 0 0 0 0 0|
(7) |1 0 0 0 0 0 0 0 0|
|0 1 0 0 0 0 0 0 0|
|0 0 0 0 0 1 0 0 0|
|0 0 0 1 0 0 0 0 0|
+0 0 0 0 1 0 0 0 0+
Type: Matrix(NonNegativeInteger) |
Laplacian Matrix
The laplacian matrix also known as "Kirchhoff matrix" or "Admittance matrix" where:
entry [i,j] =
- inDegree(vi) if i = j (number of incoming links)
- -1 if i not = j and vi is adjacent to vj
- 0 otherwise
Alternatively this is defined as D − A, where D is the diagonal degree matrix. It contains both adjacency information and degree information. There are other, similar matrices, that are also called "Laplacian matrices" of a graph. see this wiki page
(8) -> laplacianMatrix(hs3)
+ 0 0 0 0 0 0 0 0 0+
| 0 0 0 0 0 0 0 0 0|
| 0 0 0 0 0 0 0 0 0|
| 0 0 - 1 1 0 0 0 0 0|
(8) |- 1 0 0 0 1 0 0 0 0|
| 0 - 1 0 0 0 1 0 0 0|
| 0 0 0 0 0 - 1 1 0 0|
| 0 0 0 - 1 0 0 0 1 0|
+ 0 0 0 0 - 1 0 0 0 1+
Type: Matrix(Integer) |
Distance Matrix
Distance matrices are related to adjacency matrices, with the differences that:
- a) the latter only provides the information which vertices are connected but does not tell about costs or distances between the vertices and
- b) an entry of a distance matrix is smaller if two elements are closer, while "close" (connected) vertices yield larger entries in an adjacency matrix.
see this wiki page
(9) -> distanceMatrix(hs3)
+0 0 0 - 1 - 1 - 1 - 1 - 1 - 1+
|0 0 0 - 1 - 1 - 1 - 1 - 1 - 1|
|0 0 0 - 1 - 1 - 1 - 1 - 1 - 1|
|0 0 1 0 - 1 - 1 - 1 - 1 - 1|
(9) |1 0 0 - 1 0 - 1 - 1 - 1 - 1|
|0 1 0 - 1 - 1 0 - 1 - 1 - 1|
|0 2 0 - 1 - 1 1 0 - 1 - 1|
|0 0 2 1 - 1 - 1 - 1 0 - 1|
+2 0 0 - 1 1 - 1 - 1 - 1 0 +
Type: Matrix(Integer) |
Other Information about Graph
We now have a graph and we can check out various things about it. We can get information about the whole graph as follows. (10) tells us the graph is acyclic, that is it has no loops (which we can check by looking at the diagram above). (11) tells us that the graph is not functional, that is not every node has a single outgoing arrow. This is what we would expect since an acyclic graph cannot be functional.
(10) -> isAcyclic?(hs3)
(10) true
Type: Boolean
(11) -> isFunctional?(hs3)
(11) false
Type: Boolean |
About Specific Nodes
We can also get information about specific vertex and arrows. When we refer to a vertex we do so by its index number so, say we want to check if there is an arrow from "a" to "b", then "a" is index 1 and "b" is index 2. So we do this in (12) which confirms there is an arrow from "a" to "b". Note that, since this is a directed graph, the result in the other direction may be different as in (13).
isGreaterThan? in (14) tells us that we can get from 1 to 5 (not necessarily in one hop) but we cant get from 5 to 1.
isFixPoint? in (15) tells us if the given point loops back to itself in a single hop (in this case it does not).
(12) -> isDirectSuccessor?(hs3,1::NNI,5::NNI)
(12) true
Type: Boolean
(13) -> isDirectSuccessor?(hs3,5::NNI,1::NNI)
(13) false
Type: Boolean
(14) -> isGreaterThan?(hs3,1::NNI,5::NNI)
(14) true
Type: Boolean
(15) -> isFixPoint?(hs3,1::NNI)
(15) false
Type: Boolean
|
arrowName
Returns the name of arrow a->b. if it does not exist then return "?". If there are multiple arrows from a to b then return the name of the first.
(16) -> arrowName(hs3,1::NNI,5::NNI)
(16) "a1*b1"
Type: String |
inDegree
the number of arrows leading in to node 'a' in graph 's'
(17) -> inDegree(hs3,1::NNI)
(17) 0
Type: NonNegativeInteger |
outDegree
the number of arrows leading out of node 'a' in graph 's'
(18) -> outDegree(hs3,1::NNI)
(18) 1
Type: PositiveInteger |
nodeFromNode
index of all nodes with a direct arrow leading in to node 'a' in graph 's'
(19) -> nodeFromNode(hs3,1::NNI)
(19) []
Type: List(NonNegativeInteger) |
nodeToNode
index of all nodes with a direct arrow leading out of node 'a' in graph 's'
(20) -> nodeToNode(hs3,1::NNI)
(20) [5]
Type: List(NonNegativeInteger) |
arrowsFromNode
index of all arrows leading to a given node
(21) -> arrowsFromNode(hs3,1::NNI)
(21) []
Type: List(NonNegativeInteger) |
arrowsToNode
index of all arrows leading from a given node
(22) -> arrowsToNode(hs3,1::NNI)
(22) [1]
Type: List(NonNegativeInteger) |
nodeFromArrow
index of all nodes with a direct arrow leading in to arrow 'a' in graph 's'
(23) -> nodeFromArrow(hs3,1::NNI)
(23) [5]
Type: List(NonNegativeInteger) |
nodeToArrow
index of all nodes with a direct arrow leading out of arrow 'a' in graph 's'
(24) -> nodeToArrow(hs3,1::NNI)
(24) [1]
Type: List(NonNegativeInteger) |
arrowsFromArrow
index of all arrows leading to a given arrow
(25) -> arrowsFromArrow(hs3,1::NNI)
(25) []
Type: List(NonNegativeInteger) |
arrowsToArrow
index of all arrows leading from a given arrow
(26) -> arrowsToArrow(hs3,1::NNI)
(26) [5]
Type: List(NonNegativeInteger) |
Max and Min
- min returns the index of a vertex which has an arrow or a sequence of arrows from this node to every other node.
- max returns the index of a vertex which has an arrow or a sequence of arrows to this node from every other node.
If such vertices do not exist then the functions return 0 (zero). There are different forms of these functions to allow min and max to be over whole graph or over a subset of nodes. Here are some examples:
(27) -> max(hs1)
(27) 3
Type: PositiveInteger
(28) -> max(hs2)
(28) 0
Type: NonNegativeInteger
(29) -> min(hs1)
(29) 1
Type: PositiveInteger
(30) -> min(hs2)
(30) 0
Type: NonNegativeInteger
(31) -> max(hs1,[1::NNI,2::NNI])
(31) 2
Type: PositiveInteger
(32) -> min(hs1,[2::NNI,3::NNI])
(32) 2
Type: PositiveInteger |
That concludes our overview of ways to view and investigate graphs, click here to go to the next stage of the tutorial which is about ways to combine graphs such as sums and products.