Architecture - Top Level Design of Code

We need definitions for other graph-related terminology such as trees and forest and so on. There tend to be widely accepted definitions for undirected graphs but there seem to be more options and variations for these definitions as applied to directed graphs.

I have therefore drawn up two sets of definitions in order to make these issues clearer:

Definitions for undirected graph

Definitions for directed graph

Design Issues

So far, only finite graphs are implemented, these all extend the category FiniteGraph (FGRPH). I would like this to extend a more general Graph (GRPH) category which would include functions such as 'neighbours' and 'distance' which are common to both finite and infinite graphs. However, at this stage, I don't know how infinite graphs would be represented (presumably some inductively defined data structure). Therefore I don't know how vertices of the graph would be referred too, in the most general case (can they still be indexed), so I don't know if the same signature can be used for 'distance' in the finite and infinite cases. I have therefore left this Graph (GRPH) category as a possible future enhancement.

Probably the most efficient general representation coding of a graph is as a set of external 'objects' (graph is defined over a set) together with pairs of indices to represent the arrows.

Because the arrows are defined in terms of indices this means that the order of the objects becomes important and therefore must be held in a list/array rather than a set.

The issue of list verses array is a performance issue, more of that later.

It seems to me that there is a complimentary coding of graph where the arrows are a set of external objects and each node would be defined as two lists of indices: a list of incoming nodes and a list of outgoing nodes. I have not implemented this complimentary coding because its more complicated and I can't think of a use for it. However I have implemented two special related cases:

In 'FunctionGraph' each vertex has one outgoing arrow and In 'MultifunctionGraph' each vertex has exactly 'n' outgoing arrows where 'n' is the same for every vertex. These limitations mean that they can be coded more efficiently by having the arrow information directly associated with each vertex. As its name suggests 'FunctionGraph' can represent a function, a mapping where the domain and codomain are the same finite set of objects over which it is defined.

'MultifunctionGraph' can represent multiple function graphs such as Cayley graphs. Although these are special cases of the general graph, and could have used the general coding it is more efficient coding them in this way. They have a number of functions which are not applicable to the general case.

The graph structures are concerned with finite graphs, that is finite numbers of vertices. It would be interesting to find ways to encode repetitive or repeating structures in an efficient way.

Now I come to an issue which gives me a lot of concern: the representation so far includes only the information required to define the pure mathematical structures but there is other information associated with graphs which helps to make it more human understandable such as names for arrows and diagram coordinates. I think this information is very important because there are great benefits to human users in being able to 'see' the structure in an accessible way. As a general rule I think it is important to separate out these issues and as far as I can I put the graphics stuff into the graphics framework: 'scene.spad.pamphlet'. However, in this case, I have not managed to separate out these issues.

I did consider creating a wrapper domain, which would be external to the graph code, that would allow annotation and coordinate information to be associated with a vertex.

  Rep := Record(value:S,name:String,posX:NNI,posY:NNI)

However, if we want to do this with arrow information (which we do), then we would have to have a separate external arrow domain. There might be some benefits to this but its also quite messy, if we continue to use indexes then they have no meaning outside the graph and if we specify to objects directly then there are efficiency issues. If we do all that then, the Rep will be free of annotation and coordinate information, but the graph code still needs to know about coordinate information. For example, if we are taking the product of two graphs, then we can combine the coordinate of the two operands to generate useful coordinate information for the product graph as a whole.

So, in the end, I could not separate out the graphical/annotation information. It was just easier and more efficient to leave this information in Rep even though it goes against certain principles.

There is another issue about what goes into Rep, at the moment only certain combinations of graph type types are possible, for instance, we can't have a function 'FunctionGraph' with weighted arrows, it would be more general to allow all combinations of graph? If we do then the memory usage goes up a bit but if we don't then we need lots of combinations of domains:

There are other types of graph that I would like to experiment with, for instance, what I think of as a multilevel graph which perhaps could be implemented in equivalent ways:

More about 'multilevel graph' here.

How should these graph structures fit in and relate to the rest of the Axiom code library? It seems to me that structures like Tree, POSET/lattice are special cases of graph? Also there may be more general structures like Closed Cartesian Category (CCC) that should be categories in the code library?

Performance Issues

There is plenty of scope to improve the code. I have not tested how well it scales up (in terms of memory usage and runtime) but I suspect not very well at the moment. I think there is a lot of scope to improve the algorithms used.

There is the issue (pointed out by Waldek) of using lists verses arrays in Rep. If we are thinking about how well this would scale up then I guess:

I guess it would be nice to have both mutable and immutable graphs but that would add even more permutations of domain types.

To Do

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.