fubardevelopment / quickgraph Goto Github PK

View Code? Open in Web Editor NEW

8.0 8.0 2.0 4.92 MB

Fork of https://quickgraph.codeplex.com/

License: Microsoft Public License

C# 80.25% Smalltalk 19.73% Batchfile 0.01% Python 0.01%

quickgraph's People

Contributors

Stargazers

Watchers

Forkers

mdkiefer southarsch

quickgraph's Issues

CP-11613: Bidictional.Dijkstra is broken..

From unknown CodePlex user on Thursday, 13 November 2008 00:32:11

My needs are for an undirected graph. Using the hopefully functional Bidrectional, all edges have been added twice with swapped vertices
I do not care about dead end points. So for faster run times, I remove them - saves about 30% of cpu time..
ie:

    For Each Vertex As PointVertex In Graph.Vertices
            If Graph.InDegree(Vertex) = 1 Then
                If Graph.OutDegree(Vertex) = 1 Then
                        Dim Tag As Integer = Graph.OutEdge(Vertex, 0).Tag
                        DeadEdges.Add(Tag) ' do not want to kill the iterator deleting here
                        DeadEndsThisPass = DeadEndsThisPass + 1
                End If
            End If
    Next
    // Remove the DeadEdges from the graph

Since entering a vertice, which has only one way out (the entrance), will not get us a shorter path to ANYWHERE,
I feel strongly that it should not affect the results of the shortest path process.

This is not the case..

Deads Ends REMOVED

Shortest path from 0 to 1: Edges = 209   Distance = 18.6871025766148
Shortest path from 0 to 2:   No Path
Shortest path from 0 to 3: Edges = 229   Distance = 25.1420981198549
Shortest path from 0 to 4: Edges = 279   Distance = 30.185930068833
Shortest path from 0 to 5: Edges = 278   Distance = 30.1852232020982
Shortest path from 0 to 6: Edges = 279   Distance = 30.1909297394133
Shortest path from 0 to 7: Edges = 282   Distance = 30.0787995138543
Shortest path from 0 to 8: Edges = 281   Distance = 30.0036287763947
Shortest path from 0 to 9: Edges = 280   Distance = 29.9563015749597
Shortest path from 0 to 10: Edges = 285   Distance = 30.1029364471016
Shortest path from 0 to 11: Edges = 284   Distance = 30.100420657676
Shortest path from 0 to 12: Edges = 279   Distance = 30.0861420986841
Shortest path from 0 to 13: Edges = 278   Distance = 30.080859530371
Shortest path from 0 to 14: Edges = 277   Distance = 30.078852230681
Shortest path from 0 to 15: Edges = 276   Distance = 30.0748250836192
Shortest path from 0 to 16: Edges = 275   Distance = 30.0647169042368
Shortest path from 0 to 17: Edges = 276   Distance = 30.066050328606
Shortest path from 0 to 18: Edges = 276   Distance = 30.0703928405923
Shortest path from 0 to 19: Edges = 277   Distance = 30.0762113850632
Shortest path from 0 to 20: Edges = 278   Distance = 30.0822445408384
Shortest path from 0 to 21: Edges = 283   Distance = 30.1869257130482
Shortest path from 0 to 22: Edges = 283   Distance = 30.0977362529961
Shortest path from 0 to 23: Edges = 280   Distance = 30.0916260071138
Shortest path from 0 to 24: Edges = 281   Distance = 30.1977373594932
Shortest path from 0 to 25: Edges = 280   Distance = 30.1967825679065
Shortest path from 0 to 26: Edges = 281   Distance = 30.0929290774213
Shortest path from 0 to 27: Edges = 282   Distance = 30.0941029083026
Shortest path from 0 to 28: Edges = 230   Distance = 25.2547387461507
Shortest path from 0 to 29: Edges = 230   Distance = 25.1470488312715
Shortest path from 0 to 30: Edges = 229   Distance = 25.249641895234
Shortest path from 0 to 31: Edges = 374   Distance = 31.2457734131495
Shortest path from 0 to 32: Edges = 207   Distance = 18.9107195764928
Shortest path from 0 to 33: Edges = 208   Distance = 18.9195743423705
Shortest path from 0 to 34: Edges = 206   Distance = 18.8739869214042
Shortest path from 0 to 35: Edges = 210   Distance = 18.6878648595076

Dead Ends PRESENT

Shortest path from 0 to 1: Edges = 227   Distance = 19.0100456527529
Shortest path from 0 to 2:   No Path
Shortest path from 0 to 3: Edges = 261   Distance = 26.5644314427133
Shortest path from 0 to 4: Edges = 314   Distance = 31.6082941722276
Shortest path from 0 to 5: Edges = 313   Distance = 31.6075873054928
Shortest path from 0 to 6: Edges = 314   Distance = 31.6132938428079
Shortest path from 0 to 7: Edges = 318   Distance = 31.7467679565931
Shortest path from 0 to 8: Edges = 316   Distance = 31.4259928797893
Shortest path from 0 to 9: Edges = 315   Distance = 31.3786656783543
Shortest path from 0 to 10: Edges = 316   Distance = 31.3790951118068
Shortest path from 0 to 11: Edges = 314   Distance = 31.3868351149137
Shortest path from 0 to 12: Edges = 309   Distance = 31.3725565559218
Shortest path from 0 to 13: Edges = 308   Distance = 31.3672739876087
Shortest path from 0 to 14: Edges = 307   Distance = 31.3652666879187
Shortest path from 0 to 15: Edges = 306   Distance = 31.3612395408569
Shortest path from 0 to 16: Edges = 305   Distance = 31.3511313614745
Shortest path from 0 to 17: Edges = 305   Distance = 31.3507770247126
Shortest path from 0 to 18: Edges = 304   Distance = 31.3449197391847
Shortest path from 0 to 19: Edges = 305   Distance = 31.3507382836556
Shortest path from 0 to 20: Edges = 306   Distance = 31.3567714394308
Shortest path from 0 to 21: Edges = 317   Distance = 31.6386417573992
Shortest path from 0 to 22: Edges = 313   Distance = 31.3841507102338
Shortest path from 0 to 23: Edges = 310   Distance = 31.3780404643515
Shortest path from 0 to 24: Edges = 316   Distance = 31.6201014628878
Shortest path from 0 to 25: Edges = 315   Distance = 31.6191466713011
Shortest path from 0 to 26: Edges = 311   Distance = 31.379343534659
Shortest path from 0 to 27: Edges = 312   Distance = 31.3805173655403
Shortest path from 0 to 28: Edges = 262   Distance = 26.6770720690091
Shortest path from 0 to 29: Edges = 262   Distance = 26.5693821541298
Shortest path from 0 to 30: Edges = 261   Distance = 26.6719752180924
Shortest path from 0 to 31: Edges = 341   Distance = 14.0733716554419
Shortest path from 0 to 32: Edges = 206   Distance = 20.449694441428
Shortest path from 0 to 33: Edges = 207   Distance = 20.4585492073057
Shortest path from 0 to 34: Edges = 205   Distance = 20.4129617863394
Shortest path from 0 to 35: Edges = 228   Distance = 19.0108079356457

CP-9384: Wrong path from Dijkstra algorithm

From unknown CodePlex user on Wednesday, 20 February 2008 00:01:44

Hi, I have downloaded the source file 15206 and tried to use the Dijkstra algorithm to get shortest route.

I have created a simple program, it works great.

However, I found a case where the algorithm gave me wrong route A -> B - > E , where the correct route should be A -> C -> D -> E, as tested from
http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html

I have attach the snap shot from http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html:

The simple program i tested:

using System;
using System.Collections.Generic;
using System.Text;
using QuickGraph;
using QuickGraph.Algorithms.ShortestPath;
using QuickGraph.Algorithms.Observers;
using QuickGraph.Algorithms;
using System.Collections.ObjectModel;


namespace DijkstraAlgoTest
{
    public class DijkstraAlgo
    {
        private static AdjacencyGraph<string, Edge<string>> graph;
        private static DijkstraShortestPathAlgorithm<string, Edge<string>> algo;
        private static List<string> path;
        private static VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver;

        public static void Main(string[] args)
        {
            CreateGraph();
            Console.ReadLine();
        }

        public static void CreateGraph()
        {
            graph = new AdjacencyGraph<string, Edge<string>>(true);

            // Add some vertices to the graph
            graph.AddVertex("A");
            graph.AddVertex("B");
            
            graph.AddVertex("D");
            graph.AddVertex("C");
            graph.AddVertex("E");
          
            // Create the edges
            Edge<string> a_b = new Edge<string>("A", "B");          
            Edge<string> a_c = new Edge<string>("A", "C");
            Edge<string> b_e = new Edge<string>("B", "E");
            Edge<string> c_d = new Edge<string>("C", "D");
            Edge<string> d_e = new Edge<string>("D", "E");
           
            // Add edges to the graph
            graph.AddEdge(a_b);
            graph.AddEdge(a_c);
            graph.AddEdge(c_d);
            graph.AddEdge(d_e);
            graph.AddEdge(b_e);
           
            // Define some weights to the edges
            Dictionary<Edge<string>, double> weight = new Dictionary<Edge<string>, double>(graph.EdgeCount);
            weight.Add(a_b, 30);
            weight.Add(a_c, 30);
            weight.Add(b_e, 60);
            weight.Add(c_d, 40);
            weight.Add(d_e, 4);
                      
            algo = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, weight);

