Printable View
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.
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
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.
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.
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.
Actually, the delete keyword of C++ has really nothing to do with removing objects from a graph-like data structure.Quote:
Originally Posted by tr00don
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.
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.Quote:
Originally Posted by tr00don
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?
I know, my mistake, I meant "dispose of" (free memory).Quote:
Originally Posted by TheGreatCthulhu
That's possible ;)Quote:
Just out of curiosity, does your nick "tr00don" have anything to do with a dinosaur named Troodon
:rolleyes: Mysterious, huh?Quote:
Originally Posted by tr00don
Anyway, what's important is to understand that C# is fully capable of representing graphs. Hope that it's all clear now.
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.
Sure. No problem.Quote:
Originally Posted by tr00don
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.Quote:
Originally Posted by tr00don
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.
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
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?Quote:
Originally Posted by tr00don
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...
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!