[?] Seeking a recommendation: QuikGraph integration

[HG-Dev]

I'm interested in integrating ObservableCollection interfaces with QuikGraph to support the use of a directed graph as a model with MVVM architecture, but the complexity of creating an ISynchronizedView or ISortableSynchronizedView for graphs has left me puzzled. In QuikGraph, there are multiple types of collections used to store vertex and edge information, but the most common structure can be summed up as:

1. A list of <TVertex>
2. A dictionary mapping <TVertex> to List<TEdge> where TEdge : IEdge<TVertex>. IEdge guarantees that TEdge has TVertex Source and TVertex Target properties.

QuikGraph provides an interface with events for vertex addition / removal and edge addition / removal. We can interpret this to mean that one graph has two "observable" views: the vertex list, and all edges regardless of vertex. We could also view the graph to be a Dictionary<TVertex, List<TEdge>>, but this would imply an ObservableDictionary<TVertex, ObservableList<TEdge>>... and this brings us back to the integration problem.

Putting aside the QuikGraph dependency for a moment, what would be a valid synchronized view for a graph? Some ideas...

• Implement IObservableCollection for both <TVertex> and <TEdge>, and require CreateView to be used via IObservableCollection<>.CreateView
• Layer IObservableCollection such that one view allows for the creation of another view, i.e. IObservableCollection<KeyValuePair<TVertex, IObservableCollection<TEdge>>>. (big code smell here)
• Instead of implementing interfaces directly on the Graph class, have public IObservableCollection properties for vertices and edges
• Create an entirely new IObservableDataTable interface and do not treat inter-collection "relations" as additional collection objects <- This might be the conceptually soundest solution.

I'd be thrilled if I could get some advice on observing these sorts of complex collections.

[TaviTruman]

Hi HG-Dev, here is the code that I wrote and test myself. I use the R3, ObservableCollection.R3 and the QuickGraph libraries:

ObservableQuickGraph.cs:

