Comments (1)
Here is some code that can traverse a graph given a starting node and a function to get to the next items. It is assumed there are no circular dependencies. It could be improved by making DepthFirst non-recursive.
public readonly record struct TraversalCallbacks<T>(
Func<(T? Previous, T Current, T Next), bool>? AllowEnter = null,
Action<(T? Previous, T Current)>? Enter = null,
Action<(T? Previous, T Current)>? Exit = null)
{
public static TraversalCallbacks<T> CreatePreventRevisits()
{
HashSet<T> visited = new();
return new(AllowEnter: t => {
var allow = visited.Add(t.Next);
return allow;
});
}
}
public static class Traversal
{
public static IEnumerable<T> DepthFirst<T>(
T current,
Func<T, IEnumerable<T>> getNextItems,
TraversalCallbacks<T> callbacks = default,
T? previous = default)
{
callbacks.Enter?.Invoke((previous, current));
yield return current;
foreach (var next in getNextItems(current))
{
if (callbacks.AllowEnter?.Invoke((previous, current, next)) ?? true)
{
foreach (var grandChild in DepthFirst(next, getNextItems, callbacks, current))
yield return grandChild;
}
}
callbacks.Exit?.Invoke((previous, current));
}
public static IEnumerable<T> TopologicalSort<T>(
T current,
Func<T, IEnumerable<T>> getNextItems,
TraversalCallbacks<T> callbacks = default,
T? previous = default)
{
// Get the whole graph first (assuming everything is reachable from the current node)
HashSet<T> unvisited = new();
DepthFirst(current, getNextItems)
.ForEach(n => unvisited.Add(n));
HashSet<T> visited = new();
Queue<T> results = new();
TraversalCallbacks<T> callbacks2 =
new(
Enter: t =>
{
visited.Add(t.Current);
unvisited.Remove(t.Current);
},
Exit: t =>
{
results.Enqueue(t.Current);
},
AllowEnter: t =>
{
var allow = !visited.Contains(t.Next);
return allow;
});
while (unvisited.Count > 0)
DepthFirst(unvisited.First(), getNextItems, callbacks2).ForEach(_ => {});
return results;
}
}
// TEST
//A -> B
//A -> D
//A -> E
//B -> C
//C -> G
//D -> G
//E -> F
//F -> D
string[] GetNext(string current) => current switch
{
"A" => ["B", "D", "E"],
"B" => ["C"],
"C" => ["G"],
"D" => ["G"],
"E" => ["F"],
"F" => ["D"],
_ => Array.Empty<string>(),
};
Assert.Equal<string>(
["G", "C", "B", "D", "F", "E", "A"],
Traversal.TopologicalSort("A", GetNext));
from firely-cql-sdk.
Related Issues (20)
- Handling late-bound types - incorrect CQL or we need some more magic? HOT 3
- Incorrect translation of binding name in QICore model? HOT 2
- References to codesystems defined elsewhere are not yet supported HOT 1
- FHIRHelpers hack - how far do we go? HOT 2
- Query results are demoted to singles too aggressively HOT 3
- How to handle type matching cases HOT 3
- A `let` cannot refer to an alias of a let that comes before it in the same scope HOT 1
- Extension.value is a DataType, and using it will raise errors. HOT 2
- Java CQL->ELM compiler seems to use FHIR types or bindings that do not exist. HOT 2
- Cleanup - DirectedGraph HOT 3
- Time zone offsets are rendered as DateTimeOffsets incorrectly in some cases HOT 3
- CQL->ELM compiler leaves out crucial type information HOT 4
- ExpressionBuilder skips the TypeResolver in some cases
- 1.1 - Eliminate method ExpressionBuilder.GetProperty
- 1.1 Create an 'All' solution containing all projects, move tests from Demo to CQL HOT 1
- Demo solution does not all the necessary projects from the repo
- Multi-source queries with singletons as source are not/not completely supported HOT 2
- Add back property init setters for vocab stuff HOT 3
- Unify DefinitionDictionary and the resolution stuff in Cql2Elm. HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from firely-cql-sdk.