BindingGraph.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataWeb / Client / System / Data / Services / Client / Binding / BindingGraph.cs / 1625574 / BindingGraph.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
//  
//   BindingGraph class
//  
// 
//---------------------------------------------------------------------
 
namespace System.Data.Services.Client
{
    #region Namespaces
    using System.Collections; 
    using System.Collections.Generic;
    using System.Collections.Specialized; 
    using System.ComponentModel; 
    using System.Diagnostics;
    using System.Linq; 
    using System.Reflection;
    #endregion

    ///  
    /// Color of each vertex to be used for Depth First Search
    ///  
    internal enum VertexColor 
    {
        /// White color means un-visited 
        White,

        /// Gray color means added to queue for DFS
        Gray, 

        /// Black color means already visited hence reachable from root 
        Black 
    }
 
    /// 
    /// The BindingGraph maps objects tracked by the DataServiceContext to vertices in a
    /// graph used to manage the information needed for data binding. The objects tracked
    /// by the BindingGraph are entity type objects and observable entity collections. 
    /// 
    internal sealed class BindingGraph 
    { 
        /// The observer of the graph
        private BindingObserver observer; 

        /// Graph containing entities, collections and their relationships
        private Graph graph;
 
        /// Constructor
        /// Observer of the graph 
        public BindingGraph(BindingObserver observer) 
        {
            this.observer = observer; 
            this.graph = new Graph();
        }

        /// Adds a collection to the graph 
        /// Source object for the collection, this object has navigation property corresponding to collection
        /// Property in  that corresponds to the collection 
        /// Collection being added 
        /// Entity set of entities in the collection
        /// true if a new vertex had to be created, false if it already exists 
        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining | System.Runtime.CompilerServices.MethodImplOptions.NoOptimization)]
        public bool AddCollection(
            object source,
            string sourceProperty, 
            object collection,
            string collectionEntitySet) 
        { 
            Debug.Assert(collection != null, "'collection' can not be null");
            Debug.Assert( 
                BindingEntityInfo.IsDataServiceCollection(collection.GetType()),
                "Argument 'collection' must be an DataServiceCollection of entity type T");

            if (this.graph.ExistsVertex(collection)) 
            {
                return false; 
            } 

            Vertex collectionVertex = this.graph.AddVertex(collection); 
            collectionVertex.IsCollection = true;
            collectionVertex.EntitySet = collectionEntitySet;

            ICollection collectionItf = collection as ICollection; 

            if (source != null) 
            { 
                collectionVertex.Parent = this.graph.LookupVertex(source);
                collectionVertex.ParentProperty = sourceProperty; 
                this.graph.AddEdge(source, collection, sourceProperty);

                // Update the observer on the child collection
                Type entityType = BindingUtils.GetCollectionEntityType(collection.GetType()); 
                Debug.Assert(entityType != null, "Collection must at least be inherited from DataServiceCollection");
 
                // Fail if the collection entity type does not implement INotifyPropertyChanged. 
                if (!typeof(INotifyPropertyChanged).IsAssignableFrom(entityType))
                { 
                    throw new InvalidOperationException(Strings.DataBinding_NotifyPropertyChangedNotImpl(entityType));
                }

                typeof(BindingGraph) 
                    .GetMethod("SetObserver", BindingFlags.Instance | BindingFlags.NonPublic)
                    .MakeGenericMethod(entityType) 
                    .Invoke(this, new object[] { collectionItf }); 
            }
            else 
            {
                // When there is no source, then this vertex is the root vertex
                this.graph.Root = collectionVertex;
            } 

            Debug.Assert( 
                    collectionVertex.Parent != null || collectionVertex.IsRootCollection, 
                    "If parent is null, then collectionVertex should be a root collection");
 
            // Register for collection notifications
            this.AttachCollectionNotification(collection);

            // Perform deep add, by recursively adding entities in the collection 
            foreach (var item in collectionItf)
            { 
                this.AddEntity( 
                        source,
                        sourceProperty, 
                        item,
                        collectionEntitySet,
                        collection);
            } 

            return true; 
        } 

        /// Adds an entity to the graph 
        /// Source object for the entity, this object has navigation property that links to entity
        /// Property in  that links to entity
        /// Entity being added
        /// Entity set of entity being added 
        /// Item from which the directed edge in the graph goes into . This can be a collection
        /// true if a new vertex had to be created, false if it already exists 
        ///  
        /// This method processes the current 'target' entity and then recursively moves into the graph through
        /// the navigation properties. The 'source' is a previously processed item - it is the 'parent' 
        /// of the target entity.
        /// The code generated EntitySetAttribute is processed by this method.
        /// A source entity can reference the target entity directly through an entity reference navigation property,
        /// or indirectly through a collection navigation property. 
        /// 
        public bool AddEntity( 
            object source, 
            string sourceProperty,
            object target, 
            string targetEntitySet,
            object edgeSource)
        {
            Vertex sourceVertex = this.graph.LookupVertex(edgeSource); 
            Debug.Assert(sourceVertex != null, "Must have a valid edge source");
 
            Vertex entityVertex = null; 
            bool addedNewEntity = false;
 
            if (target != null)
            {
                entityVertex = this.graph.LookupVertex(target);
 
                if (entityVertex == null)
                { 
                    entityVertex = this.graph.AddVertex(target); 

                    entityVertex.EntitySet = BindingEntityInfo.GetEntitySet(target, targetEntitySet); 

                    // Register for entity notifications, fail if the entity does not implement INotifyPropertyChanged.
                    if (!this.AttachEntityOrComplexObjectNotification(target))
                    { 
                        throw new InvalidOperationException(Strings.DataBinding_NotifyPropertyChangedNotImpl(target.GetType()));
                    } 
 
                    addedNewEntity = true;
                } 

                // Add relationship. Connect the from end to the target.
                if (this.graph.ExistsEdge(edgeSource, target, sourceVertex.IsCollection ? null : sourceProperty))
                { 
                    throw new InvalidOperationException(Strings.DataBinding_EntityAlreadyInCollection(target.GetType()));
                } 
 
                this.graph.AddEdge(edgeSource, target, sourceVertex.IsCollection ? null : sourceProperty);
            } 

            if (!sourceVertex.IsCollection)
            {
                this.observer.HandleUpdateEntityReference( 
                        source,
                        sourceProperty, 
                        sourceVertex.EntitySet, 
                        target,
                        entityVertex == null ? null : entityVertex.EntitySet); 
            }
            else
            {
                Debug.Assert(target != null, "Target must be non-null when adding to collections"); 
                this.observer.HandleAddEntity(
                        source, 
                        sourceProperty, 
                        sourceVertex.Parent != null ? sourceVertex.Parent.EntitySet : null,
                        edgeSource as ICollection, 
                        target,
                        entityVertex.EntitySet);
            }
 
            if (addedNewEntity)
            { 
                // Perform recursive add operation through target's properties 
                this.AddFromProperties(target);
            } 

            return addedNewEntity;
        }
 
        /// 
        /// Removes the  from the binding graph 
        ///  
        /// Item to remove
        /// Parent of the  
        /// Parent property that refers to 
        public void Remove(object item, object parent, string parentProperty)
        {
            Vertex vertexToRemove = this.graph.LookupVertex(item); 
            if (vertexToRemove == null)
            { 
                return; 
            }
 
            Debug.Assert(!vertexToRemove.IsRootCollection, "Root collections are never removed");

            // Parent will always be non-null for deletes from collections, this will include
            // both root and child collections. For root collections, parentProperty will be null. 
            Debug.Assert(parent != null, "Parent has to be present.");
 
            // When parentProperty is null, parent is itself a root collection 
            if (parentProperty != null)
            { 
                BindingEntityInfo.BindingPropertyInfo bpi = BindingEntityInfo.GetObservableProperties(parent.GetType())
                                                                             .Single(p => p.PropertyInfo.PropertyName == parentProperty);
                Debug.Assert(bpi.PropertyKind == BindingPropertyKind.BindingPropertyKindCollection, "parentProperty must refer to an DataServiceCollection");
 
                parent = bpi.PropertyInfo.GetValue(parent);
            } 
 
            object source = null;
            string sourceProperty = null; 
            string sourceEntitySet = null;
            string targetEntitySet = null;

            this.GetEntityCollectionInfo( 
                    parent,
                    out source, 
                    out sourceProperty, 
                    out sourceEntitySet,
                    out targetEntitySet); 

            targetEntitySet = BindingEntityInfo.GetEntitySet(item, targetEntitySet);

            this.observer.HandleDeleteEntity( 
                            source,
                            sourceProperty, 
                            sourceEntitySet, 
                            parent as ICollection,
                            item, 
                            targetEntitySet);

            this.graph.RemoveEdge(parent, item, null);
        } 

        /// Removes the collection from the graph 
        /// Collection to remove 
        public void RemoveCollection(object collection)
        { 
            Vertex collectionVertex = this.graph.LookupVertex(collection);
            Debug.Assert(collectionVertex != null, "Must be tracking the vertex for the collection");

            foreach (Edge collectionEdge in collectionVertex.OutgoingEdges.ToList()) 
            {
                this.graph.RemoveEdge(collection, collectionEdge.Target.Item, null); 
            } 

            // This is where actual removal from graph happens, detach notifications for removed object 
            this.RemoveUnreachableVertices();
        }

        /// Removes a relationship between two items based on source and relation label 
        /// Source item
        /// Label for relation 
        public void RemoveRelation(object source, string relation) 
        {
            Edge edge = this.graph 
                            .LookupVertex(source)
                            .OutgoingEdges
                            .SingleOrDefault(e => e.Source.Item == source && e.Label == relation);
            if (edge != null) 
            {
                this.graph.RemoveEdge(edge.Source.Item, edge.Target.Item, edge.Label); 
            } 

            // This is where actual removal from graph happens, detach notifications for removed object 
            this.RemoveUnreachableVertices();
        }