            // Attach a Vertex Predecessor Recorder Observer to give us the paths
            predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>();
            
            using (ObserverScope.Create<IVertexPredecessorRecorderAlgorithm<string, Edge<string>>>(algo, predecessorObserver))
            {
                // Run the algorithm with A set to be the source
                algo.Compute("A");
            }

            path = new List<string>();
            PopulatePath("E");

            path.Reverse();

            foreach (string v in path)
            {
                Console.Write("{0} -> ", v);
            }
        }

        static void PopulatePath(string vertex)
        {
            path.Add(vertex);
            if (vertex == "A")
                return;           
            PopulatePath(predecessorObserver.VertexPredecessors[vertex].Source);            
        }
    }
}

Please advice.
Thankyou.

CP-11579: Optimization for UndirectedGraph.ContainsEdge?

From unknown CodePlex user on Thursday, 06 November 2008 22:20:31

Since the graph is Undirected, we by definition do not care about the ordering of vertices.
So, when adding an edge, sort the vertices, then add the edge.

this would allow the inner loop of ContainsEdge to be reduced to:

if (edge.Source.Equals(source) && edge.Target.Equals(target))
return true;

Thus saving Edges.Count compares per call.

We do have to do the initial compares while adding the edge, but we only load the graph
once, then work with it repeatedly.

Perhaps an IVertex interface and then an IUndirectedVertex, which requires IEquatable and IComparable
would be needed.

CP-12359: dijkstra

From unknown CodePlex user on Monday, 12 January 2009 07:37:07

I've problem with dijkstra and the last changeset. It' s too slow.

