Menu
I'm trying to do a cyclic graph in F#
My node type looks something like this:
type Node = { Value : int; Edges : Node list }
My question is: Do I need to make Edges mutable in order to have cycles?
871
A cyclic graph is a graph containing at least one graph cycle. A graph that is not cyclic is said to be acyclic. A cyclic graph possessing exactly one (undirected, simple) cycle is called a unicyclic graph.
You can check for cycles in a connected component of a graph as follows. Find a node which has only outgoing edges. If there is no such node, then there is a cycle.
Approach: Using the graph coloring method, mark all the vertex of the different cycles with unique numbers. Once the graph traversal is completed, push all the similar marked numbers to an adjacency list and print the adjacency list accordingly.
F# makes it possible to create immediate recursive object references with cycles, but this really only works on (fairly simple) records. So, if you try this on your definition it won't work:
let rec loop =
{ Value = 0;
Edges = [loop] }
However, you can still avoid mutation - one reasonable alternative is to use lazy values:
type Node = { Value : int; Edges : Lazy<Node list>}
This way, you are giving the compiler "enough time" to create a loop value before it needs to evaluate the edges (and access the loop value again):
let rec loop =
{ Value = 0;
Edges = lazy [loop] }
In practice, you'll probably want to call some functions to create the edges, but that should work too. You should be able to write e.g. Edges = lazy (someFancyFunction loop).
Alternatively, you could also use seq<Edges> (as sequences are lazy by default), but that would re-evaluate the edges every time, so you probably don't want to do that.
127
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
