Menu
I'm looking for a simple algorithm to 'serialize' a directed graph. In particular I've got a set of files with interdependencies on their execution order, and I want to find the correct order at compile time. I know it must be a fairly common thing to do - compilers do it all the time - but my google-fu has been weak today. What's the 'go-to' algorithm for this?
724
An object graph contains a set of objects that are automatically serialized given that the object that contains the reference is serialized too. Any object that is serialized and contains an object reference, the object reference will be serialized by the JVM.
Serialization is the process of converting a data object—a combination of code and data represented within a region of data storage—into a series of bytes that saves the state of the object in an easily transmittable form.
Serialization is the process of converting an object into a stream of bytes to store the object or transmit it to memory, a database, or a file. Its main purpose is to save the state of an object in order to be able to recreate it when needed. The reverse process is called deserialization.
Serialization encodes objects into another format. For example you have an array in PHP like this: $array = array("a" => 1, "b" => 2, "c" => array("a" => 1, "b" => 2)); And then you want to store it in file or send to other application.
Topological Sort (From Wikipedia):
In graph theory, a topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts.
Pseudo code:
L ← Empty list where we put the sorted elements Q ← Set of all nodes with no incoming edges while Q is non-empty do remove a node n from Q insert n into L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into Q if graph has edges then output error message (graph has a cycle) else output message (proposed topologically sorted order: L) I would expect tools that need this simply walk the tree in a depth-first manner and when they hit a leaf, just process it (e.g. compile) and remove it from the graph (or mark it as processed, and treat nodes with all leaves processed as leaves).
As long as it's a DAG, this simple stack-based walk should be trivial.
20
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