Attached two sample applications.
The first (Testgraph_01) is developed with a Changeset before 29945 (I don't remember).
Te second one (Testgraph_02) with the last changeset (30070).

As you can see, the second one It's too much slow and uses over 50% of CPU.

Bye

TestGraph_01.zip
TestGraph_02.zip
Graph.zip

CP-11566: BidirectionalGraph.clone exists, yet no other GraphTypes have this.

From unknown CodePlex user on Wednesday, 05 November 2008 20:57:28

Make all graph types cloneable.

CP-12470: EdgeEventArgs not accepting its' event method

From unknown CodePlex user on Monday, 26 January 2009 05:59:58

EdgeEventArgs not accepting its' event method.
It demands an edge like Edge<Vertex> edge.

QuickGraph v3.2.40122

CP-12240: Question about Prim spanning tree algorithm

From unknown CodePlex user on Monday, 29 December 2008 06:39:11

Hello,
I tried to call PrimMinimumSpanningTreeAlgorithm for simple input and I got wrong results. So this is my input:
AdjacencyGraph<TVertex,TEdge> adjency_graph with edges (1,2), (3,2),(3,4),(1,4) and all weights are equal to 1.
I use the following code to call PrimMinimumSpanningTreeAlgorithm:

     IDictionary<TEdge, double> weights = new Dictionary<TEdge, double>();
     IEnumerable<TEdge> edges = adjency_graph.Edges;
            foreach (TEdge edge in edges)
            {
                weights.Add(edge, 1);
            }
       UndirectedGraph<TVertex, TEdge> undirectedgraph =
               new UndirectedGraph<TVertex, TEdge>();
            foreach (TVertex v in adjency_graph.Vertices)
                undirectedgraph.AddVertex(v);
            foreach (TEdge e1 in adjency_graph.Edges)
                if (!undirectedgraph.ContainsEdge(e1.Source, e1.Target))
                    undirectedgraph.AddEdge(e1);

Then I call PrimMinimumSpanningTreeAlgorithm in debugging mode

  Prim_alg =
             new PrimMinimumSpanningTreeAlgorithm<TVertex, TEdge>(undirectedgraph, weights);
 
           
            Prim_alg.Compute(root);  //root is 1

I see in InternalCompute method that only (1,2) and (1,4) edges give TreeEdge event and it is not sufficient because vertex 3 does not belong such tree.
I suppose that problem is because you process only edge.Target but not processedge.Source. I tried to improve
code of InternalCompute as the following (in the cycle):

  TVertex second_end;
 foreach (var edge in this.VisitedGraph.AdjacentEdges(u))
                    {
                        if (cancelManager.IsCancelling)
                            return;
                        double edgeWeight = this.EdgeWeights[edge];
                        //My
                        if(edge.Target.Equals(u))
                        {
                            second_end = edge.Source;
                        }
                        else
                            second_end=edge.Target;
                        if (
                            queue.Contains(second_end) &&
                            edgeWeight < this.minimumWeights[second_end]
                            )
                        {
                            this.minimumWeights[second_end] = edgeWeight;
                            this.queue.Update(second_end);
                            this.OnTreeEdge(edge);
                        }
                    }

Am I right or I have missed something?
Thank you
Evgeny

CP-11877: BidrectionalGraph.ContainsEdge Optimization - Re: Issue 11612

From unknown CodePlex user on Thursday, 04 December 2008 17:24:30

Issue 11612 - Closed Today at 11:31 PM by pelikhan
By design. Source/Target should be in the graph.

if this behavior is BY DESIGN, then just DELETE the function. Why check to see if it is
present if BY DESIGN it should be in the graph? Seems redundant.

In order to maintain backwards compatibility just have the function return TRUE and exit. This would give a
performance gain, due to the lack of iterating..

CP-11550: Saving Graphs

From unknown CodePlex user on Sunday, 02 November 2008 13:57:50

I've tried using the GraphMLSerializer but I'm currently having problems with the deserialization process. I'm using the BidirectionalGraph.Here's the graph initialization.

// single line
var distributionGraph = new idirectionalGraph<IdentifiableVertex, IdentifiableEdge<IdentifiableVertex>>();

Here's the serialization code:

var s = new GraphMLSerializer<IdentifiableVertex, IdentifiableEdge<IdentifiableVertex>>();
var x = new XmlTextWriter( GRAPH_FILE, Encoding.UTF8 );
s.Serialize( x, distributionGraph );

Here's the deserialization code.

var s = new GraphMLSerializer<IdentifiableVertex, IdentifiableEdge<IdentifiableVertex>>();
var vFact = new IdentifiableVertexFactory();
var eFact = new IdentifiableEdgeFactory<IdentifiableVertex>();
var r = new XmlTextReader( GRAPH_FILE );
s.Deserialize( r, distributionGraph, vFact, eFact );

The error message I'm getting is "Cannot find vertex 1" or "There is no root element"

CP-12604: Undirected Graphs Visualization

From unknown CodePlex user on Friday, 13 February 2009 17:07:32

Hi again,

Firstly, thanks for the quicker reponse, I really appreciate your effort.

Once wrote this post, I began to research deeper and I found that the graphviz writer has always, or in major cases, the same behaviour.

It includes the header digraph on dot files without take into account the graph type. I don't know if this is an error or not because I'm a begginer with this API.

I solved it with a "little trick". Keep the data structure of UndirectedGraph for compatibility purposes, and change edge direction toNone on rendering tier, and get a true correspondence between data structure and rendering tier.

Regards.

CP-12469: BidirectionalGraph KeyNotFoundException errror

From unknown CodePlex user on Monday, 26 January 2009 05:54:38

I am getting this error for trying to add an edge to a Bidirectional graph.

System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
 at System.ThrowHelper.ThrowKeyNotFoundException()
 at System.Collections.Generic.Dictionary`2.get_Item(TKey key)
 at QuickGraph.BidirectionalGraph`2.AddEdge(TEdge e)

My code is:

this.graph = new BidirectionalGraph<Vertex<int>, Edge<Vertex<int>>>(true);

I created a Vertex class for the X and Z values for the Key, and am using Edge<> for the value. I created the two verteces I want to use for the edge (Target and Source then addEdge(Edge<Vertex> e)), yet I get a Key not found error.

For QuickGraph v3.2.40122

CP-12273: Question about Prim spanning tree algorithm

From unknown CodePlex user on Friday, 02 January 2009 13:55:41

Hello,

I tried your implementation of Prim spanning tree algorithm after your changes: I downloaded release 29565 and changed my program
according to MinimumSpanningTreePrim method fromAlgorithmExtensions class. You just use here yourUndirectedDijkstraShortestPathAlgorithm and then return tree that consists from edges that are included in shortest paths from some (default) vertex to all other vertices. IMHO that did not guarantee that the result is minimum spanning tree. I tested this algorithm with a graph from book "Graph theory" by N.Christofides, chapter 7 “Trees, paragraph 3.4 (I have Russian translation of 1975 year). The weight of minimal spanning tree is equal to 63. But your algorithm gives 88. I modified slightly MinimumSpanningTreePrim and tried it for all vertices being the root. The minimal weight is when the root is vertex 10 and it is equal to 72. But it is greater than 63. So the minimal tree could not be founded by this way. I add an XML representation of this graph so you could check it:

<?xml version="1.0" encoding="utf-8"?>
  <graph>
    <node id="1" />
    <node id="2" />
    <node id="3" />
    <node id="4" />
    <node id="5"  />
    <node id="6" />
    <node id="7" />
    <node id="8" />
    <node id="9" />
    <node id="10" />
    <node id="11" />
    <node id="12" />
    <edge id="1_2" source="1" target="2" weight="6" />
    <edge id="1_4" source="1" target="4" weight="11" />
    <edge id="1_5" source="1" target="5" weight="5" />
    <edge id="2_5" source="2" target="5" weight="8" />
    <edge id="2_3" source="2" target="3" weight="15" />
    <edge id="2_4" source="2" target="4" weight="18" />
    <edge id="2_7" source="2" target="7" weight="11" />
    <edge id="3_4" source="3" target="4" weight="8" />
    <edge id="3_8" source="3" target="8" weight="18" />
    <edge id="3_9" source="3" target="9" weight="6" />
    <edge id="4_6" source="4" target="6" weight="10" />
    <edge id="4_7" source="4" target="7" weight="7" />
    <edge id="4_11" source="4" target="11" weight="17" />
    <edge id="5_6" source="5" target="6" weight="15" />
    <edge id="5_7" source="5" target="7" weight="9" />
    <edge id="6_11" source="6" target="11" weight="3" />
    <edge id="7_8" source="7" target="8" weight="9" />
    <edge id="7_9" source="7" target="9" weight="4" />
    <edge id="7_11" source="7" target="11" weight="12" />
    <edge id="7_10" source="7" target="10" weight="13" />
    <edge id="8_9" source="8" target="9" weight="14" />
    <edge id="8_12" source="8" target="12" weight="5" />
    <edge id="9_10" source="9" target="10" weight="19" />
    <edge id="10_12" source="10" target="12" weight="2" />
    <edge id="11_12" source="11" target="12" weight="7" />
  </graph>

CP-11567: UndirectedGraph.ClearAdjacentEdges has a bug

From unknown CodePlex user on Wednesday, 05 November 2008 21:32:15

specifically in UndirectedGraph.ClearAdjacentEdges

if (edge.Source.Equals(v))
this.adjacentEdges[edge.Target].Remove(edge);
else
this.adjacentEdges[edge.Source].Remove(edge);

The problem here is that my somewhat dirty data
(Tiger RT1 records from the US Census road networks, all 18.3 gigs of them)
sometimes has identical source and target points.
So only one gets removed, the other lingers on in the graph.
If the points are coincident, both should be removed.
Underneath the RT1 points there is an RT2 chain, which might describe a loop
beginning and ending at the same point.. So it could actually be valid data..

Thanks in advance.

CP-5365: AlgoUtility.IsolatedVertices returns vertices with neighbours

From unknown CodePlex user on Thursday, 23 August 2007 13:02:37

LS,

I wrote a small program to illustrate a problem that I encountered while working with QuickGraph (change set 7900, still present in 9398). The program searches for isolated vertices in a graph. At this stage, I – sadly – don’t have enough time to dig into your code, but hopefully this post helps you to improve your library by reproducing what I find to be a bug.

When I build the following bidirectional graph (see uploaded file and code below), I expect AlgoUtility.IsolatedVertices to return TT05, TT06, TT10 and TT11. However it additionally returns TT02, TT13, TT14 and TT19.

From this (and assuming you use degree==0 of a vertex to see if it’s isolated), I suspect that in order to obtain the degree of the vertex the in-degree and out-degree of a vertex are subtracted instead of added. If this were the case, it would be incorrect, they should be added (I used ‘Introduction to Algorithms’ by you-know-who, pp1081 to check).

Sincerely,

Marijn

PS: I couldn’t resist to, so I checked anyway and in your code I see you indeed use

        public int Degree(Vertex v)
        {
            return this.OutDegree(v) - this.InDegree(v);
        }

in the class BidirectionalGraph on line 134. To me, this seems wrong. Am I mistaken?

The Graph ‘Example 1’

        public static BidirectionalGraph<String, MarkedEdge<String, String>> Example1()
        {
            BidirectionalGraph<String, QuickGraph.MarkedEdge<string, string>> g =
                new BidirectionalGraph<string, MarkedEdge<string, string>>();
 
            List<string> lst = new List<string>();
            for (int i = 0; i < 20; i++)
            {
                lst.Add(string.Format("TT{0:00}", i));
            }
 
            g.AddVertexRange(lst.ToArray());
 
            g.AddEdge(new MarkedEdge<string, string>(lst[0], lst[1], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[1], lst[2], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[2], lst[3], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[3], lst[4], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[3], lst[1], "user constraint"));
            g.AddEdge(new MarkedEdge<string, string>(lst[7], lst[8], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[8], lst[9], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[8], lst[9], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[12], lst[13], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[13], lst[14], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[14], lst[15], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[16], lst[17], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[18], lst[19], "unload order"));
            g.AddEdge(new MarkedEdge<string, string>(lst[19], lst[9], "unload order"));
 
            return g;
        }

Progam

    class Program
    {
        private static log4net.ILog log = log4net.LogManager.GetLogger(typeof(Program));
 
        static void Main(string[] args)
        {
            log.Info("Application started.");
 
            BidirectionalGraph<String, MarkedEdge<String, String>> g = Dummies.Example1();
 
            Analyze(g);
 
            Export.Save(g, "d:\\dev\\data\\graphs\\test");
            
            log.Info("Application Ended.");
 
        }
 
        static void Analyze<Vertex, Edge>(BidirectionalGraph<Vertex, Edge> g)
                        where Edge : IEdge<Vertex>
        {
            foreach (Vertex v in AlgoUtility.IsolatedVertices(g))
            {
                log.InfoFormat("Found Isolated vertex: {0}", v);
            }
 
            foreach (Vertex v in Helpers.Roots(g))
            {
                log.DebugFormat("Found root: {0}", v);
            }
 
            foreach (Vertex v in Helpers.Sinks(g))
            {
                log.DebugFormat("Found sink: {0}", v);
            }
        }
 
 
    }

Output

[graph-testing]
INFO  APP_GraphOutput.Program - Application started.
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT02
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT05
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT06
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT10
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT11
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT13
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT14
INFO  APP_GraphOutput.Program - Found Isolated vertex: TT19
DEBUG APP_GraphOutput.Program - Found root: TT00
DEBUG APP_GraphOutput.Program - Found root: TT05
DEBUG APP_GraphOutput.Program - Found root: TT06
DEBUG APP_GraphOutput.Program - Found root: TT07
DEBUG APP_GraphOutput.Program - Found root: TT10
DEBUG APP_GraphOutput.Program - Found root: TT11
DEBUG APP_GraphOutput.Program - Found root: TT12
DEBUG APP_GraphOutput.Program - Found root: TT16
DEBUG APP_GraphOutput.Program - Found root: TT18
DEBUG APP_GraphOutput.Program - Found sink: TT04
DEBUG APP_GraphOutput.Program - Found sink: TT05
DEBUG APP_GraphOutput.Program - Found sink: TT06
DEBUG APP_GraphOutput.Program - Found sink: TT09
DEBUG APP_GraphOutput.Program - Found sink: TT10
DEBUG APP_GraphOutput.Program - Found sink: TT11
DEBUG APP_GraphOutput.Program - Found sink: TT15
DEBUG APP_GraphOutput.Program - Found sink: TT17
INFO  GraphUtils.Export - Saved file: d:\dev\data\graphs\test.dot
INFO  APP_GraphOutput.Program - Application Ended.
[/graph-testing]

CP-11367: Make AddVerticesAndEdge an extension method

From unknown CodePlex user on Tuesday, 23 September 2008 15:38:05

AddVerticesAndEdge is a nice shorthand.

It exists on AdjacencyGraph<T,E> but not UndirectedGraph<T,E>.

Seems like it would be a good candidate for an extension method on whichever IMutable* interface has both vertices and edges? If not, it would be nice to just have an implementation on UndirectedGraph.

Keep up the awesome work.

CP-11442: passing test

From unknown CodePlex user on Tuesday, 14 October 2008 02:15:13

--- Description
passing test

this.Test();

[TestMethod]
[PexGeneratedBy(typeof(Class1Test))]
public void Test02()
{
this.Test();
}

CP-12425: Serialization of GraphML <data> element as child <graph> node

From unknown CodePlex user on Wednesday, 21 January 2009 12:22:01

The GraphML schema allows user-defined data to be specified at the graph-level (a sibling of the edge and node list), as follows.

<key ... />
<graph>
  <node/>
  <edge/>
  <data><key ... /></data>
</graph>

Could this be supported in QuickGraph without too much refactoring?

CP-11224: Missing pages in the user manual wiki

From unknown CodePlex user on Friday, 12 September 2008 06:08:28

Some links on the user manual wiki take you a page displaying this message:
The wiki page does not exist

e.g.
User Manual -> Observer Concepts -> VertexPredecessorRecorderObserver
User Manual -> Graph Concepts -> Traversal Concepts -> IBidirectionalGraph

CP-477: RemoveVertex Events missing

From unknown CodePlex user on Monday, 21 May 2007 01:25:19

In BidirectionalGraph.RemoveVertex(Vertex v) when the vertex is removed, it also removes the in and out edges which connect to it.
Unfortunately, the EdgeRemoved Event is not raised when these edges are removed. This might happen with other graph types as well, but I haven't yet checked.
Just one line required to fix it though.

Cheers,
Iain

CP-9273: Abort doesn't work on Dijkstra algorithm

From unknown CodePlex user on Friday, 01 February 2008 13:54:48

I have a Dijkstra graph which I want to stop running when a particular node is reached (under certain circumstances). To do this, I added a FinishVertex listener to the algorithm, in which I want to abort the graph computation.

My first attempt was to call the Abort method on the Dijkstra algorithm. I found that this doesn't do anything because the Dijkstra algorithm uses a BredthFirstSearchAlgorithm internally, so the call wasn't going to the right code. I guess the intention is for this to be invisible, so I think the request should be passed through to the internal object.

My second attempt was to use the sender object passed in to the event handler:

AlgorithmBase<IVertexListGraph<int, MarkedEdge<int, MoveGraphRunnerData.MoveRouteLinkRow>>> searcher =
sender as AlgorithmBase<IVertexListGraph<int, MarkedEdge<int, MoveGraphRunnerData.MoveRouteLinkRow>>>;
sender.Abort();

This doesn't work because when the Dijkstra runs the BredthFirstSearchAlgorithm, it doesn't set the state of the algorithm to Running. I worked around this with a bit of reflection:

typeof(AlgorithmBase<IVertexListGraph<int, MarkedEdge<int, MoveGraphRunnerData.MoveRouteLinkRow>>>)
.GetField("state", BindingFlags.NonPublic | BindingFlags.Instance).SetValue(searcher, ComputationState.Running);

And now it works.

CP-11894: Problems with ShortestPathsBellmanFord

From unknown CodePlex user on Friday, 05 December 2008 21:20:04

Hi Pelikhan,

thanks for your reply.
testPath(1) was indeed a bad example as it is the source node.
But as I wrote, testPath is empty for any other node, too.
Can anybody verify that? Here is a complete test example:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using QuickGraph;
using QuickGraph.Algorithms;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            AdjacencyGraph<int, Edge<int>> testGraph = new AdjacencyGraph<int, Edge<int>>();
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 2));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 3));
            testGraph.AddVerticesAndEdge(new Edge<int>(3, 4));
            testGraph.AddVerticesAndEdge(new Edge<int>(1, 4));
            var testPath = testGraph.ShortestPathsBellmanFord<int, Edge<int>>(e => 1.0, 1);
            for (int i = 1; i <= 4; i++)
            {
                Console.WriteLine(testPath(i).Count());
            }
        }
    }
}