` using System.Collections.Specialized; using ObservableCollections; using QuickGraph;

namespace R3.QuickGraphDemo.Observable.Graph { ///

/// Represents an observable graph with vertices of type TVertex and edges of type TEdge. /// Implements observability for vertices and edges using ObservableCollections. ///

/// The type of vertices. /// The type of edges, implementing IEdge<TVertex>. public class ObservableQuickGraph<TVertex, TEdge> where TEdge : IEdge where TVertex : notnull { ///

/// Gets the collection of vertices. ///

public ObservableList Vertices { get; private set; }

    /// <summary>
    /// Gets the dictionary mapping vertices to their associated edges.
    /// </summary>
    public ObservableDictionary<TVertex, ObservableList<TEdge>> Edges { get; private set; }

    /// <summary>
    /// Gets a synchronized view of the vertices collection.
    /// </summary>
    public INotifyCollectionChangedSynchronizedView<TVertex> VerticesView { get; private set; }

    /// <summary>
    /// Gets the collection of all edges.
    /// </summary>
    public ObservableList<TEdge> AllEdges { get; private set; }

    /// <summary>
    /// Gets a synchronized view of the edges collection.
    /// </summary>
    public INotifyCollectionChangedSynchronizedView<TEdge> AllEdgesView { get; private set; }

    /// <summary>
    /// Reactive property to signal vertices collection changes.
    /// </summary>
    public ReactiveProperty<Unit> VerticesChanges { get; }

    /// <summary>
    /// Initializes a new instance of the ObservableQuickGraph class.
    /// </summary>
    public ObservableQuickGraph()
    {
        Vertices = new ObservableList<TVertex>();
        Edges = new ObservableDictionary<TVertex, ObservableList<TEdge>>();
        AllEdges = new ObservableList<TEdge>();

        VerticesView = Vertices.CreateView(x => x).ToNotifyCollectionChanged();
        AllEdgesView = AllEdges.CreateView(x => x).ToNotifyCollectionChanged();

        // Initialize the reactive property
        VerticesChanges = new ReactiveProperty<Unit>();

        // Subscribe to the CollectionChanged event and update the ReactiveProperty
        Vertices.CollectionChanged += OnVerticesCollectionChanged;

        // Subscribe to the ReactiveProperty to handle vertex changes
        VerticesChanges.Subscribe(_ => HandleVerticesChanged());
    }

    /// <summary>
    /// Handles the CollectionChanged event for the vertices collection.
    /// Updates the reactive property and calls HandleVerticesChanged.
    /// </summary>
    /// <param name="e">The event arguments for the collection change.</param>
    private void OnVerticesCollectionChanged(in NotifyCollectionChangedEventArgs<TVertex> e)
    {
        // FOL: ∀e (CollectionChanged(Vertices, e) → HandleVerticesChanged(e) ∧ VerticesChanges.Value = Unit.Default)
        // OTL: Start(Transaction: OnVerticesCollectionChanged) → HandleVerticesChanged(e) ∧ VerticesChanges.Value = Unit.Default → End(Transaction)
        HandleVerticesChanged(e);
        VerticesChanges.Value = Unit.Default;
    }

    /// <summary>
    /// Handles changes to the vertices collection, updating the edges dictionary accordingly.
    /// </summary>
    /// <param name="e">The event arguments for the collection change (optional).</param>
    private void HandleVerticesChanged(NotifyCollectionChangedEventArgs<TVertex> e = default)
    {
        // OTL: Start(Transaction: HandleVerticesChanged)
        // FOL: ∀v ∈ e.NewItems (¬Edges.ContainsKey(v) → Edges[v] = new ObservableList<TEdge>())
        if (e.Action == NotifyCollectionChangedAction.Add && e.NewItems != null)
        {
            foreach (var newItem in e.NewItems)
            {
                if (!Edges.ContainsKey(newItem))
                {
                    var edges = new ObservableList<TEdge>();
                    Edges[newItem] = edges;
                }
            }
        }

        // FOL: ∀v ∈ e.OldItems (Edges.ContainsKey(v) → ∀e ∈ Edges[v] (AllEdges.Remove(e)) ∧ Edges.Remove(v))
        if (e.Action == NotifyCollectionChangedAction.Remove && e.OldItems != null)
        {
            foreach (var oldItem in e.OldItems)
            {
                if (Edges.ContainsKey(oldItem))
                {
                    var edges = Edges[oldItem];
                    foreach (var edge in edges)
                    {
                        AllEdges.Remove(edge);
                    }
                    Edges.Remove(oldItem);
                }
            }
        }
        // OTL: End(Transaction)
    }

    /// <summary>
    /// Adds a vertex to the graph.
    /// </summary>
    /// <param name="vertex">The vertex to add.</param>
    public void AddVertex(TVertex vertex)
    {
        // OTL: Start(Transaction: AddVertex)
        // FOL: ¬Vertices.Contains(vertex) → Vertices.Add(vertex)
        Vertices.Add(vertex);
        // OTL: End(Transaction)
    }

    /// <summary>
    /// Adds an edge to the graph.
    /// </summary>
    /// <param name="edge">The edge to add.</param>
    public void AddEdge(TEdge edge)
    {
        // OTL: Start(Transaction: AddEdge)
        // SOL: ∀v ∈ {edge.Source, edge.Target} (¬Edges.ContainsKey(v) → Edges[v] = new ObservableList<TEdge>())
        if (!Edges.ContainsKey(edge.Source))
        {
            Edges[edge.Source] = new ObservableList<TEdge>();
        }
        if (!Edges.ContainsKey(edge.Target))
        {
            Edges[edge.Target] = new ObservableList<TEdge>();
        }

        // FOL: Edges[edge.Source].Add(edge) ∧ AllEdges.Add(edge)
        Edges[edge.Source].Add(edge);
        AllEdges.Add(edge);
        // OTL: End(Transaction)
    }

    /// <summary>
    /// Removes a vertex from the graph.
    /// </summary>
    /// <param name="vertex">The vertex to remove.</param>
    public void RemoveVertex(TVertex vertex)
    {
        // OTL: Start(Transaction: RemoveVertex)
        // FOL: Vertices.Contains(vertex) → Vertices.Remove(vertex)
        Vertices.Remove(vertex);
        // OTL: End(Transaction)
    }

    /// <summary>
    /// Removes an edge from the graph.
    /// </summary>
    /// <param name="edge">The edge to remove.</param>
    public void RemoveEdge(TEdge edge)
    {
        // OTL: Start(Transaction: RemoveEdge)
        // FOL: Edges.ContainsKey(edge.Source) → Edges[edge.Source].Remove(edge)
        if (Edges.ContainsKey(edge.Source))
        {
            Edges[edge.Source].Remove(edge);
        }

        // FOL: Edges.ContainsKey(edge.Target) → Edges[edge.Target].Remove(edge)
        if (Edges.ContainsKey(edge.Target))
        {
            Edges[edge.Target].Remove(edge);
        }

        // FOL: AllEdges.Contains(edge) → AllEdges.Remove(edge)
        AllEdges.Remove(edge);
        // OTL: End(Transaction)
    }
}

}

`

ViewModel:

` using System.Windows.Data; using System.Windows.Threading; using ObservableCollections; using QuickGraph; using R3.QuickGraphDemo.Observable.Graph;

namespace R3.QuickGraphDemo.ViewModels { ///

/// ViewModel class for the QuickGraphDemo application. /// Manages the observable graph and provides commands for interacting with the graph. ///

public class ViewModel : IDisposable { ///

/// The graph model holding vertices of type int and edges of type Edge<int>. ///

public ObservableQuickGraph<int, Edge> Graph { get; }

    /// <summary>
    /// Views for observing changes in vertices and edges.
    /// </summary>
    public INotifyCollectionChangedSynchronizedView<int> VerticesView { get; }
    public INotifyCollectionChangedSynchronizedView<Edge<int>> AllEdgesView { get; }

    /// <summary>
    /// Commands for clearing the graph and adding a vertex.
    /// </summary>
    public ReactiveCommand<Unit> ClearCommand { get; }
    public ReactiveCommand<Unit> AddVertexCommand { get; }

    /// <summary>
    /// Reactive property for debug output.
    /// </summary>
    public BindableReactiveProperty<string> DebugOutput { get; }

    private readonly object _syncLock = new object();

    /// <summary>
    /// Constructor initializes the graph, commands, and debug output.
    /// </summary>
    public ViewModel()
    {
        Graph = new ObservableQuickGraph<int, Edge<int>>();
        Graph.AddVertex(1);
        Graph.AddVertex(2);
        Graph.AddEdge(new Edge<int>(1, 2));

        VerticesView = Graph.Vertices.CreateView(x => x).ToNotifyCollectionChanged();
        AllEdgesView = Graph.AllEdges.CreateView(x => x).ToNotifyCollectionChanged();

        // Ensure thread-safe access to the collections
        BindingOperations.EnableCollectionSynchronization(VerticesView, _syncLock);
        BindingOperations.EnableCollectionSynchronization(AllEdgesView, _syncLock);

        DebugOutput = new BindableReactiveProperty<string>(string.Empty);

        ClearCommand = new ReactiveCommand<Unit>();
        AddDebugOutput("ClearCommand initialized.");
        ClearCommand
            .ObserveOnDispatcher(Dispatcher.CurrentDispatcher)
            .Subscribe(_ =>
            {
                // FOL: ∀v ∈ Graph.Vertices, ∀e ∈ Graph.AllEdges (Clear(v) ∧ Clear(e))
                // OTL: Start(Transaction: ClearCommand) → Graph.Vertices.Clear() ∧ Graph.AllEdges.Clear() → End(Transaction)
                AddDebugOutput("ClearCommand Executed");
                Graph.Vertices.Clear();
                Graph.AllEdges.Clear();
                AddDebugOutput("Vertices and edges cleared.");
                LogCurrentState();
            });

        AddVertexCommand = new ReactiveCommand<Unit>();
        AddDebugOutput("AddVertexCommand initialized.");
        AddVertexCommand
            .ObserveOnDispatcher(Dispatcher.CurrentDispatcher)
            .Subscribe(_ =>
            {
                // FOL: ∃v (v ∉ Graph.Vertices) → AddVertex(v)
                // OTL: Start(Transaction: AddVertexCommand) → Graph.AddVertex(v) ∧ (Graph.Vertices.Count > 1 → Graph.AddEdge(e)) → End(Transaction)
                AddDebugOutput("AddVertexCommand Executed");
                var newVertex = Graph.Vertices.Count + 1;
                Graph.AddVertex(newVertex);

                // SOL: ∃e (Edge(e.Source, e.Target) ∧ (e.Source = newVertex - 1) ∧ (e.Target = newVertex)) → AddEdge(e)
                if (Graph.Vertices.Count > 1)
                {
                    Graph.AddEdge(new Edge<int>(newVertex - 1, newVertex));
                }
                AddDebugOutput($"Vertex {newVertex} added.");
                LogCurrentState();
            });
    }

    /// <summary>
    /// Adds a message to the debug output.
    /// </summary>
    /// <param name="message">The debug message to add.</param>
    private void AddDebugOutput(string message)
    {
        // FOL: ∀m ∈ DebugOutput (Append(m))
        DebugOutput.Value += $"{DateTime.Now:yyyy-MM-dd HH:mm:ss}: {message}{Environment.NewLine}";
    }

    /// <summary>
    /// Logs the current state of the graph to the debug output.
    /// </summary>
    private void LogCurrentState()
    {
        // FOL: ∀v ∈ Graph.Vertices (Log(v))
        // FOL: ∀e ∈ Graph.AllEdges (Log(e))
        AddDebugOutput($"Current Vertices: {string.Join(", ", Graph.Vertices)}");
        AddDebugOutput($"Current Edges: {string.Join(", ", Graph.AllEdges)}");
    }

    /// <summary>
    /// Disposes of the resources used by the ViewModel.
    /// </summary>
    public void Dispose()
    {
        // SOL: ∀c ∈ {ClearCommand, AddVertexCommand, VerticesView, AllEdgesView} (Dispose(c))
        // OTL: Start(Transaction: Dispose) → Dispose(ClearCommand) ∧ Dispose(AddVertexCommand) ∧ Dispose(VerticesView) ∧ Dispose(AllEdgesView) → End(Transaction)
        ClearCommand.Dispose();
        AddVertexCommand.Dispose();
        VerticesView.Dispose();
        AllEdgesView.Dispose();
    }
}

}

`

WPF View (XAML):

` <Window x:Class="QuickGraphDemo.MainWindow" xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" xmlns:d="http://schemas.microsoft.com/expression/blend/2008" xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:local="clr-namespace:QuickGraphDemo" xmlns:viewModels="clr-namespace:QuickGraphDemo.ViewModels" mc:Ignorable="d" Title="QuickGraph Demo using R3 and ObservableCollections" Height="450" Width="800">

`

[HG-Dev]

Err, thanks ChatGPT.

[TaviTruman]

@HG-Dev Okay let me fix this as the code I posted does not work!

[TaviTruman]

Err, thanks ChatGPT.

Okay, I have updated my experiment based on your requirements using QuickGraph, R3 and ObservableCollection; I am also attaching the VS project for your review. Was a fun bit of coding :-)

QuickGraphDemo.zip