Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Graph serialization

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?

like image 724
Kieron Avatar asked Aug 07 '08 00:08

Kieron


People also ask

What serialized graphs?

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.

What is meant by serialization of data?

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.

What is the purpose of serialization?

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.

What is data serialization example?

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.


2 Answers

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) 
like image 62
Andrew Peters Avatar answered Sep 30 '22 08:09

Andrew Peters


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.

like image 20
Lily Ballard Avatar answered Sep 30 '22 07:09

Lily Ballard