CP-11583: DepthFirstSearchAlgorithm.Visit

From unknown CodePlex user on Saturday, 08 November 2008 01:42:22

depth parameter is not used.

CP-11606: Undirected.ShortestPathsDijkstra does not work..

From unknown CodePlex user on Wednesday, 12 November 2008 01:50:29

out of (36*35)/2 items 5 return a path...

Background data, the nodes seem somewhat connected:

        VertexCount = 197817, EdgeCount = 262692
        36320 nodes have 1 Degree
        32516 nodes have 2 Degree
        92370 nodes have 3 Degree
        36167 nodes have 4 Degree
        411 nodes have 5 Degree
        32 nodes have 6 Degree
        1 nodes have 7 Degree

I am iterating an array of 36 vertexes.

for i = 0 to 35
      Djikstra(point(i))
      for j = i+1 to 35
           if Path(point(j)).count > 0 then debug.writeline...
      Next
Next

Results

Index 1 with TLID 78325681 Failed 
Shortest path from 3 to 28: 3
Shortest path from 3 to 29: 1
Shortest path from 3 to 30: 2
Index 5 with TLID 78359719 Failed 
Index 6 with TLID 78359720 Failed 
Index 7 with TLID 78359722 Failed 
Index 8 with TLID 78359723 Failed 
Index 9 with TLID 78359724 Failed 
Index 10 with TLID 78359725 Failed 
Index 11 with TLID 78359726 Failed 
Index 12 with TLID 78359728 Failed 
Index 13 with TLID 78359729 Failed 
Index 14 with TLID 78359730 Failed 
Index 15 with TLID 78359731 Failed 
Index 16 with TLID 78359732 Failed 
Index 17 with TLID 78359733 Failed 
Index 18 with TLID 78359734 Failed 
Index 19 with TLID 78359735 Failed 
Index 20 with TLID 78359736 Failed 
Index 21 with TLID 78360012 Failed 
Index 22 with TLID 78364692 Failed 
Index 23 with TLID 78364693 Failed 
Index 24 with TLID 78365567 Failed 
Index 25 with TLID 78365568 Failed 
Index 26 with TLID 78365569 Failed 
Index 27 with TLID 78365570 Failed 
Shortest path from 29 to 30: 1
Shortest path from 32 to 33: 1

The indexes not in the list like 0, 34,35 did not fail, nor did they find any paths..

