Martin Baker wrote:
>
> I have updated the graph theory code here:
>
> https://github.com/martinbaker/fricas/blob/master/src/algebra/graph.spad.pa=
> mphlet
>
> and also the graphics framework here:
>
> https://github.com/martinbaker/fricas/blob/master/src/algebra/scene.spad.pa=
> mphlet
>
> The changes to the graph theory depend on the changes to the graphics
> framework so it would be quite good if you chose to include both with
> FriCAS. At least I would not have to do so many loads before doing any
> work!
Changes to scene.spad.pamphlet contain a lot of whitespace change,
do you really mean it? Also, did you compare with version that
I commited? Apparently your new version is wiping out a few
spelling corrections that I made (construct vs constuct).
>
> The changes to the graphics framework affect the user interface, but
> only the functions for drawing arrows.
>
> On Wednesday 01 Feb 2012 17:32:52 Waldek Hebisch wrote:
> > Yes. I have my own ideas how graph should be done and as you
> > see Franz Lehner also did work in this direction, so we will
> > probably be pushing some changes (more about this tomorrow).
>
> I have not seen this, did I miss something?
I had to many distractions. Anyway, here are remarks. I think
that we should have a collection of classical algorithms for graphs.
And they should be efficient. I hope that I can quicky code
a few "easy" algorithms: minimal/arbitrary spanning forest,
connected components, strongly connected components,
biconected components, minimal distances, maximal flow.
I have some ideas how to quickly do semi-reasonable isomorphizm
test -- should work fast for large "random" graphs, but
behave poorly on regular graphs, but that while can be done
relatively quickly, almost surely will take too much time for
coming release. Other things like planarity (there is linear
algorithm for this), chromatic number, etc are highly desirable,
but reguire much more effort. All the algorithms should use
array representation of graphs (otherwise there is no hope for
efficient implementation). ATM it is not clear for me if graphs
represented in arrays (we need a bunch of arrays for single graph)
should get their own domain -- we can simply make an algorithm
package which just takes array arguments and converts
graphs to array form in the graph domain. Certainly such
graphs should _not_ have drawing related information
(such information would be pure overhead, with no reasonable
way to update and of limited use because it is practically
impossible to look at very large graph as a whole).
> But I have started to address your earlier concerns:
>
> 1) I have renamed Graph category to 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.
I must admit that ATM I would limit effort spent on infinite
graphs. Basically, for infinite graphs for almost any
operations I can imagine sensible representation such that
this operation is impossible to do. As simplest example
consider graphs that have finite degree at some nodes, but
infinite at other nodes and allow retrival of adjacent nodes
only as a Stream. Or worse, graphs where you can not list
neighbours, but can test if an edge is in the edge set.
Note that in the first case (adjacent nodes as a stream)
it may happen that you can not decide if node is in the
graph.
In fact you may have theoretically finite but "practically
almost infinite" graphs: there are so called binary decision
diragrams (and variations) which in some cases allow
to represent huge structures (say of 10^100 nodes) in
much smaller space. They are widely used for finite
automata, but in principle should also work for graphs.
If you try to retrive list of neighbours of a node of such
graph you will overflow available memory, so only way
to work on them is via relational operations.
Now, ATM we do not have infinite graphs, and IHMO it
is pointless trying to anticipate all possiblities,
Murphy say the one of possibilites that you did not
consider will be the important one. Given that Franz
has some code, it makes sense to make some accomodations,
but that code will evolve and only later we will know
what is the right thing to do.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
