Martin Baker wrote:
>
> Are you interested in an implementation of graph theory I have put
> here:
> https://github.com/martinbaker/fricas/blob/master/src/algebra/graph.spad.pamphlet
>
> If so there is a tutorial here:
> http://www.euclideanspace.com/maths/standards/program/mycode/discrete/graph/
>
It looks very interesting. I have the following comments:
- you provide 'spanningForestNode' which IIUC will give list of
as many trees as there are vertices in the graph. However,
usually one needs a single tree per connected component.
- in description of 'spanningTreeArrow' you say that the
it is expanded up to moment when it is impossible the.
expand it without getting repeated arrow. If this description
is true then the thing is quite different than a tree so
the name is misleading.
- for WeightedGraph it is natural make type of weights into
a type parameter. For path algorithm we would then require
this parameter to come from OrderedAbelianMonoid.
- WeightedGraph associates extra info with arrows. Sometimes
we need extra info at vertices, so that would be another kind
of graph.
- AFAICS you consistenly use lists for representation. That is
fine if you want to incrementallu construct graphs. But most
(all ???) efficient graph algorithms assume that vertices
are some interval in integers and represent other info in
arrays.
--
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.