On failure the call stack looks like this the attached file.
Failure always happens on calls to Graph.ShortestPathsDijkstra

 	mscorlib.dll!System.ThrowHelper.ThrowKeyNotFoundException() + 0x24 bytes	
 	mscorlib.dll!System.Collections.Generic.Dictionary<System.__Canon,System.__Canon>.this[System.__Canon].get(System.__Canon key) + 0x4c bytes	
 	GraphSharp.Controls.dll!GraphSharp.Controls.GraphLayout<*my_namespace*.IVertex,*my_namespace*.IEdge,QuickGraph.IBidirectionalGraph<*my_namespace*.IVertex,*my_namespace*.IEdge>>.CreateEdgeControl(*my_namespace*.IEdge edge = SameSiteEdge Input = "JXBG-S1-2512", Output = "JXBG-S13-2512") + 0x1c4 bytes	
 	GraphSharp.Controls.dll!GraphSharp.Controls.GraphLayout<*my_namespace*.IVertex,*my_namespace*.IEdge,QuickGraph.IBidirectionalGraph<*my_namespace*.IVertex,*my_namespace*.IEdge>>.OnMutation() + 0x313 bytes	
 	GraphSharp.Controls.dll!GraphSharp.Controls.GraphLayout<*my_namespace*.IVertex,*my_namespace*.IEdge,QuickGraph.IBidirectionalGraph<*my_namespace*.IVertex,*my_namespace*.IEdge>>.DoNotificationLayout.AnonymousMethod__24(object s = {System.ComponentModel.BackgroundWorker}, System.ComponentModel.RunWorkerCompletedEventArgs e = {System.ComponentModel.RunWorkerCompletedEventArgs}) + 0x51 bytes	
 	WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.InternalRealCall(System.Delegate callback, object args, bool isSingleParameter) + 0x1a7 bytes	
 	WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.TryCatchWhen(object source = {System.Windows.Threading.Dispatcher}, System.Delegate callback, object args, bool isSingleParameter, System.Delegate catchHandler = null) + 0x4c bytes	
 	WindowsBase.dll!System.Windows.Threading.DispatcherOperation.InvokeImpl() + 0xc0 bytes	
 	mscorlib.dll!System.Threading.ExecutionContext.runTryCode(object userData) + 0x178 bytes	
 	[Native to Managed Transition]	
 	[Managed to Native Transition]	
 	mscorlib.dll!System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext executionContext, System.Threading.ContextCallback callback, object state) + 0x62 bytes	
 	WindowsBase.dll!System.Windows.Threading.DispatcherOperation.Invoke() + 0x6a bytes	
 	WindowsBase.dll!System.Windows.Threading.Dispatcher.ProcessQueue() + 0x2b0 bytes	
 	WindowsBase.dll!System.Windows.Threading.Dispatcher.WndProcHook(System.IntPtr hwnd, int msg, System.IntPtr wParam, System.IntPtr lParam, ref bool handled) + 0xb4 bytes	
 	WindowsBase.dll!MS.Win32.HwndWrapper.WndProc(System.IntPtr hwnd, int msg, System.IntPtr wParam, System.IntPtr lParam, ref bool handled) + 0xce bytes	
 	WindowsBase.dll!MS.Win32.HwndSubclass.DispatcherCallbackOperation(object o) + 0x96 bytes	
 	WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.InternalRealCall(System.Delegate callback, object args, bool isSingleParameter) + 0xec bytes	
 	WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.TryCatchWhen(object source = {System.Windows.Threading.Dispatcher}, System.Delegate callback, object args, bool isSingleParameter, System.Delegate catchHandler = null) + 0x4c bytes	
 	WindowsBase.dll!System.Windows.Threading.Dispatcher.InvokeImpl(System.Windows.Threading.DispatcherPriority priority, System.TimeSpan timeout, System.Delegate method, object args, bool isSingleParameter) + 0xde bytes	
 	WindowsBase.dll!MS.Win32.HwndSubclass.SubclassWndProc(System.IntPtr hwnd, int msg, System.IntPtr wParam, System.IntPtr lParam) + 0x177 bytes	
 	[Native to Managed Transition]	
 	[Managed to Native Transition]	
 	WindowsBase.dll!System.Windows.Threading.Dispatcher.TranslateAndDispatchMessage(ref System.Windows.Interop.MSG msg) + 0x46 bytes	
 	WindowsBase.dll!System.Windows.Threading.Dispatcher.PushFrameImpl(System.Windows.Threading.DispatcherFrame frame) + 0xf1 bytes	
 	WindowsBase.dll!System.Windows.Threading.DispatcherOperation.Wait(System.TimeSpan timeout) + 0x86 bytes	
 	WindowsBase.dll!System.Windows.Threading.Dispatcher.InvokeImpl(System.Windows.Threading.DispatcherPriority priority, System.TimeSpan timeout, System.Delegate method, object args, bool isSingleParameter) + 0x128 bytes	
 	WindowsBase.dll!System.Windows.Threading.DispatcherSynchronizationContext.Send(System.Threading.SendOrPostCallback d, object state) + 0x43 bytes	
 	Microsoft.Practices.CompositeUI.dll!Microsoft.Practices.CompositeUI.EventBroker.Subscription.CallOnUserInterface(object sender = {Eterra.Apf.Services.Viewport.Wpf.ViewportWrapperWpf}, System.EventArgs e = {System.EventArgs}, System.Collections.Generic.List<System.Exception> exceptions = Count = 0) Line 222 + 0x63 bytes	C#
 	Microsoft.Practices.CompositeUI.dll!Microsoft.Practices.CompositeUI.EventBroker.Subscription.EventTopicFireHandler(object sender = {Eterra.Apf.Services.Viewport.Wpf.ViewportWrapperWpf}, System.EventArgs e = {System.EventArgs}, System.Collections.Generic.List<System.Exception> exceptions = Count = 0, System.Diagnostics.TraceSource traceSource = {System.Diagnostics.TraceSource}) Line 170 + 0x19 bytes	C#
 	Microsoft.Practices.CompositeUI.dll!Microsoft.Practices.CompositeUI.EventBroker.EventTopic.CallSubscriptionHandlers(object sender = {Eterra.Apf.Services.Viewport.Wpf.ViewportWrapperWpf}, System.EventArgs e = {System.EventArgs}, Microsoft.Practices.CompositeUI.EventBroker.EventTopicFireDelegate[] handlers = {Microsoft.Practices.CompositeUI.EventBroker.EventTopicFireDelegate[1]}) Line 423 + 0x37 bytes	C#
 	Microsoft.Practices.CompositeUI.dll!Microsoft.Practices.CompositeUI.EventBroker.EventTopic.Fire(object sender = {Eterra.Apf.Services.Viewport.Wpf.ViewportWrapperWpf}, System.EventArgs e = {System.EventArgs}, Microsoft.Practices.CompositeUI.WorkItem workItem = {Eterra.Apf.Services.Viewport.ViewportWorkItem}, Microsoft.Practices.CompositeUI.EventBroker.PublicationScope scope = Global) Line 245 + 0x6a bytes	C#
 	Microsoft.Practices.CompositeUI.dll!Microsoft.Practices.CompositeUI.EventBroker.EventTopic.Fire(Microsoft.Practices.CompositeUI.EventBroker.Publication publication = {Microsoft.Practices.CompositeUI.EventBroker.Publication}, object sender = {Eterra.Apf.Services.Viewport.Wpf.ViewportWrapperWpf}, System.EventArgs e = {System.EventArgs}) Line 526 + 0x91 bytes	C#
 	Microsoft.Practices.CompositeUI.dll!Microsoft.Practices.CompositeUI.EventBroker.Publication.PublicationHandler(object sender = {Eterra.Apf.Services.Viewport.Wpf.ViewportWrapperWpf}, System.EventArgs e = {System.EventArgs}) Line 86 + 0x2f bytes	C#
 	Eterra.Apf.Services.dll!Eterra.Apf.Services.Viewport.Wpf.ViewportWrapperWpf.viewport_Activated(object sender = {Eterra.Apf.Services.Viewport.Wpf.ViewportWpf}, System.EventArgs e = {System.EventArgs}) Line 596 + 0x23 bytes	C#
 	PresentationFramework.dll!System.Windows.Window.OnActivated(System.EventArgs e) + 0xb8 bytes	
 	Eterra.Apf.Services.dll!Eterra.Apf.Services.Viewport.Wpf.ViewportWpf.OnActivated(System.EventArgs e = {System.EventArgs}) Line 483 + 0xf bytes	C#
 	PresentationFramework.dll!System.Windows.Window.WmActivate(System.IntPtr wParam) + 0x48 bytes	
 	PresentationFramework.dll!System.Windows.Window.WindowFilterMessage(System.IntPtr hwnd, int msg, System.IntPtr wParam, System.IntPtr lParam, ref bool handled) + 0x17c bytes	
 	PresentationCore.dll!System.Windows.Interop.HwndSource.PublicHooksFilterMessage(System.IntPtr hwnd, int msg, System.IntPtr wParam, System.IntPtr lParam, ref bool handled) + 0xa4 bytes	
 	WindowsBase.dll!MS.Win32.HwndWrapper.WndProc(System.IntPtr hwnd, int msg, System.IntPtr wParam, System.IntPtr lParam, ref bool handled) + 0xce bytes	
 	WindowsBase.dll!MS.Win32.HwndSubclass.DispatcherCallbackOperation(object o) + 0x96 bytes	
 	WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.InternalRealCall(System.Delegate callback, object args, bool isSingleParameter) + 0xec bytes	
 	WindowsBase.dll!System.Windows.Threading.ExceptionWrapper.TryCatchWhen(object source = {System.Windows.Threading.Dispatcher}, System.Delegate callback, object args, bool isSingleParameter, System.Delegate catchHandler = null) + 0x4c bytes	
 	WindowsBase.dll!System.Windows.Threading.Dispatcher.InvokeImpl(System.Windows.Threading.DispatcherPriority priority, System.TimeSpan timeout, System.Delegate method, object args, bool isSingleParameter) + 0xde bytes	
 	WindowsBase.dll!MS.Win32.HwndSubclass.SubclassWndProc(System.IntPtr hwnd, int msg, System.IntPtr wParam, System.IntPtr lParam) + 0x177 bytes	
 	[Native to Managed Transition]	
 	[Managed to Native Transition]	
 	System.Windows.Forms.dll!System.Windows.Forms.NativeWindow.DefWndProc(ref System.Windows.Forms.Message m) + 0x9f bytes	
 	Eterra.Apf.Services.dll!Eterra.Apf.Services.Viewport.Wpf.ViewportWpf.ViewportWpfHiddenWindow.WndProc(ref System.Windows.Forms.Message m = {System.Windows.Forms.Message}) Line 1404 + 0x13 bytes	C#
 	System.Windows.Forms.dll!System.Windows.Forms.NativeWindow.DebuggableCallback(System.IntPtr hWnd, int msg = 6, System.IntPtr wparam, System.IntPtr lparam) + 0xad bytes	
 	[Native to Managed Transition]	
 	[Managed to Native Transition]	
 	WindowsBase.dll!System.Windows.Threading.DispatcherSynchronizationContext.Wait(System.IntPtr[] waitHandles, bool waitAll, int millisecondsTimeout) + 0x29 bytes	
 	[Native to Managed Transition]	
 	[Managed to Native Transition]	
 	GraphSharp.Controls.dll!GraphSharp.Controls.GraphLayout<*my_namespace*.IVertex,*my_namespace*.IEdge,QuickGraph.IBidirectionalGraph<*my_namespace*.IVertex,*my_namespace*.IEdge>>.DoNotificationLayout() + 0x5b bytes	
 	GraphSharp.Controls.dll!GraphSharp.Controls.GraphLayout<*my_namespace*.IVertex,*my_namespace*.IEdge,QuickGraph.IBidirectionalGraph<*my_namespace*.IVertex,*my_namespace*.IEdge>>.OnMutableGraph_EdgeAdded(*my_namespace*.IEdge edge = SameSiteEdge Input = "JXBG-S1-2512", Output = "JXBG-S13-2512") + 0x58 bytes	
 	[Native to Managed Transition]	
 	[Managed to Native Transition]	
 	QuickGraph.dll!QuickGraph.BidirectionalGraph<*my_namespace*.IVertex,*my_namespace*.IEdge>.OnEdgeAdded(*my_namespace*.IEdge args = SameSiteEdge Input = "JXBG-S1-2512", Output = "JXBG-S13-2512") + 0x58 bytes	
 	QuickGraph.dll!QuickGraph.BidirectionalGraph<*my_namespace*.IVertex,*my_namespace*.IEdge>.AddEdge(*my_namespace*.IEdge e = SameSiteEdge Input = "JXBG-S1-2512", Output = "JXBG-S13-2512") + 0x47e bytes