#if DEBUG 
        /// Checks to see if an object is being tracked by the graph
        /// Object being checked 
        /// true if the object exists in the graph, false otherwise 
        public bool IsTracking(object item)
        { 
            return this.graph.ExistsVertex(item);
        }
#endif
        /// Remove all non-tracked entities from the graph 
        public void RemoveNonTrackedEntities()
        { 
            // Cleanup all untracked entities 
            foreach (var entity in this.graph.Select(o => BindingEntityInfo.IsEntityType(o.GetType()) && !this.observer.IsContextTrackingEntity(o)))
            { 
                this.graph.ClearEdgesForVertex(this.graph.LookupVertex(entity));
            }

            this.RemoveUnreachableVertices(); 
        }
 
        ///  
        /// Returns a sequence of items belonging to a collection. Uses the children of a collection
        /// vertex for this enumeration. 
        /// 
        /// Collection being enumerated.
        /// Sequence of items belonging to the collection.
        public IEnumerable GetCollectionItems(object collection) 
        {
            Vertex collectionVertex = this.graph.LookupVertex(collection); 
            Debug.Assert(collectionVertex != null, "Must be tracking the vertex for the collection"); 
            foreach (Edge collectionEdge in collectionVertex.OutgoingEdges.ToList())
            { 
                yield return collectionEdge.Target.Item;
            }
        }
 
        /// Reset the graph after detaching notifications for everything
        public void Reset() 
        { 
            this.graph.Reset(this.DetachNotifications);
        } 

        /// Removes the un-reachable vertices from the graph and un-registers notification handlers
        public void RemoveUnreachableVertices()
        { 
            // This is where actual removal from graph happens, detach notifications for removed object
            this.graph.RemoveUnreachableVertices(this.DetachNotifications); 
        } 

        /// Get the binding information for a collection 
        /// Collection
        /// The source object that reference the target object through a navigation property.
        /// The navigation property in the source object that reference the target object.
        /// The entity set of the source object. 
        /// The entity set name of the target object.
        public void GetEntityCollectionInfo( 
            object collection, 
            out object source,
            out string sourceProperty, 
            out string sourceEntitySet,
            out string targetEntitySet)
        {
            Debug.Assert(collection != null, "Argument 'collection' cannot be null."); 
            Debug.Assert(this.graph.ExistsVertex(collection), "Vertex corresponding to 'collection' must exist in the graph.");
 
            this.graph 
                .LookupVertex(collection)
                .GetEntityCollectionInfo( 
                    out source,
                    out sourceProperty,
                    out sourceEntitySet,
                    out targetEntitySet); 
        }
 
        ///  
        /// Obtains the closest ancestor entity type in the graph corresponding to a complex object vertex.
        ///  
        /// On input this is a complex object, on output it is the closest entity ancestor.
        /// On input this is a complex object's member property name, on output it is the name of complex type property of the ancestor.
        /// On input this is a complex object's member property value, on output it is the value of complex type property of the ancestor.
        public void GetAncestorEntityForComplexProperty( 
            ref object entity,
            ref string propertyName, 
            ref object propertyValue) 
        {
            Vertex childVertex = this.graph.LookupVertex(entity); 
            Debug.Assert(childVertex != null, "Must have a vertex in the graph corresponding to the entity.");
            Debug.Assert(childVertex.IsComplex == true, "Vertex must correspond to a complex object.");

            while (childVertex.IsComplex) 
            {
                propertyName = childVertex.IncomingEdges[0].Label; 
                propertyValue = childVertex.Item; 

                Debug.Assert(childVertex.Parent != null, "Complex properties must always have parent vertices."); 
                entity = childVertex.Parent.Item;

                childVertex = childVertex.Parent;
            } 
        }
 
        ///  
        /// Adds a complex typed property to the graph for an object, also traverses all the child complex properties and adds them.
        ///  
        /// Source entity object.
        /// Source entity property of complex type.
        /// Target complex object property value.
        public void AddComplexProperty(object source, string sourceProperty, object target) 
        {
            Vertex parentVertex = this.graph.LookupVertex(source); 
            Debug.Assert(parentVertex != null, "Must have a valid parent entity for complex properties."); 
            Debug.Assert(target != null, "Must have non-null complex object reference.");
 
            Vertex complexVertex = this.graph.LookupVertex(target);

            if (complexVertex == null)
            { 
                complexVertex = this.graph.AddVertex(target);
                complexVertex.Parent = parentVertex; 
                complexVertex.IsComplex = true; 

                // Register for complex type notifications, fail if the complex type does not implement INotifyPropertyChanged. 
                if (!this.AttachEntityOrComplexObjectNotification(target))
                {
                    throw new InvalidOperationException(Strings.DataBinding_NotifyPropertyChangedNotImpl(target.GetType()));
                } 
            }
            else 
            { 
                throw new InvalidOperationException(Strings.DataBinding_ComplexObjectAssociatedWithMultipleEntities(target.GetType()));
            } 

            this.graph.AddEdge(source, target, sourceProperty);

            // Add nested properties for the complex object. 
            this.AddFromProperties(target);
        } 
 
        /// Add items to the graph, from the  object's properties
        /// Object whose properties are to be explored 
        private void AddFromProperties(object entity)
        {
            // Once the entity is attached to the graph, we need to traverse all it's properties
            // and add related entities and collections to this entity. 
            foreach (BindingEntityInfo.BindingPropertyInfo bpi in BindingEntityInfo.GetObservableProperties(entity.GetType()))
            { 
                object propertyValue = bpi.PropertyInfo.GetValue(entity); 

                if (propertyValue != null) 
                {
                    switch (bpi.PropertyKind)
                    {
                        case BindingPropertyKind.BindingPropertyKindCollection: 
                            this.AddCollection(
                                    entity, 
                                    bpi.PropertyInfo.PropertyName, 
                                    propertyValue,
                                    null); 

                            break;

                        case BindingPropertyKind.BindingPropertyKindEntity: 
                            this.AddEntity(
                                    entity, 
                                    bpi.PropertyInfo.PropertyName, 
                                    propertyValue,
                                    null, 
                                    entity);

                            break;
 
                        default:
                            Debug.Assert(bpi.PropertyKind == BindingPropertyKind.BindingPropertyKindComplex, "Must be complex type if PropertyKind is not entity or collection."); 
                            this.AddComplexProperty( 
                                    entity,
                                    bpi.PropertyInfo.PropertyName, 
                                    propertyValue);
                            break;
                    }
                } 
            }
        } 
 
        /// Attach the CollectionChanged handler to an DataServiceCollection.
        /// An DataServiceCollection. 
        private void AttachCollectionNotification(object target)
        {
            Debug.Assert(target != null, "Argument 'target' cannot be null");
 
            INotifyCollectionChanged notify = target as INotifyCollectionChanged;
            Debug.Assert(notify != null, "DataServiceCollection must implement INotifyCollectionChanged"); 
 
            notify.CollectionChanged -= this.observer.OnCollectionChanged;
            notify.CollectionChanged += this.observer.OnCollectionChanged; 
        }

        /// Attach the PropertyChanged handler to an entity or complex object.
        /// An entity or complex object. 
        /// True if the target is attached; otherwise false.
        private bool AttachEntityOrComplexObjectNotification(object target) 
        { 
            Debug.Assert(target != null, "Argument 'target' cannot be null");
 
            INotifyPropertyChanged notify = target as INotifyPropertyChanged;
            if (notify != null)
            {
                notify.PropertyChanged -= this.observer.OnPropertyChanged; 
                notify.PropertyChanged += this.observer.OnPropertyChanged;
                return true; 
            } 

            return false; 
        }

        /// Detach CollectionChanged or PropertyChanged handlers from the target
        /// An entity object or collection 
        private void DetachNotifications(object target)
        { 
            Debug.Assert(target != null, "Argument 'target' cannot be null"); 

            this.DetachCollectionNotifications(target); 

            INotifyPropertyChanged notifyPropertyChanged = target as INotifyPropertyChanged;
            if (notifyPropertyChanged != null)
            { 
                notifyPropertyChanged.PropertyChanged -= this.observer.OnPropertyChanged;
            } 
        } 

        /// Detach CollectionChanged handlers from the target 
        /// A collection object
        private void DetachCollectionNotifications(object target)
        {
            Debug.Assert(target != null, "Argument 'target' cannot be null"); 

            INotifyCollectionChanged notifyCollectionChanged = target as INotifyCollectionChanged; 
            if (notifyCollectionChanged != null) 
            {
                notifyCollectionChanged.CollectionChanged -= this.observer.OnCollectionChanged; 
            }
        }

        ///  
        /// Sets the observer for a child DataServiceCollection
        ///  
        /// Entity type for the collection 
        /// Non-typed collection interface
        private void SetObserver(ICollection collection) 
        {
            DataServiceCollection oec = collection as DataServiceCollection;
            oec.Observer = this.observer;
        } 

        /// Graph implementation for tracking entities, collections for binding 
        internal sealed class Graph 
        {
            /// Vertices of the graph, which also hold edges 
            private Dictionary vertices;

            /// The root vertex for the graph, DFS traversals start from this vertex
            private Vertex root; 

            /// Constructor 
            public Graph() 
            {
                this.vertices = new Dictionary(ReferenceEqualityComparer.Instance); 
            }

            /// Root vertex of the graph
            public Vertex Root 
            {
                get 
                { 
                    Debug.Assert(this.root != null, "Must have a non-null root vertex when this call is made.");
                    return this.root; 
                }

                set
                { 
                    Debug.Assert(this.root == null, "Must only initialize root vertex once.");
                    Debug.Assert(this.ExistsVertex(value.Item), "Must already have the assigned vertex in the graph."); 
                    this.root = value; 
                }
            } 

            /// Adds vertex to the graph
            /// Item corresponding to vertex
            /// Newly created vertex 
            public Vertex AddVertex(object item)
            { 
                Vertex v = new Vertex(item); 
                this.vertices.Add(item, v);
                return v; 
            }

            /// Removes all edges going out of and coming into the given vertex
            /// Vertex whose edges are to be cleared 
            public void ClearEdgesForVertex(Vertex v)
            { 
                foreach (Edge e in v.OutgoingEdges.Concat(v.IncomingEdges).ToList()) 
                {
                    this.RemoveEdge(e.Source.Item, e.Target.Item, e.Label); 
                }
            }

            ///  
            /// Checks if a vertex exists corresponding to given 
            ///  
            /// Item to lookup 
            /// true if vertex found, false otherwise
            public bool ExistsVertex(object item) 
            {
                Vertex v;
                return this.vertices.TryGetValue(item, out v);
            } 

            /// Looksup the vertex corresponding to  
            /// Item to lookup 
            /// Vertex corresponding to item
            public Vertex LookupVertex(object item) 
            {
                Vertex v;
                this.vertices.TryGetValue(item, out v);
                return v; 
            }
 
            ///  
            /// Adds edge between vertices corresponding to  and 
            /// objects which will be labeled with  
            /// 
            /// Outgoing end of the edge
            /// Incoming end of the edge
            /// Label for the vertex 
            /// Newly created edge
            public Edge AddEdge(object source, object target, string label) 
            { 
                Vertex s = this.vertices[source];
                Vertex t = this.vertices[target]; 
                Edge e = new Edge { Source = s, Target = t, Label = label };
                s.OutgoingEdges.Add(e);
                t.IncomingEdges.Add(e);
                return e; 
            }
 
            ///  
            /// Removes edge between vertices corresponding to  and 
            /// objects which was labeled with  
            /// 
            /// Outgoing end of the edge
            /// Incoming end of the edge
            /// Label for the vertex 
            public void RemoveEdge(object source, object target, string label)
            { 
                Vertex s = this.vertices[source]; 
                Vertex t = this.vertices[target];
                Edge e = new Edge { Source = s, Target = t, Label = label }; 
                s.OutgoingEdges.Remove(e);
                t.IncomingEdges.Remove(e);
            }
 
            /// 
            /// Checks if an edge exists between  and  labeled 
            /// with  
            /// 
            /// Outgoing end of the edge 
            /// Incoming end of the edge
            /// Label for the vertex
            /// true if an edge exists between source and target with given label, false otherwise
            public bool ExistsEdge(object source, object target, string label) 
            {
                Edge e = new Edge { Source = this.vertices[source], Target = this.vertices[target], Label = label }; 
                return this.vertices[source].OutgoingEdges.Any(r => r.Equals(e)); 
            }
 
            /// 
            /// Selects collection of objects tracked by the graph based on the given filter
            /// 
            /// Filter for the objects 
            /// Filtered list of objects tracked by the graph
            public IList Select(Func filter) 
            { 
                return this.vertices.Keys.Where(filter).ToList();
            } 

            /// 
            /// Removes everything from the graph after applying 
            ///  
            /// Action to apply before removal of each node
            public void Reset(Action action) 
            { 
                foreach (object obj in this.vertices.Keys)
                { 
                    action(obj);
                }

                this.vertices.Clear(); 
            }
 
            /// Remove all vertices from graph that are unreachable from the root collection vertex 
            /// Action to perform for each removed vertex
            public void RemoveUnreachableVertices(Action detachAction) 
            {
                try
                {
                    foreach (Vertex v in this.UnreachableVertices()) 
                    {
                        this.ClearEdgesForVertex(v); 
                        detachAction(v.Item); 
                        this.vertices.Remove(v.Item);
                    } 
                }
                finally
                {
                    // Reset color for all vertices back to white. 
                    foreach (Vertex v in this.vertices.Values)
                    { 
                        v.Color = VertexColor.White; 
                    }
                } 
            }

            /// Collects all vertices unreachable from the root collection vertex
            /// Sequence of vertices that are unreachable from the root collection vertex 
            /// 
            /// Performs a depth first traversal of the graph starting from the root collection 
            /// vertex and checks if some vertices were unreachable was reached while doing the traversal. 
            /// Alogrithm from Introduction to Algorithms 22.2 by Cormen et al.
            ///  
            private IEnumerable UnreachableVertices()
            {
                Queue q = new Queue();
 
                this.Root.Color = VertexColor.Gray;
                q.Enqueue(this.Root); 
 
                while (q.Count != 0)
                { 
                    Vertex current = q.Dequeue();

                    foreach (Edge e in current.OutgoingEdges)
                    { 
                        if (e.Target.Color == VertexColor.White)
                        { 
                            e.Target.Color = VertexColor.Gray; 
                            q.Enqueue(e.Target);
                        } 
                    }

                    current.Color = VertexColor.Black;
                } 

                return this.vertices.Values.Where(v => v.Color == VertexColor.White).ToList(); 
            } 
        }
 
        /// Vertex of the 
        internal sealed class Vertex
        {
            /// Collection of incoming edges for the vertex 
            private List incomingEdges;
 
            /// Collection of outgoing edges for the vertex 
            private List outgoingEdges;
 
            /// Constructor
            /// Item corresponding to vertex
            public Vertex(object item)
            { 
                Debug.Assert(item != null, "item must be non-null");
                this.Item = item; 
                this.Color = VertexColor.White; 
            }
 
            /// Item corresponding to the vertex
            public object Item
            {
                get; 
                private set;
            } 
 
            /// Entity set of the item held by the vertex
            public string EntitySet 
            {
                get;
                set;
            } 

            /// Is item a collection object 
            public bool IsCollection 
            {
                get; 
                set;
            }

            /// Is item a complex type object 
            public bool IsComplex
            { 
                get; 
                set;
            } 

            /// Parent vertex, only exists for non-top level collection vertices or complex objects
            public Vertex Parent
            { 
                get;
                set; 
            } 

            /// Property of the  object that associates this vertex with it's parent 
            public string ParentProperty
            {
                get;
                set; 
            }
 
            /// Is item a root collection object 
            public bool IsRootCollection
            { 
                get
                {
                    return this.IsCollection && this.Parent == null;
                } 
            }
 
            /// Color of the vertex 
            public VertexColor Color
            { 
                get;
                set;
            }
 
            /// Edges coming into this vertex
            public IList IncomingEdges 
            { 
                get
                { 
                    if (this.incomingEdges == null)
                    {
                        this.incomingEdges = new List();
                    } 

                    return this.incomingEdges; 
                } 
            }
 
            /// Edges going out of this vertex
            public IList OutgoingEdges
            {
                get 
                {
                    if (this.outgoingEdges == null) 
                    { 
                        this.outgoingEdges = new List();
                    } 

                    return this.outgoingEdges;
                }
            } 

            /// Get the binding information for a collection vertex 
            /// The source object that reference the target object through a navigation property corresponding to current collection vertex. 
            /// The navigation property in the source object that reference the target object.
            /// The entity set of the source object. 
            /// The entity set of the target object.
            public void GetEntityCollectionInfo(
                out object source,
                out string sourceProperty, 
                out string sourceEntitySet,
                out string targetEntitySet) 
            { 
                Debug.Assert(this.IsCollection, "Must be a collection to be in this method");
 
                if (!this.IsRootCollection)
                {
                    Debug.Assert(this.Parent != null, "Parent must be non-null for child collection");
 
                    source = this.Parent.Item;
                    Debug.Assert(source != null, "Source object must be present for child collection"); 
 
                    sourceProperty = this.ParentProperty;
                    Debug.Assert(sourceProperty != null, "Source entity property associated with a child collection must be non-null"); 

#if DEBUG
                    PropertyInfo propertyInfo = source.GetType().GetProperty(sourceProperty);
                    Debug.Assert(propertyInfo != null, "Unable to get information for the source entity property associated with a child collection"); 
#endif
                    sourceEntitySet = this.Parent.EntitySet; 
                } 
                else
                { 
                    Debug.Assert(this.Parent == null, "Parent must be null for top level collection");
                    source = null;
                    sourceProperty = null;
                    sourceEntitySet = null; 
                }
 
                targetEntitySet = this.EntitySet; 
            }
        } 

        /// 
        /// Edge between two vertices of graph, directed and labeled
        ///  
        internal sealed class Edge : IEquatable
        { 
            /// Source vertex 
            public Vertex Source
            { 
                get;
                set;
            }
 
            /// Target vertex
            public Vertex Target 
            { 
                get;
                set; 
            }

            /// Label of the edge
            public string Label 
            {
                get; 
                set; 
            }
 
            /// IEquatable override
            /// Comparand
            /// true if equal, false otherwise
            public bool Equals(Edge other) 
            {
                return other != null && 
                    Object.ReferenceEquals(this.Source, other.Source) && 
                    Object.ReferenceEquals(this.Target, other.Target) &&
                    this.Label == other.Label; 
            }
        }
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
//  
//   BindingGraph class
//  
// 
//---------------------------------------------------------------------
 
