Viewing Graphs

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:

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
graph theory diagram 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

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:

(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] =

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:

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

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.


metadata block
see also:
Correspondence about this page

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2023 Martin John Baker - All rights reserved - privacy policy.