CP-12403: GraphML Deserialization for Missing <node>/<edge> Data Elements

From unknown CodePlex user on Monday, 19 January 2009 22:07:32

Consider the following graph.

<graph id="G" edgedefault="directed">
    <node id="0">
      <data key="isSpecial">true</data>
      <data key="isSuperSpecial">true</data>
    </node>
    <node id="1">
      <data key="isSuperSpecial">true</data>
    </node>
    <node id="2"/>
  </graph>

The IsSpecial and IsSuperSpecial keys are properties that are decorated with an appropriate XmlAttribtueAttribute. When I deserialize this graph, I am hoping that the missing property values for nodes 1,2 will be deserialized with a suitable default. However, none of the property values are deserialized, even the ones that are explicitly provided in node 0.

I'm not sure if this is intended, but the semantics appear correct for a GraphML document.

GraphML.zip

CP-11607: Undirected.ConnectedComponents

From unknown CodePlex user on Wednesday, 12 November 2008 02:33:42

Fails with stack overflow while trying to verify connectedness of the graph I am passing to Djikstra..

QuickGraph.Algorithms.Search.UndirectedDepthFirstSearchAlgorithm<TigerViewer.PointVertex,QuickGraph.TaggedEdge<TigerViewer.PointVertex,int>>.Visit(TigerViewer.PointVertex u = Coords: Cannot evaluate expression because the current thread is in a stack overflow state., int depth = 3406) Line 193 C#

Specific line is: if (u.Equals(e.Source))

Only the top line in the call stack, since they are all the same...

CP-12474: BidirectionalGraph addEdge() error

From unknown CodePlex user on Monday, 26 January 2009 11:35:09

I create two vertices and try to add a single edge, but get this error.

Code:

this.graph = new BidirectionalGraph<Vertex<int>, Edge<Vertex<int>>>(true);
this.edge = new Edge<Vertex<int>>(new Vertex<int>(0, 0), new Vertex<int>(0,0));
// more stuff
this.graph.addEdge(edge);

Error:

[01:29:01] System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
   at System.ThrowHelper.ThrowKeyNotFoundException()
   at System.Collections.Generic.Dictionary`2.get_Item(TKey key)
   at QuickGraph.BidirectionalGraph`2.AddEdge(TEdge e)

QuickGraph v 3.2.40122

CP-11603: More folders..

From unknown CodePlex user on Tuesday, 11 November 2008 20:31:47

the list of files in solution explorer is rather long.
how about folders for:

Interfaces
Events
Exceptions

CP-276: Stackbased Deep first traversal algorithm?

From unknown CodePlex user on Saturday, 12 May 2007 09:34:42

Hello,

Why did you use the recursive deep first traversal method instead a stack based algorithm? Can you provide such an algorithm or can i help you with this? If you inspect the stack based DFS and the queue based BFS you will notice many similarities, so you can refactor both algorithms to one base algorithm which is using only a different vertex buffer.

regards

Stefan

CP-11582: DepthFirstSearchAlgorithm.MaxDepth

From unknown CodePlex user on Saturday, 08 November 2008 01:32:49

Does not seem to be used..

Is this intended to signal to the search, the maximum depth reached at the end
of the search? Or perhaps to tell the search how many levels deep to search?

Thanks in advance.

CP-11612: BidirectionalGraph.ContainsEdge(TVertex source, TVertex target) has a bug..

From unknown CodePlex user on Thursday, 13 November 2008 00:14:14

if Source edge is not in the graph, it fails..

Disabling the contracts has side effects it appears.

CP-11568: Deserializing AdjacencyGraph

From unknown CodePlex user on Wednesday, 05 November 2008 22:54:18

Hello,

I am trying to binary serialize and deserialize an adjacency graph and I am getting this error when deserializing:

"The constructor to deserialize an object of type 'QuickGraph.AdjacencyGraph`2+VertexEdgeDictionary[EjemploQuickGraph.Nodo,EjemploQuickGraph.Arco]' was not found."

* All my classes are marked as Serializable.
* I use the .NET 2.0 version of QuickGraph (unfortunately)
* This is the piece of code I am using:

System.Runtime.Serialization.IFormatter formatter = new System.Runtime.Serialization.Formatters.Binary.BinaryFormatter();
System.IO.MemoryStream ms = new System.IO.MemoryStream();
formatter.Serialize(ms, grafo);

ms.Seek(0, System.IO.SeekOrigin.Begin);

object x = formatter.Deserialize(ms);

Where 'grafo' is the AdjacencyGraph.

CP-12472: EdgeEventArgs not accepting a method argument

From unknown CodePlex user on Monday, 26 January 2009 11:27:10

The EdgeEventArgs is not accepting a method argument, just an edge.
new EdgeEventArgs<Vertex, Edge<Vertex>>(this.RecordOutEdge); // ERROR

Error 2 Argument '1': cannot convert from 'method group' to 'QuickGraph.Edge<SmartMap.Vertex>' D:\Projects\SmartMap\SmartMap.cs 241

The intellisense wants me to put in Edge<Vertex> edge

QuickGraph v 3.2.40122

CP-12503: Compiling 2.0 on Mono

From unknown CodePlex user on Thursday, 29 January 2009 12:30:50

In 2.0/sources/QuickGraph/Algorithms/EulerianTrailAlgorithm.cs on line 216 there's an error:

