Yog.FSharp
Getting Started Examples API Reference GitHub

Eulerian Module

Namespace: Yog.Multi
Assembly: Yog.FSharp.dll

Eulerian circuit algorithms for multigraphs.

An Eulerian circuit is a trail that visits every edge exactly once and returns to the starting vertex.

Functions and values

Function or value Description

findEulerianCircuit graph

Full Usage: findEulerianCircuit graph

Parameters:
Returns: EdgeId list option

Some edgeIdList forming the circuit, or None if no circuit exists.

Finds an Eulerian circuit if one exists.

Conditions

  • Graph must be connected
  • All vertices must have even degree (for undirected)
  • For directed: in-degree = out-degree for all vertices

Example

1: 
2: 
3: 

match Eulerian.findEulerianCircuit graph with
| Some path -> printfn "Eulerian circuit: %A" path
| None -> printfn "No Eulerian circuit exists"

Use Cases

  • Route planning (visit every road exactly once)
  • DNA sequencing (de Bruijn graphs)
  • Chinese Postman Problem
union case Option.Some: Value: 'T -> Option<'T>
val path: obj
val printfn: format: Printf.TextWriterFormat<'T> -> 'T
union case Option.None: Option<'T>

graph : MultiGraph<'n, 'e>
Returns: EdgeId list option

Some edgeIdList forming the circuit, or None if no circuit exists.