Graph data structures?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: Graph data structures?

  1. #1
    Join Date
    Apr 2009
    Location
    Ottawa, ON, Canada
    Posts
    34

    Graph data structures?

    Graphs are the most complex data structures and are typically implemented using pointers. One on the advantages of graphs is that one can programatically add and delete nodes. Apparently, this is not possible in C# as deleting pointers is not allowed. What kind of solution have you found for working with graphs in C#? Thanks.

  2. #2
    Join Date
    Jun 2008
    Posts
    2,477

    Re: Graph data structures?

    I don't understand your point. What do you mean you "can't delete pointers"? You can certainly add and remove items from a collection as you would remove a pointer. Maybe this article will get on the right path:

    http://blogs.msdn.com/b/ericlippert/...-part-one.aspx

  3. #3

    Re: Graph data structures?

    who told you there are no pointers in C#. That is a fable they tell the noobs, in my opinion to their own determint. Understanding that most everything in C# is in reality a pointer helps greatly in understanding how to correctly use the language. It also makes it rather obvious the differance between object1==object2 and object1.Equals(object2)

    There are only two types of objects in c# stack objects and heap objects. stack objects are objects such as structs, int, double etc... Heap objects are everything else, and are called heap objects because THEY ARE ALLOCATED ON THE HEAP.

    Anyway to your question implementing the IDisposable interface and calling Dispose has the essentially the same effect as calling delete in cpp.
    --------------------------------------------------------------------------------------------------------------------------
    Disclaimer - Most likely any code I have posted as an answer was most likely written free hand and may have some minor compile errors, and is merely intended to give you the idea.

  4. #4
    Join Date
    Apr 2009
    Location
    Ottawa, ON, Canada
    Posts
    34

    Re: Graph data structures?

    I appreciate the answers and the link.

    As there is no clear method for deleting objects (pointer variables) in C# I wonder how that can be achieved in an efficient manner when working with graphs. My understanding is that Dispose only marks the object for deletion; the garbage collector will delete it at the next pass.

    Consider a graph similar to that shown in the first figure at http://en.wikipedia.org/wiki/Graph_%28mathematics%29 where 1..6 are nodes and (1->2), (1->5), (2->5), (2->3), (3->4), (4->5), (4->6) are directed edges. In my data structure each graph node is an object with two fields, an int (the numerical value mentioned) and a linked list of objects (of the same class). I create this data structure programatically and I use it in an algorithm. So far so good.

    I need to delete nodes 4 and 6 and edges (3->4), (4->5), (4->6) which depend on these nodes; then I need to create a new edge (3, 5). Deleting an edge is equivalent to assigning its value to null. To create a new edge between existing nodes I assign the value of the object it points to to another object (node). My concern is that I should programatically free the memory allocated to the two objects represented by nodes 4 and 6 because they are not assigned to some explicit variable that the GC can take care of.

    Am I wrong? Will they be deleted automatically once no other node points to them?

    On the same note, if I create a new node, 7, and I link node 1 to node 7 only, will the rest of the data structure (nodes 2..6 and associated edges) be deleted by the GC at some point or should I mark them for deletion somehow for that to happen?

    Thanks.
    Last edited by tr00don; July 24th, 2010 at 12:11 PM.

  5. #5
    Join Date
    Jun 2008
    Posts
    2,477

    Re: Graph data structures?

    You just remove them from the collection as you would in any other language. C# does not require you to manually manage the lifetime of your heap objects. I don't know why you think that "deleting pointers" is the only way to maintain a graph structure.

  6. #6
    Join Date
    Jan 2010
    Posts
    1,099

    Re: Graph data structures?

    Quote Originally Posted by tr00don View Post
    One on the advantages of graphs is that one can programatically add and delete nodes. Apparently, this is not possible in C# as deleting pointers is not allowed.
    Actually, the delete keyword of C++ has really nothing to do with removing objects from a graph-like data structure.

    You can remove nodes and/or branches of a graph, without ever deleting anything (no matter what the language is used). What if you wanted to use a node you removed in some way? Like, putting it in another graph, or changing it's place within the same graph, or adding it to some temporary structure?

    Removing graph elements is one thing - freeing the memory with delete is another.

    Quote Originally Posted by tr00don View Post
    My understanding is that Dispose only marks the object for deletion; the garbage collector will delete it at the next pass.
    No. For managed objects, you don't need to give any hint at all to the GC. The Garbage Collector is smart enough to know when an object is not used anymore, and if this is the case, it does what it does. And it's pretty efficient at that, too.

    Dispose(), on the other hand is used for unmanaged resources only.
    See:
    IDisposable.Dispose Method
    Implementing a Dispose Method
    Implementing Finalize and Dispose to Clean Up Unmanaged Resources


    EDIT:
    ----------------------------------
    Just out of curiosity, does your nick "tr00don" have anything to do with a dinosaur named Troodon?
    Last edited by TheGreatCthulhu; July 24th, 2010 at 04:42 PM.

  7. #7
    Join Date
    Apr 2009
    Location
    Ottawa, ON, Canada
    Posts
    34

    Re: Graph data structures?

    Quote Originally Posted by TheGreatCthulhu View Post
    Removing graph elements is one thing - freeing the memory with [/I]delete[I] is another.
    I know, my mistake, I meant "dispose of" (free memory).

    Just out of curiosity, does your nick "tr00don" have anything to do with a dinosaur named Troodon
    That's possible

  8. #8
    Join Date
    Jan 2010
    Posts
    1,099

    Re: Graph data structures?

    Quote Originally Posted by tr00don View Post
    That's possible
    Mysterious, huh?

    Anyway, what's important is to understand that C# is fully capable of representing graphs. Hope that it's all clear now.

  9. #9
    Join Date
    Apr 2009
    Location
    Ottawa, ON, Canada
    Posts
    34

    Re: Graph data structures?

    No offense, but I need to understand how things work. If I create a graph in C# and only the entry node is stored in a variable named P then the GC may free at any time the memory used by the entire graph unless I use P again in my code? For example, if the last line of code is P = null then the GC will not free the structure until it reaches that statement? What happens if, instead of assigning null to P, I try to recreate P -- will the memory previously allocated to the graph be released at that moment?

    To answer your question: Yes, I guess I am a "dinosaur" (I prefer to "dispose" of pointers rather than "delete" them) and I was a http://trescom.org fan.
    Last edited by tr00don; July 24th, 2010 at 06:09 PM.

  10. #10
    Join Date
    Jan 2010
    Posts
    1,099

    Re: Graph data structures?

    Quote Originally Posted by tr00don View Post
    No offense, but I need to understand how things work.
    Sure. No problem.

    Quote Originally Posted by tr00don View Post
    If I create a graph in C# and only the entry node is stored in a variable named P then the GC may free at any time the memory used by the entire graph unless I use P again in my code? For example, if the last line of code is P = null then the GC will not free the structure until it reaches that statement?
    The GC will not collect any object as long as there's some sort of a reference to that object in the code, even if indirect. You do not need to worry about the GC at all. It cannot affect your application logic in any way.
    You don't need to actually use the object, you need to keep it somewhere where it can be accessed, directly or indirectly. As long as there's a way for your code to get a reference to this object, it is safe [the object] from the effect of the GC.

    If you coded in C++, and if you written "P = null" without freeing the memory, you'd have a memory leak. In C#, freeing managed memory is not your responsibility, the GC does that. Most of the other stuff is pretty much the same.

    Note that you have only limited control over the GC anyway.

    Quote Originally Posted by tr00don View Post
    What happens if, instead of assigning null to P, I try to recreate P -- will the memory previously allocated to the graph be released at that moment?
    If the new P, or anything else for that matter, doesn't reference this memory in any way, then yes (but maybe not at the very same moment - the GC sort of has its own agenda ). As I said, you don't need to worry about that.

    Quote Originally Posted by tr00don View Post
    To answer your question: Yes, I guess I am a "dinosaur" (I prefer to "dispose" of pointers rather than "delete" them) and I was a http://trescom.org fan.
    I didn't try to insinuate anything, and I didn't call you a metaphorical dinosaur or anything like that. It's just that I think dinosaurs are cool. I mean, who doesn't, right?
    P.S. BTW, since you seem to have misinterpreted my just-out-of-curiosity question, maybe you're not aware that there is a dinosaur with such a name. That's why I asked (Troodon - Wikipedia, the free encyclopedia).
    Anyway, enough about dinosaurs, since this is not the right place for the off-topic chit-chat. But, I started it, I know...
    Last edited by TheGreatCthulhu; July 24th, 2010 at 06:31 PM.

  11. #11
    Join Date
    Apr 2009
    Location
    Ottawa, ON, Canada
    Posts
    34

    Re: Graph data structures?

    I didn't mean to live up to my nickname (Troodon = wounding tooth) or to seem offended, as that was not the case. To prove it, I knew Troodon was a dino and if you visit the http://trescom.org website that I pointed to above you will notice that every forum user nickname is a dinosaur name and mine has been Troodon since 1998. I was only making fun of myself as I still do some software development in Delphi, which would probably make most C# developers think that I am some sort of "dinosaur"

    Cheers!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center