namespace System.Data.Services.Client
{
    #region Namespaces
    using System.Collections; 
    using System.Collections.Generic;
    using System.Collections.Specialized; 
    using System.ComponentModel; 
    using System.Diagnostics;
    using System.Linq; 
    using System.Reflection;
    #endregion

    ///  
    /// Color of each vertex to be used for Depth First Search
    ///  
    internal enum VertexColor 
    {
        /// White color means un-visited 
        White,

        /// Gray color means added to queue for DFS
        Gray, 

        /// Black color means already visited hence reachable from root 
        Black 
    }
 
    /// 
    /// The BindingGraph maps objects tracked by the DataServiceContext to vertices in a
    /// graph used to manage the information needed for data binding. The objects tracked
    /// by the BindingGraph are entity type objects and observable entity collections. 
    /// 
    internal sealed class BindingGraph 
    { 
        /// The observer of the graph
        private BindingObserver observer; 

        /// Graph containing entities, collections and their relationships
        private Graph graph;
 
        /// Constructor
        /// Observer of the graph 
        public BindingGraph(BindingObserver observer) 
        {
            this.observer = observer; 
            this.graph = new Graph();
        }

        /// Adds a collection to the graph 
        /// Source object for the collection, this object has navigation property corresponding to collection
        /// Property in  that corresponds to the collection 
        /// Collection being added 
        /// Entity set of entities in the collection
        /// true if a new vertex had to be created, false if it already exists 
        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining | System.Runtime.CompilerServices.MethodImplOptions.NoOptimization)]
        public bool AddCollection(
            object source,
            string sourceProperty, 
            object collection,
            string collectionEntitySet) 
        { 
            Debug.Assert(collection != null, "'collection' can not be null");
            Debug.Assert( 
                BindingEntityInfo.IsDataServiceCollection(collection.GetType()),
                "Argument 'collection' must be an DataServiceCollection of entity type T");

            if (this.graph.ExistsVertex(collection)) 
            {
                return false; 
            } 

            Vertex collectionVertex = this.graph.AddVertex(collection); 
            collectionVertex.IsCollection = true;
            collectionVertex.EntitySet = collectionEntitySet;

            ICollection collectionItf = collection as ICollection; 

            if (source != null) 
            { 
                collectionVertex.Parent = this.graph.LookupVertex(source);
                collectionVertex.ParentProperty = sourceProperty; 
                this.graph.AddEdge(source, collection, sourceProperty);

                // Update the observer on the child collection
                Type entityType = BindingUtils.GetCollectionEntityType(collection.GetType()); 
                Debug.Assert(entityType != null, "Collection must at least be inherited from DataServiceCollection");
 
                // Fail if the collection entity type does not implement INotifyPropertyChanged. 
                if (!typeof(INotifyPropertyChanged).IsAssignableFrom(entityType))
                { 
                    throw new InvalidOperationException(Strings.DataBinding_NotifyPropertyChangedNotImpl(entityType));
                }

                typeof(BindingGraph) 
                    .GetMethod("SetObserver", BindingFlags.Instance | BindingFlags.NonPublic)
                    .MakeGenericMethod(entityType) 
                    .Invoke(this, new object[] { collectionItf }); 
            }
            else 
            {
                // When there is no source, then this vertex is the root vertex
                this.graph.Root = collectionVertex;
            } 

            Debug.Assert( 
                    collectionVertex.Parent != null || collectionVertex.IsRootCollection, 
                    "If parent is null, then collectionVertex should be a root collection");
 
            // Register for collection notifications
            this.AttachCollectionNotification(collection);

            // Perform deep add, by recursively adding entities in the collection 
            foreach (var item in collectionItf)
            { 
                this.AddEntity( 
                        source,
                        sourceProperty, 
                        item,
                        collectionEntitySet,
                        collection);
            } 

            return true; 
        } 

        /// Adds an entity to the graph 
        /// Source object for the entity, this object has navigation property that links to entity
        /// Property in  that links to entity
        /// Entity being added
        /// Entity set of entity being added 
        /// Item from which the directed edge in the graph goes into . This can be a collection
        /// true if a new vertex had to be created, false if it already exists 
        ///  
        /// This method processes the current 'target' entity and then recursively moves into the graph through
        /// the navigation properties. The 'source' is a previously processed item - it is the 'parent' 
        /// of the target entity.
        /// The code generated EntitySetAttribute is processed by this method.
        /// A source entity can reference the target entity directly through an entity reference navigation property,
        /// or indirectly through a collection navigation property. 
        /// 
        public bool AddEntity( 
            object source, 
            string sourceProperty,
            object target, 
            string targetEntitySet,
            object edgeSource)
        {
            Vertex sourceVertex = this.graph.LookupVertex(edgeSource); 
            Debug.Assert(sourceVertex != null, "Must have a valid edge source");
 
            Vertex entityVertex = null; 
            bool addedNewEntity = false;
 
            if (target != null)
            {
                entityVertex = this.graph.LookupVertex(target);
 
                if (entityVertex == null)
                { 
                    entityVertex = this.graph.AddVertex(target); 

                    entityVertex.EntitySet = BindingEntityInfo.GetEntitySet(target, targetEntitySet); 

                    // Register for entity notifications, fail if the entity does not implement INotifyPropertyChanged.
                    if (!this.AttachEntityOrComplexObjectNotification(target))
                    { 
                        throw new InvalidOperationException(Strings.DataBinding_NotifyPropertyChangedNotImpl(target.GetType()));
                    } 
 
                    addedNewEntity = true;
                } 

                // Add relationship. Connect the from end to the target.
                if (this.graph.ExistsEdge(edgeSource, target, sourceVertex.IsCollection ? null : sourceProperty))
                { 
                    throw new InvalidOperationException(Strings.DataBinding_EntityAlreadyInCollection(target.GetType()));
                } 
 
                this.graph.AddEdge(edgeSource, target, sourceVertex.IsCollection ? null : sourceProperty);
            } 

            if (!sourceVertex.IsCollection)
            {
                this.observer.HandleUpdateEntityReference( 
                        source,
                        sourceProperty, 
                        sourceVertex.EntitySet, 
                        target,
                        entityVertex == null ? null : entityVertex.EntitySet); 
            }
            else
            {
                Debug.Assert(target != null, "Target must be non-null when adding to collections"); 
                this.observer.HandleAddEntity(
                        source, 
                        sourceProperty, 
                        sourceVertex.Parent != null ? sourceVertex.Parent.EntitySet : null,
                        edgeSource as ICollection, 
                        target,
                        entityVertex.EntitySet);
            }
 
            if (addedNewEntity)
            { 
                // Perform recursive add operation through target's properties 
                this.AddFromProperties(target);
            } 

            return addedNewEntity;
        }
 
        /// 
        /// Removes the  from the binding graph 
        ///  
        /// Item to remove
        /// Parent of the  
        /// Parent property that refers to 
        public void Remove(object item, object parent, string parentProperty)
        {
            Vertex vertexToRemove = this.graph.LookupVertex(item); 
            if (vertexToRemove == null)
            { 
                return; 
            }
 
            Debug.Assert(!vertexToRemove.IsRootCollection, "Root collections are never removed");

            // Parent will always be non-null for deletes from collections, this will include
            // both root and child collections. For root collections, parentProperty will be null. 
            Debug.Assert(parent != null, "Parent has to be present.");
 
            // When parentProperty is null, parent is itself a root collection 
            if (parentProperty != null)
            { 
                BindingEntityInfo.BindingPropertyInfo bpi = BindingEntityInfo.GetObservableProperties(parent.GetType())
                                                                             .Single(p => p.PropertyInfo.PropertyName == parentProperty);
                Debug.Assert(bpi.PropertyKind == BindingPropertyKind.BindingPropertyKindCollection, "parentProperty must refer to an DataServiceCollection");
 
                parent = bpi.PropertyInfo.GetValue(parent);
            } 
 
            object source = null;
            string sourceProperty = null; 
            string sourceEntitySet = null;
            string targetEntitySet = null;

            this.GetEntityCollectionInfo( 
                    parent,
                    out source, 
                    out sourceProperty, 
                    out sourceEntitySet,
                    out targetEntitySet); 

            targetEntitySet = BindingEntityInfo.GetEntitySet(item, targetEntitySet);

            this.observer.HandleDeleteEntity( 
                            source,
                            sourceProperty, 
                            sourceEntitySet, 
                            parent as ICollection,
                            item, 
                            targetEntitySet);

            this.graph.RemoveEdge(parent, item, null);
        } 

        /// Removes the collection from the graph 
        /// Collection to remove 
        public void RemoveCollection(object collection)
        { 
            Vertex collectionVertex = this.graph.LookupVertex(collection);
            Debug.Assert(collectionVertex != null, "Must be tracking the vertex for the collection");

            foreach (Edge collectionEdge in collectionVertex.OutgoingEdges.ToList()) 
            {
                this.graph.RemoveEdge(collection, collectionEdge.Target.Item, null); 
            } 

            // This is where actual removal from graph happens, detach notifications for removed object 
            this.RemoveUnreachableVertices();
        }

        /// Removes a relationship between two items based on source and relation label 
        /// Source item
        /// Label for relation 
        public void RemoveRelation(object source, string relation) 
        {
            Edge edge = this.graph 
                            .LookupVertex(source)
                            .OutgoingEdges
                            .SingleOrDefault(e => e.Source.Item == source && e.Label == relation);
            if (edge != null) 
            {
                this.graph.RemoveEdge(edge.Source.Item, edge.Target.Item, edge.Label); 
            } 

            // This is where actual removal from graph happens, detach notifications for removed object 
            this.RemoveUnreachableVertices();
        }