[Task:File=/home/mikl/quickgraph/2.0/sources/QuickGraph/Algorithms/EulerianTrailAlgorithm.cs, Line=216, Column=46, Type=Error, Priority=Normal, Description=The call is ambiguous between the following methods or properties: `QuickGraph.TraversalHelper.GetFirstVertex<TVertex,TEdge>(QuickGraph.IVertexListGraph<TVertex,TEdge>)' and `QuickGraph.TraversalHelper.GetFirstVertex<TVertex,TEdge>(QuickGraph.IUndirectedGraph<TVertex,TEdge>)'(CS0121)]

The lines are:

            if (!this.TryGetRootVertex(out rootVertex)) 
                rootVertex = TraversalHelper.GetFirstVertex<TVertex, TEdge>(this.VisitedGraph);

It can be fixed by, e.g.:

	if (!this.TryGetRootVertex(out rootVertex))
	{
		if (this.VisitedGraph is IVertexListGraph<TVertex, TEdge>)
		{
			rootVertex = TraversalHelper.GetFirstVertex<TVertex, TEdge>(this.VisitedGraph as IVertexListGraph<TVertex, TEdge>);
		}
		else
		{
			rootVertex = TraversalHelper.GetFirstVertex<TVertex, TEdge>(this.VisitedGraph as IUndirectedGraph<TVertex, TEdge>);
		}
	}

I haven't tried with the 3.0-sources.

CP-11890: ShortestPathsDijkstra from AlgorithmExtensions.cs does infinite loop

From unknown CodePlex user on Friday, 05 December 2008 15:37:47

Hi,
I'm a student and I have been using the 3.0 release for a project with no problems, but when I moved to release 3.1 I noticed that the method ShortestPathsDijkstra from AlgorithmExtensions.cs does an infinite loop. I've tried compiling the last source (changeset 26955) with identical results. I managed to debug it and realized that in fact, the infinite loop is done in the "while" from the FlushVisitQueue method from the BreadthFirstSearchAlgorithm class, which is used by ShortestPathsDijkstra.
I could continue using the 3.0 release, but I'm very interested in the FibonacciQueue implementation that the 3.1 release includes.

Thank you for your attention.

CP-304: Critical Path

From unknown CodePlex user on Sunday, 13 May 2007 12:31:53

It is a DAG. I build a database schema representation as a graph. Vertexes are tables, edges are foreign key constraints.

I'm really illiterate on graph theory, hence why I'm asking if there is a way to find the critical path using the existing framework or if I have to modify one of the algorithms (DijkstraShortestPathAlgorithm perhaps) to do this. A DAG exactly represents my problem hence why I chose it.

As for the exact path, won't the DFS algorithm give me the shortest path to a node? Assuming, that I have multiple paths to a node, I need the critical path, not the shortest path.

Thank you.

-Nick

CP-11578: Bug in UndirectedGraph.AllowParallelEdges implementation with TaggedEdge

From unknown CodePlex user on Thursday, 06 November 2008 22:01:44

Specifically with AddVerticesAndEdge and AddEdge.

It appears that you simply check List to see if the TAGGED-edge is already present.
The problem is the underlying Edge (not tagged) can already be present, with a different tag.

The tag I choose should not be used in the determination of Parallel-ness,
otherwise AllowParallelEdges degenerates to AllowDuplicateTaggedEdges..

It looks necessary to iterate the base Edges to check for duplicates. Pity it will be much slower..

CP-11893: Support for Msagl 2.0?

From unknown CodePlex user on Friday, 05 December 2008 21:11:32

Hi all,

I just bought Msagl from the Microsoft store with the following assemblies:
Microsoft.Msagl, Version=2.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35
Microsoft.Msagl.Drawing, Version=2.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35
Microsoft.Msagl.GraphViewerGdi, Version=2.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35

But the newest Quickgraph.Msagl.dll refers to the following assembly files:
Microsoft.Msagl, Version=2.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35
Microsoft.Msagl.Drawing, Version=1.2.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35
Microsoft.Msagl.GraphViewerGDI, Version=1.2.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35

==> Could not load file or assembly 'Microsoft.Msagl.Drawing, Version=1.2.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35' or one of its dependencies. The located assembly's manifest definition does not match the assembly reference. (Exception from HRESULT: 0x80131040)

Do you have any plan to update Quickgraph for this?
Thanks in advance!

CP-11662: Possible bug in Dijkstra algorithm?

From unknown CodePlex user on Wednesday, 19 November 2008 21:49:40

I also am having some strange results.
I am guessing that you are using the bidirectionalGraph, as Undirected.Dijkstra does not work at this time.

My needs are for an undirected graph. Using the hopefully functional Bidrectional, all edges have been added twice with swapped vertices
I do not care about dead end points. So for faster run times, I remove them - saves about 30% of cpu time..
ie:

    For Each Vertex As PointVertex In Graph.Vertices
            If Graph.InDegree(Vertex) = 1 Then
                If Graph.OutDegree(Vertex) = 1 Then
                        Dim Tag As Integer = Graph.OutEdge(Vertex, 0).Tag
                        DeadEdges.Add(Tag) ' do not want to kill the iterator deleting here
                        DeadEndsThisPass = DeadEndsThisPass + 1
                End If
            End If
    Next
    // Remove the DeadEdges from the graph

Deads Ends REMOVED

Shortest path from 0 to 1: Edges = 209   Distance = 18.6871025766148
Shortest path from 0 to 2:   No Path
Shortest path from 0 to 3: Edges = 229   Distance = 25.1420981198549
Shortest path from 0 to 4: Edges = 279   Distance = 30.185930068833
Shortest path from 0 to 5: Edges = 278   Distance = 30.1852232020982
Shortest path from 0 to 6: Edges = 279   Distance = 30.1909297394133
Shortest path from 0 to 7: Edges = 282   Distance = 30.0787995138543
Shortest path from 0 to 8: Edges = 281   Distance = 30.0036287763947
Shortest path from 0 to 9: Edges = 280   Distance = 29.9563015749597
Shortest path from 0 to 10: Edges = 285   Distance = 30.1029364471016
Shortest path from 0 to 11: Edges = 284   Distance = 30.100420657676
Shortest path from 0 to 12: Edges = 279   Distance = 30.0861420986841
Shortest path from 0 to 13: Edges = 278   Distance = 30.080859530371
Shortest path from 0 to 14: Edges = 277   Distance = 30.078852230681
Shortest path from 0 to 15: Edges = 276   Distance = 30.0748250836192
Shortest path from 0 to 16: Edges = 275   Distance = 30.0647169042368
Shortest path from 0 to 17: Edges = 276   Distance = 30.066050328606
Shortest path from 0 to 18: Edges = 276   Distance = 30.0703928405923
Shortest path from 0 to 19: Edges = 277   Distance = 30.0762113850632
Shortest path from 0 to 20: Edges = 278   Distance = 30.0822445408384
Shortest path from 0 to 21: Edges = 283   Distance = 30.1869257130482
Shortest path from 0 to 22: Edges = 283   Distance = 30.0977362529961
Shortest path from 0 to 23: Edges = 280   Distance = 30.0916260071138
Shortest path from 0 to 24: Edges = 281   Distance = 30.1977373594932
Shortest path from 0 to 25: Edges = 280   Distance = 30.1967825679065
Shortest path from 0 to 26: Edges = 281   Distance = 30.0929290774213
Shortest path from 0 to 27: Edges = 282   Distance = 30.0941029083026
Shortest path from 0 to 28: Edges = 230   Distance = 25.2547387461507
Shortest path from 0 to 29: Edges = 230   Distance = 25.1470488312715
Shortest path from 0 to 30: Edges = 229   Distance = 25.249641895234
Shortest path from 0 to 31: Edges = 374   Distance = 31.2457734131495
Shortest path from 0 to 32: Edges = 207   Distance = 18.9107195764928
Shortest path from 0 to 33: Edges = 208   Distance = 18.9195743423705
Shortest path from 0 to 34: Edges = 206   Distance = 18.8739869214042
Shortest path from 0 to 35: Edges = 210   Distance = 18.6878648595076

Dead Ends PRESENT

Shortest path from 0 to 1: Edges = 227   Distance = 19.0100456527529
Shortest path from 0 to 2:   No Path
Shortest path from 0 to 3: Edges = 261   Distance = 26.5644314427133
Shortest path from 0 to 4: Edges = 314   Distance = 31.6082941722276
Shortest path from 0 to 5: Edges = 313   Distance = 31.6075873054928
Shortest path from 0 to 6: Edges = 314   Distance = 31.6132938428079
Shortest path from 0 to 7: Edges = 318   Distance = 31.7467679565931
Shortest path from 0 to 8: Edges = 316   Distance = 31.4259928797893
Shortest path from 0 to 9: Edges = 315   Distance = 31.3786656783543
Shortest path from 0 to 10: Edges = 316   Distance = 31.3790951118068
Shortest path from 0 to 11: Edges = 314   Distance = 31.3868351149137
Shortest path from 0 to 12: Edges = 309   Distance = 31.3725565559218
Shortest path from 0 to 13: Edges = 308   Distance = 31.3672739876087
Shortest path from 0 to 14: Edges = 307   Distance = 31.3652666879187
Shortest path from 0 to 15: Edges = 306   Distance = 31.3612395408569
Shortest path from 0 to 16: Edges = 305   Distance = 31.3511313614745
Shortest path from 0 to 17: Edges = 305   Distance = 31.3507770247126
Shortest path from 0 to 18: Edges = 304   Distance = 31.3449197391847
Shortest path from 0 to 19: Edges = 305   Distance = 31.3507382836556
Shortest path from 0 to 20: Edges = 306   Distance = 31.3567714394308
Shortest path from 0 to 21: Edges = 317   Distance = 31.6386417573992
Shortest path from 0 to 22: Edges = 313   Distance = 31.3841507102338
Shortest path from 0 to 23: Edges = 310   Distance = 31.3780404643515
Shortest path from 0 to 24: Edges = 316   Distance = 31.6201014628878
Shortest path from 0 to 25: Edges = 315   Distance = 31.6191466713011
Shortest path from 0 to 26: Edges = 311   Distance = 31.379343534659
Shortest path from 0 to 27: Edges = 312   Distance = 31.3805173655403
Shortest path from 0 to 28: Edges = 262   Distance = 26.6770720690091
Shortest path from 0 to 29: Edges = 262   Distance = 26.5693821541298
Shortest path from 0 to 30: Edges = 261   Distance = 26.6719752180924
Shortest path from 0 to 31: Edges = 341   Distance = 14.0733716554419
Shortest path from 0 to 32: Edges = 206   Distance = 20.449694441428
Shortest path from 0 to 33: Edges = 207   Distance = 20.4585492073057
Shortest path from 0 to 34: Edges = 205   Distance = 20.4129617863394
Shortest path from 0 to 35: Edges = 228   Distance = 19.0108079356457

CP-12237: K-th Shortest path

From unknown CodePlex user on Sunday, 28 December 2008 12:29:00

Is there any plan for this algorithm?

Thanks.

CP-11565: RootedAlgorithmBase.OnRooVertexChanged has a typo..

From unknown CodePlex user on Wednesday, 05 November 2008 20:55:57

RootedAlgorithmBase.OnRooVertexChanged has a typo..

CP-12726: Wrong documentation

From unknown CodePlex user on Monday, 02 March 2009 02:52:33

In release 31880 there is wrong description of parameters of method

QuickGraph.Serialization.SerializationExtensions. DeserializeFromXml<TVertex, TEdge, TGraph>(
            XmlReader reader,
            Predicate<XmlReader> graphPredicate,
            Predicate<XmlReader> vertexPredicate,
            Predicate<XmlReader> edgePredicate,
            Func<XmlReader, TGraph> graphFactory,
            Func<XmlReader, TVertex> vertexFactory,
            Func<XmlReader, TEdge> edgeFactory
            )
            where TGraph : class, IMutableVertexAndEdgeSet<TVertex, TEdge>
            where TEdge : IEdge<TVertex>

CP-11586: Build 24003 has some problems...

From unknown CodePlex user on Saturday, 08 November 2008 23:31:44

Sample Code:
For Each Vertex As PointVertexType In Graph.Vertices 'Iterate Graph
Select Case Graph.AdjacentEdges(Vertex).Count
Case 1 ' dead end
Case 2 ' line
Case Is >= 3 : Vertex.IsIntersection = True
End Select
Next

2nd lines fails with:
System.TypeLoadException occurred
Message="GenericArguments[1], 'TVertex', on 'QuickGraph.IGraph2[TVertex,TEdge]' violates the constraint of type parameter 'TEdge'." Source="QuickGraph" TypeName="" StackTrace: at QuickGraph.UndirectedGraph2.AdjacentEdges(TVertex v)
at TigerViewer.DeadEndProcessor.Process(Object State) in C:\Projects\Rt1Viewer\DeadEnds.vb:line 97
InnerException:

CP-12417: Support GraphML <default> Directive for User-defined Keys

From unknown CodePlex user on Tuesday, 20 January 2009 13:31:16

Consider the following graph.

<graph id="G" edgedefault="directed">
<node id="0">
<data key="isSpecial">true</data>
<data key="isSuperSpecial">true</data>
</node>
<node id="1">
<data key="isSuperSpecial">true</data>
</node>
<node id="2"/>
</graph>

It is currently not possible to create an IdentifiableVertex class that allows for optional use of the isSpecial and isSuperSpecial keys. We need a "DefaultAttribute" to decorate the corresponding IsSpecial and IsSuperSpecial properties so that deserialization will render the correct values when the keys are missing in the XML.

See #39 for more information.

CP-12471: Undirected Graph shortest path problem

From unknown CodePlex user on Monday, 26 January 2009 07:13:22

Hi,
i have this sample code:

var ug = new UndirectedGraph<object, Edge<object>>(true);
object v1 = "vertex1";
object v2 = "vertex2";
object v3 = "vertex3";
Edge<object> e1 = new Edge<object>(v1, v2);
Edge<object> e2 = new Edge<object>(v2, v3);
Edge<object> e3 = new Edge<object>(v3, v1);
ug.AddVertex(v1);
ug.AddVertex(v2);
ug.AddVertex(v3);
ug.AddEdge(e1);
ug.AddEdge(e2);
ug.AddEdge(e3);

var udspa = new QuickGraph.Algorithms.ShortestPath.UndirectedDijkstraShortestPathAlgorithm<object, QuickGraph.Edge<object>>(ug, edge => (double)1);
var observer = new QuickGraph.Algorithms.Observers.UndirectedVertexPredecessorRecorderObserver<object, Edge<object>>();
observer.Attach(udspa); 
udspa.Compute(v1);
IEnumerable<QuickGraph.Edge<object>> path;
observer.TryGetPath(v3, out path);

and i get out of memory exception. what am i doing wrong?

tnx,
Alfred.

CP-12288: K-Shortest paths - Hoffman Pavley

From unknown CodePlex user on Monday, 05 January 2009 23:18:23

Ok, sorry.

I've seen the extension method (To bidirectional) with the new changeset.Thanks!

I've a problem. Executing the code below, it returns always (KeyNotFoundException) Error: key not found in the dictionary:

            IBidirectionalGraph<int, Edge<int>> g1 = g.ToBidirectionalGraph();
 
            int Source = 1;
            int Target = 33;
 
            int pathCount = 5;
 
            foreach (IEnumerable<Edge<int>> path in g1.RankedShortestPathHoffmanPavley(E=> 5, Source, Target, pathCount))
            {
            }

Attached my serialized adjacency graph

Bye.

TestGraph.zip

AdjacencyGraph.zip

CP-12270: Make input parameter of StronglyConnectedComponents as Out

From unknown CodePlex user on Thursday, 01 January 2009 10:20:21

I would prefer

IDictionary<int, int> com;
var comp = testGraph.StronglyConnectedComponents(out com);

instead of this currently,

var com = new Dictionary<int, int>();
 var comp = testGraph.StronglyConnectedComponents(com);

Similar to how ShortestPathsBellmanFord works

CP-11128: TopologicalSort KeyNotFoundException

From unknown CodePlex user on Friday, 29 August 2008 05:58:19

// QuickGraph Version 2.0.30826.0

var graph = new AdjacencyGraph<int, Edge>();
graph.AddVertex(1);
graph.AddVertex(2);
graph.AddEdge(new Edge(1, 2));
var t = new TopologicalSortAlgorithm<int, Edge>(graph);
t.Compute();

System.Collections.Generic.KeyNotFoundException was unhandled
Message="The given key was not present in the dictionary."
Source="mscorlib"
StackTrace:
at System.ThrowHelper.ThrowKeyNotFoundException()
at System.Collections.Generic.Dictionary2.get_Item(TKey key) at QuickGraph.AdjacencyGraph2.OutEdges(TVertex v)
at QuickGraph.Algorithms.Search.DepthFirstSearchAlgorithm2.Visit(TVertex root, Int32 depth) at QuickGraph.Algorithms.Search.DepthFirstSearchAlgorithm2.InternalCompute()
at QuickGraph.Algorithms.AlgorithmBase1.Compute() at QuickGraph.Algorithms.TopologicalSortAlgorithm2.InternalCompute()
at QuickGraph.Algorithms.AlgorithmBase`1.Compute()

CP-12603: UndirectedGraph<string, Edge<string>>.RemoveVertex bug?

From unknown CodePlex user on Friday, 13 February 2009 17:03:50

I can't make this to run:

            UndirectedGraph<string, Edge<string>> graph = new UndirectedGraph<string, Edge<string>>();
            graph.AddVerticesAndEdge(new Edge<string>("aaaa", "bbbb"));
            graph.AddVerticesAndEdge(new Edge<string>("aaaa", "cccc"));
            graph.AddVerticesAndEdge(new Edge<string>("bbbb", "cccc"));
            graph.AddVerticesAndEdge(new Edge<string>("dddd", "bbbb"));
            graph.AddVerticesAndEdge(new Edge<string>("bbbb", "eeee"));
            graph.RemoveVertex("bbbb");

is this really a bug?

CP-11928: Search Algorithms with Heuristics

From unknown CodePlex user on Sunday, 07 December 2008 19:48:28

It would be nice to see the search algorithms (DFS, BFS, etc...) support a user-defined heuristic function for selecting the next node(s) to visit. Currently, the DFS and BFS algorithms use the implicit Vertex.OutEdges ordering.

The heuristic function prototype could be Func<TVertex, IEnumerable>, or something more appropriate. In this case TVertex is the vertex type and would be the vertex from which the candidate traversals are selected. IEnumerable is the resulting list of edges.

CP-6232: KeyNotFoundException

From unknown CodePlex user on Sunday, 09 September 2007 01:45:09

Some of my graphs cause a KeyNotFoundEception when trying to transform it into a gleegraph. Here is the code:

I start constructing an {{AdjacencyGraph}} followed by some lines to add vertices and edges:
{{
AdjacencyGraph<string, Edge> graph = new AdjacencyGraph<string, Edge>();
graph.AddVertex("someString1");
graph.AddVertex("someString2");
graph.AddEdge("someString1","someString2"));
}}

This code is highly simplyfied because my graphs are construced out of an XML tree and have about 20-30 vertices depending on the XML.
In the next step i generate the glee graph:
{{
GleeGraphPopulator<string, Edge> populator = GleeGraphUtility.Create<string, Edge>(graph);
populator.Compute();
Graph gleeGraph = populator.GleeGraph;
}}

But as said with some graphs already in the line {{populator.Compute();}} i get the following exception:
{{
System.Collections.Generic.KeyNotFoundException was unhandled
Message="Der angegebene Schlüssel war nicht im Wörterbuch angegeben."
Source="mscorlib"
StackTrace:
bei System.ThrowHelper.ThrowKeyNotFoundException()
bei System.Collections.Generic.Dictionary2.get_Item(TKey key) bei QuickGraph.Glee.GleeDefaultGraphPopulator2.AddEdge(Edge e)
bei QuickGraph.Glee.GleeGraphPopulator2.InternalCompute() bei QuickGraph.Algorithms.AlgorithmBase1.Compute()
....
}}

If it wuld be helpful i could try to output my vertices and edges to a textfile.

fubardevelopment / quickgraph Goto Github PK

quickgraph's People

Contributors

Stargazers

Watchers

Forkers

quickgraph's Issues

Deads Ends REMOVED

Dead Ends PRESENT

The Graph ‘Example 1’

Progam

Output

Results

Deads Ends REMOVED

Dead Ends PRESENT

// QuickGraph Version 2.0.30826.0 var graph = new AdjacencyGraph<int, Edge>(); graph.AddVertex(1); graph.AddVertex(2); graph.AddEdge(new Edge(1, 2)); var t = new TopologicalSortAlgorithm<int, Edge>(graph); t.Compute();

Recommend Projects

Recommend Topics

Recommend Org

// QuickGraph Version 2.0.30826.0

var graph = new AdjacencyGraph<int, Edge>();
graph.AddVertex(1);
graph.AddVertex(2);
graph.AddEdge(new Edge(1, 2));
var t = new TopologicalSortAlgorithm<int, Edge>(graph);
t.Compute();