mfe- / datastructures.algorithms Goto Github PK

When setting a custom width and height >40 on the VertexControl on a directed graph the arrow is underneath the control. Therefore it looks like that the arrow isn't displayed. The ShiftConverter is currently using hardcoded +-7.

To fix this:

• Pass additonal parameter with width and height of control to ShiftConverter
• Calculate a reasonable value which can be used to shift the arrow

Remove old legacy issues which are related to DataStructures/Interfaces/IData.cs, DataStructures/Interfaces/INode.cs . The resulting interfaces for the datastructure is to unhandy.

To be able to set the CornerRadius in the VertexControl a CornerRadius DP should be created

• basic implementation
• tests
• priorityQueue

• Define or extend interface of IVertex which makes it possible to use the internal Guid for comparision of vertex1 and vertex2; Possible candidate IComparable<Guid> or IEquatable<IntPtr>
• Adjust algo.

Repro steps:

1. Clone the code from main branch and open with VS2022.

2. Press F5 to launch the DataStructures.UI.Demo project.

3. Select node 3 and right-click to choose BreadthFirstSearch option.
   

4. It will throw Object reference not set to an instance of an object at DataStructures.UI.Demo\Window1ViewModel.cs:line 116

Findings:
After checking the line 116, we found the vertex object is null.

Another issue:

1. Press F5 to launch the DataStructures.UI.Demo project.
2. Select node 3 and right-click to choose Kruskal option.

Excepted Result:
The screen should show this result.

Actual Result:
The screen doesn't do any changes. It keeps in this:

• Currently the Width and Height are hardcoded. The VertexContro should adopt the height and width of the Datatemplate.
• Also make CornerRadius to the VertexControl accessable.

vertices in a undirected graph will be connected by two edges.
E.g (where "->" and "<-" is representing an edge):
v1 -> v2
v1 <- v1

This fact requires to implement additonal checks in DFS and other graph algorithm.
E.g.:

    private static IEnumerable<IEdge> DepthFirstSearch(IVertex current, List<IEdge> edges, IVertex goal)
    {
        //mark edges
        foreach (IEdge e in current.Edges)
        {
            //check if we found the goal
            if (e.V.Equals(goal))
            {
                //some special behaviour duo circlues which we have to consider resulting of the our model (undirected: 1->3, 3->1)
                if (!edges.First().U.Edges.SelectMany(a => a.V.Edges).ToList().Exists(y => y.Equals(e))//schauen ob er zurückgehen will
                    || (edges.First().U.Edges.SelectMany(a => a.V.Edges).ToList().Exists(y => y.Equals(e) && //(kreis existiert mit IEdge ausgehend vom start), (schauen ob dazwischen noch andere IEdges sind)
                    edges.Find(delegate (IEdge ed) { return ed.V == e.U && ed.U != e.V; }) != null)))
                {
                    edges.Add(e);
                    return edges;
                }
           [...]

Therefore we should provide a method which considers the opposite edge when checking if the edge was already visitied.

Keeping the whole vertex /edge list in memory allocates too much space in some scenarios.
When iterating over vertices /edge list, it should be possible to outsource them (for example into a file by using the existing deserializing function or simply save the guid of the vertex or edge).

• Implement outsourcing part of the vertice/edge list by saving them into a file.

Remove INPC from IVertex(Vertex).
Because the UI GraphControl requires INPC we can create an own Vertex class which implements INPC

When generating more than 250000 edges with Generate_Grid_Graph there are many collisions using Edge.GetHashCode

return Math.Abs(U.GetHashCode()) + (V != null ? Math.Abs(V.GetHashCode()) : 0);

U.GetHashCode() =       return this._Guid.Equals((obj as Vertex)?._Guid);

Currently workaround.

return ($"{U}{V}" == $"{edge.U}{edge.V}" || $"{U}{V}" == $"{edge.V}{edge.U}");

Maybe the Guid of the Vertex should be exposed in IVertex so it can be used for comparison in the implementation of Edge.
The Edge itself could generate a new Guid of Vertex.U and Vertex.V.

https://gist.github.com/mfe-/c23279f73f1b2373eeeb4a8baa5d7906