#if DEBUG 
        /// Checks to see if an object is being tracked by the graph
        /// Object being checked 
        /// true if the object exists in the graph, false otherwise 
        public bool IsTracking(object item)
        { 
            return this.graph.ExistsVertex(item);
        }
#endif
        /// Remove all non-tracked entities from the graph 
        public void RemoveNonTrackedEntities()
        { 
            // Cleanup all untracked entities 
            foreach (var entity in this.graph.Select(o => BindingEntityInfo.IsEntityType(o.GetType()) && !this.observer.IsContextTrackingEntity(o)))
            { 
                this.graph.ClearEdgesForVertex(this.graph.LookupVertex(entity));
            }

            this.RemoveUnreachableVertices(); 
        }
 
        ///  
        /// Returns a sequence of items belonging to a collection. Uses the children of a collection
        /// vertex for this enumeration. 
        /// 
        /// Collection being enumerated.
        /// Sequence of items belonging to the collection.
        public IEnumerable GetCollectionItems(object collection) 
        {
            Vertex collectionVertex = this.graph.LookupVertex(collection); 
            Debug.Assert(collectionVertex != null, "Must be tracking the vertex for the collection"); 
            foreach (Edge collectionEdge in collectionVertex.OutgoingEdges.ToList())
            { 
                yield return collectionEdge.Target.Item;
            }
        }
 
        /// Reset the graph after detaching notifications for everything
        public void Reset() 
        { 
            this.graph.Reset(this.DetachNotifications);
        } 

        /// Removes the un-reachable vertices from the graph and un-registers notification handlers
        public void RemoveUnreachableVertices()
        { 
            // This is where actual removal from graph happens, detach notifications for removed object
            this.graph.RemoveUnreachableVertices(this.DetachNotifications); 
        } 

        /// Get the binding information for a collection 
        /// Collection
        /// The source object that reference the target object through a navigation property.
        /// The navigation property in the source object that reference the target object.
        /// The entity set of the source object. 
        /// The entity set name of the target object.
        public void GetEntityCollectionInfo( 
            object collection, 
            out object source,
            out string sourceProperty, 
            out string sourceEntitySet,
            out string targetEntitySet)
        {
            Debug.Assert(collection != null, "Argument 'collection' cannot be null."); 
            Debug.Assert(this.graph.ExistsVertex(collection), "Vertex corresponding to 'collection' must exist in the graph.");
 
            this.graph 
                .LookupVertex(collection)
                .GetEntityCollectionInfo( 
                    out source,
                    out sourceProperty,
                    out sourceEntitySet,
                    out targetEntitySet); 
        }
 
        ///  
        /// Obtains the closest ancestor entity type in the graph corresponding to a complex object vertex.
        ///  
        /// On input this is a complex object, on output it is the closest entity ancestor.
        /// On input this is a complex object's member property name, on output it is the name of complex type property of the ancestor.
        /// On input this is a complex object's member property value, on output it is the value of complex type property of the ancestor.
        public void GetAncestorEntityForComplexProperty( 
            ref object entity,
            ref string propertyName, 
            ref object propertyValue) 
        {
            Vertex childVertex = this.graph.LookupVertex(entity); 
            Debug.Assert(childVertex != null, "Must have a vertex in the graph corresponding to the entity.");
            Debug.Assert(childVertex.IsComplex == true, "Vertex must correspond to a complex object.");

            while (childVertex.IsComplex) 
            {
                propertyName = childVertex.IncomingEdges[0].Label; 
                propertyValue = childVertex.Item; 

                Debug.Assert(childVertex.Parent != null, "Complex properties must always have parent vertices."); 
                entity = childVertex.Parent.Item;

                childVertex = childVertex.Parent;
            } 
        }
 
        ///  
        /// Adds a complex typed property to the graph for an object, also traverses all the child complex properties and adds them.
        ///  
        /// Source entity object.
        /// Source entity property of complex type.
        /// Target complex object property value.
        public void AddComplexProperty(object source, string sourceProperty, object target) 
        {
            Vertex parentVertex = this.graph.LookupVertex(source); 
            Debug.Assert(parentVertex != null, "Must have a valid parent entity for complex properties."); 
            Debug.Assert(target != null, "Must have non-null complex object reference.");
 
            Vertex complexVertex = this.graph.LookupVertex(target);

            if (complexVertex == null)
            { 
                complexVertex = this.graph.AddVertex(target);
                complexVertex.Parent = parentVertex; 
                complexVertex.IsComplex = true; 

                // Register for complex type notifications, fail if the complex type does not implement INotifyPropertyChanged. 
                if (!this.AttachEntityOrComplexObjectNotification(target))
                {
                    throw new InvalidOperationException(Strings.DataBinding_NotifyPropertyChangedNotImpl(target.GetType()));
                } 
            }
            else 
            { 
                throw new InvalidOperationException(Strings.DataBinding_ComplexObjectAssociatedWithMultipleEntities(target.GetType()));
            } 

            this.graph.AddEdge(source, target, sourceProperty);

            // Add nested properties for the complex object. 
            this.AddFromProperties(target);
        } 
 
        /// Add items to the graph, from the  object's properties
        /// Object whose properties are to be explored 
        private void AddFromProperties(object entity)
        {
            // Once the entity is attached to the graph, we need to traverse all it's properties
            // and add related entities and collections to this entity. 
            foreach (BindingEntityInfo.BindingPropertyInfo bpi in BindingEntityInfo.GetObservableProperties(entity.GetType()))
            { 
                object propertyValue = bpi.PropertyInfo.GetValue(entity); 

                if (propertyValue != null) 
                {
                    switch (bpi.PropertyKind)
                    {
                        case BindingPropertyKind.BindingPropertyKindCollection: 
                            this.AddCollection(
                                    entity, 
                                    bpi.PropertyInfo.PropertyName, 
                                    propertyValue,
                                    null); 

                            break;

                        case BindingPropertyKind.BindingPropertyKindEntity: 
                            this.AddEntity(
                                    entity, 
                                    bpi.PropertyInfo.PropertyName, 
                                    propertyValue,
                                    null, 
                                    entity);

                            break;
 
                        default:
                            Debug.Assert(bpi.PropertyKind == BindingPropertyKind.BindingPropertyKindComplex, "Must be complex type if PropertyKind is not entity or collection."); 
                            this.AddComplexProperty( 
                                    entity,
                                    bpi.PropertyInfo.PropertyName, 
                                    propertyValue);
                            break;
                    }
                } 
            }
        } 
 
        /// Attach the CollectionChanged handler to an DataServiceCollection.
        /// An DataServiceCollection. 
        private void AttachCollectionNotification(object target)
        {
            Debug.Assert(target != null, "Argument 'target' cannot be null");
 
            INotifyCollectionChanged notify = target as INotifyCollectionChanged;
            Debug.Assert(notify != null, "DataServiceCollection must implement INotifyCollectionChanged"); 
 
            notify.CollectionChanged -= this.observer.OnCollectionChanged;
            notify.CollectionChanged += this.observer.OnCollectionChanged; 
        }

        /// Attach the PropertyChanged handler to an entity or complex object.
        /// An entity or complex object. 
        /// True if the target is attached; otherwise false.
        private bool AttachEntityOrComplexObjectNotification(object target) 
        { 
            Debug.Assert(target != null, "Argument 'target' cannot be null");
 
            INotifyPropertyChanged notify = target as INotifyPropertyChanged;
            if (notify != null)
            {
                notify.PropertyChanged -= this.observer.OnPropertyChanged; 
                notify.PropertyChanged += this.observer.OnPropertyChanged;
                return true; 
            } 

            return false; 
        }

        /// Detach CollectionChanged or PropertyChanged handlers from the target
        /// An entity object or collection 
        private void DetachNotifications(object target)
        { 
            Debug.Assert(target != null, "Argument 'target' cannot be null"); 

            this.DetachCollectionNotifications(target); 

            INotifyPropertyChanged notifyPropertyChanged = target as INotifyPropertyChanged;
            if (notifyPropertyChanged != null)
            { 
                notifyPropertyChanged.PropertyChanged -= this.observer.OnPropertyChanged;
            } 
        } 

        /// Detach CollectionChanged handlers from the target 
        /// A collection object
        private void DetachCollectionNotifications(object target)
        {
            Debug.Assert(target != null, "Argument 'target' cannot be null"); 

            INotifyCollectionChanged notifyCollectionChanged = target as INotifyCollectionChanged; 
            if (notifyCollectionChanged != null) 
            {
                notifyCollectionChanged.CollectionChanged -= this.observer.OnCollectionChanged; 
            }
        }

        ///  
        /// Sets the observer for a child DataServiceCollection
        ///  
        /// Entity type for the collection 
        /// Non-typed collection interface
        private void SetObserver(ICollection collection) 
        {
            DataServiceCollection oec = collection as DataServiceCollection;
            oec.Observer = this.observer;
        } 

        /// Graph implementation for tracking entities, collections for binding 
        internal sealed class Graph 
        {
            /// Vertices of the graph, which also hold edges 
            private Dictionary vertices;

            /// The root vertex for the graph, DFS traversals start from this vertex
            private Vertex root; 

            /// Constructor 
            public Graph() 
            {
                this.vertices = new Dictionary(ReferenceEqualityComparer.Instance); 
            }

            /// Root vertex of the graph
            public Vertex Root 
            {
                get 
                { 
                    Debug.Assert(this.root != null, "Must have a non-null root vertex when this call is made.");
                    return this.root; 
                }

                set
                { 
                    Debug.Assert(this.root == null, "Must only initialize root vertex once.");
                    Debug.Assert(this.ExistsVertex(value.Item), "Must already have the assigned vertex in the graph."); 
                    this.root = value; 
                }
            } 

            /// Adds vertex to the graph
            /// Item corresponding to vertex
            /// Newly created vertex 
            public Vertex AddVertex(object item)
            { 
                Vertex v = new Vertex(item); 
                this.vertices.Add(item, v);
                return v; 
            }

            /// Removes all edges going out of and coming into the given vertex
            /// Vertex whose edges are to be cleared 
            public void ClearEdgesForVertex(Vertex v)
            { 
                foreach (Edge e in v.OutgoingEdges.Concat(v.IncomingEdges).ToList()) 
                {
                    this.RemoveEdge(e.Source.Item, e.Target.Item, e.Label); 
                }
            }

            ///  
            /// Checks if a vertex exists corresponding to given 
            ///  
            /// Item to lookup 
            /// true if vertex found, false otherwise
            public bool ExistsVertex(object item) 
            {
                Vertex v;
                return this.vertices.TryGetValue(item, out v);
            } 

            /// Looksup the vertex corresponding to  
            /// Item to lookup 
            /// Vertex corresponding to item
            public Vertex LookupVertex(object item) 
            {
                Vertex v;
                this.vertices.TryGetValue(item, out v);
                return v; 
            }
 
            ///  
            /// Adds edge between vertices corresponding to  and 
            /// objects which will be labeled with  
            /// 
            /// Outgoing end of the edge
            /// Incoming end of the edge
            /// Label for the vertex 
            /// Newly created edge
            public Edge AddEdge(object source, object target, string label) 
            { 
                Vertex s = this.vertices[source];
                Vertex t = this.vertices[target]; 
                Edge e = new Edge { Source = s, Target = t, Label = label };
                s.OutgoingEdges.Add(e);
                t.IncomingEdges.Add(e);
                return e; 
            }
 
            ///  
            /// Removes edge between vertices corresponding to  and 
            /// objects which was labeled with  
            /// 
            /// Outgoing end of the edge
            /// Incoming end of the edge
            /// Label for the vertex 
            public void RemoveEdge(object source, object target, string label)
            { 
                Vertex s = this.vertices[source]; 
                Vertex t = this.vertices[target];
                Edge e = new Edge { Source = s, Target = t, Label = label }; 
                s.OutgoingEdges.Remove(e);
                t.IncomingEdges.Remove(e);
            }
 
            /// 
            /// Checks if an edge exists between  and  labeled 
            /// with  
            /// 
            /// Outgoing end of the edge 
            /// Incoming end of the edge
            /// Label for the vertex
            /// true if an edge exists between source and target with given label, false otherwise
            public bool ExistsEdge(object source, object target, string label) 
            {
                Edge e = new Edge { Source = this.vertices[source], Target = this.vertices[target], Label = label }; 
                return this.vertices[source].OutgoingEdges.Any(r => r.Equals(e)); 
            }
 
            /// 
            /// Selects collection of objects tracked by the graph based on the given filter
            /// 
            /// Filter for the objects 
            /// Filtered list of objects tracked by the graph
            public IList Select(Func filter) 
            { 
                return this.vertices.Keys.Where(filter).ToList();
            } 

            /// 
            /// Removes everything from the graph after applying 
            ///  
            /// Action to apply before removal of each node
            public void Reset(Action action) 
            { 
                foreach (object obj in this.vertices.Keys)
                { 
                    action(obj);
                }

                this.vertices.Clear(); 
            }
 
            /// Remove all vertices from graph that are unreachable from the root collection vertex 
            /// Action to perform for each removed vertex
            public void RemoveUnreachableVertices(Action detachAction) 
            {
                try
                {
                    foreach (Vertex v in this.UnreachableVertices()) 
                    {
                        this.ClearEdgesForVertex(v); 
                        detachAction(v.Item); 
                        this.vertices.Remove(v.Item);
                    } 
                }
                finally
                {
                    // Reset color for all vertices back to white. 
                    foreach (Vertex v in this.vertices.Values)
                    { 
                        v.Color = VertexColor.White; 
                    }
                } 
            }

            /// Collects all vertices unreachable from the root collection vertex
            /// Sequence of vertices that are unreachable from the root collection vertex 
            /// 
            /// Performs a depth first traversal of the graph starting from the root collection 
            /// vertex and checks if some vertices were unreachable was reached while doing the traversal. 
            /// Alogrithm from Introduction to Algorithms 22.2 by Cormen et al.
            ///  
            private IEnumerable UnreachableVertices()
            {
                Queue q = new Queue();
 
                this.Root.Color = VertexColor.Gray;
                q.Enqueue(this.Root); 
 
                while (q.Count != 0)
                { 
                    Vertex current = q.Dequeue();

                    foreach (Edge e in current.OutgoingEdges)
                    { 
                        if (e.Target.Color == VertexColor.White)
                        { 
                            e.Target.Color = VertexColor.Gray; 
                            q.Enqueue(e.Target);
                        } 
                    }

                    current.Color = VertexColor.Black;
                } 

                return this.vertices.Values.Where(v => v.Color == VertexColor.White).ToList(); 
            } 
        }
 
        /// Vertex of the 
        internal sealed class Vertex
        {
            /// Collection of incoming edges for the vertex 
            private List incomingEdges;
 
            /// Collection of outgoing edges for the vertex 
            private List outgoingEdges;
 
            /// Constructor
            /// Item corresponding to vertex
            public Vertex(object item)
            { 
                Debug.Assert(item != null, "item must be non-null");
                this.Item = item; 
                this.Color = VertexColor.White; 
            }
 
            /// Item corresponding to the vertex
            public object Item
            {
                get; 
                private set;
            } 
 
            /// Entity set of the item held by the vertex
            public string EntitySet 
            {
                get;
                set;
            } 

            /// Is item a collection object 
            public bool IsCollection 
            {
                get; 
                set;
            }

            /// Is item a complex type object 
            public bool IsComplex
            { 
                get; 
                set;
            } 

            /// Parent vertex, only exists for non-top level collection vertices or complex objects
            public Vertex Parent
            { 
                get;
                set; 
            } 

            /// Property of the  object that associates this vertex with it's parent 
            public string ParentProperty
            {
                get;
                set; 
            }
 
            /// Is item a root collection object 
            public bool IsRootCollection
            { 
                get
                {
                    return this.IsCollection && this.Parent == null;
                } 
            }
 
            /// Color of the vertex 
            public VertexColor Color
            { 
                get;
                set;
            }
 
            /// Edges coming into this vertex
            public IList IncomingEdges 
            { 
                get
                { 
                    if (this.incomingEdges == null)
                    {
                        this.incomingEdges = new List();
                    } 

                    return this.incomingEdges; 
                } 
            }
 
            /// Edges going out of this vertex
            public IList OutgoingEdges
            {
                get 
                {
                    if (this.outgoingEdges == null) 
                    { 
                        this.outgoingEdges = new List();
                    } 

                    return this.outgoingEdges;
                }
            } 

            /// Get the binding information for a collection vertex 
            /// The source object that reference the target object through a navigation property corresponding to current collection vertex. 
            /// The navigation property in the source object that reference the target object.
            /// The entity set of the source object. 
            /// The entity set of the target object.
            public void GetEntityCollectionInfo(
                out object source,
                out string sourceProperty, 
                out string sourceEntitySet,
                out string targetEntitySet) 
            { 
                Debug.Assert(this.IsCollection, "Must be a collection to be in this method");
 
                if (!this.IsRootCollection)
                {
                    Debug.Assert(this.Parent != null, "Parent must be non-null for child collection");
 
                    source = this.Parent.Item;
                    Debug.Assert(source != null, "Source object must be present for child collection"); 
 
                    sourceProperty = this.ParentProperty;
                    Debug.Assert(sourceProperty != null, "Source entity property associated with a child collection must be non-null"); 

#if DEBUG
                    PropertyInfo propertyInfo = source.GetType().GetProperty(sourceProperty);
                    Debug.Assert(propertyInfo != null, "Unable to get information for the source entity property associated with a child collection"); 
#endif
                    sourceEntitySet = this.Parent.EntitySet; 
                } 
                else
                { 
                    Debug.Assert(this.Parent == null, "Parent must be null for top level collection");
                    source = null;
                    sourceProperty = null;
                    sourceEntitySet = null; 
                }
 
                targetEntitySet = this.EntitySet; 
            }
        } 

        /// 
        /// Edge between two vertices of graph, directed and labeled
        ///  
        internal sealed class Edge : IEquatable
        { 
            /// Source vertex 
            public Vertex Source
            { 
                get;
                set;
            }
 
            /// Target vertex
            public Vertex Target 
            { 
                get;
                set; 
            }

            /// Label of the edge
            public string Label 
            {
                get; 
                set; 
            }
 
            /// IEquatable override
            /// Comparand
            /// true if equal, false otherwise
            public bool Equals(Edge other) 
            {
                return other != null && 
                    Object.ReferenceEquals(this.Source, other.Source) && 
                    Object.ReferenceEquals(this.Target, other.Target) &&
                    this.Label == other.Label; 
            }
        }
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK