|
Packit |
1e8aac |
/*
|
|
Packit |
1e8aac |
* glade-tsort.c: a topological sorting algorithm implementation
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* Copyright (C) 2013 Juan Pablo Ugarte.
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* This program is free software; you can redistribute it and/or modify
|
|
Packit |
1e8aac |
* it under the terms of the GNU General Public License as
|
|
Packit |
1e8aac |
* published by the Free Software Foundation; either version 2 of the
|
|
Packit |
1e8aac |
* License, or (at your option) any later version.
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* This program is distributed in the hope that it will be useful,
|
|
Packit |
1e8aac |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
1e8aac |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit |
1e8aac |
* GNU General Public License for more details.
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* You should have received a copy of the GNU General Public License
|
|
Packit |
1e8aac |
* along with this program; if not, write to the Free Software
|
|
Packit |
1e8aac |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* Authors:
|
|
Packit |
1e8aac |
* Juan Pablo Ugarte <juanpablougarte@gmail.com>
|
|
Packit |
1e8aac |
*/
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
#include "glade-tsort.h"
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/**
|
|
Packit |
1e8aac |
* _node_edge_prepend:
|
|
Packit |
1e8aac |
* @node: a _NodeEdge pointer or NULL
|
|
Packit |
1e8aac |
* @predecessor:
|
|
Packit |
1e8aac |
* @successor:
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* Adds a new node with the values @predecessor and @successor to the start of
|
|
Packit |
1e8aac |
* @node list.
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* Returns: the new start of the node list.
|
|
Packit |
1e8aac |
*/
|
|
Packit |
1e8aac |
GList *
|
|
Packit |
1e8aac |
_node_edge_prepend (GList *list,
|
|
Packit |
1e8aac |
gpointer predecessor,
|
|
Packit |
1e8aac |
gpointer successor)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
_NodeEdge *edge = g_slice_new (_NodeEdge);
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
edge->predecessor = predecessor;
|
|
Packit |
1e8aac |
edge->successor = successor;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
return g_list_prepend (list, edge);
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
static void
|
|
Packit |
1e8aac |
_node_edge_free (gpointer data)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
g_slice_free (_NodeEdge, data);
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
void
|
|
Packit |
1e8aac |
_node_edge_list_free (GList *list)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
g_list_free_full (list, _node_edge_free);
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
static inline void
|
|
Packit |
1e8aac |
tsort_remove_non_start_nodes (GList **nodes, GList *edges)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
GList *l;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
for (l = edges; l; l = g_list_next (l))
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
_NodeEdge *edge = l->data;
|
|
Packit |
1e8aac |
*nodes = g_list_remove (*nodes, edge->successor);
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
static inline gboolean
|
|
Packit |
1e8aac |
tsort_node_has_no_incoming_edge (gpointer node, GList *edges)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
GList *l;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
for (l = edges; l; l = g_list_next (l))
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
_NodeEdge *edge = l->data;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
if (node == edge->successor)
|
|
Packit |
1e8aac |
return FALSE;
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
return TRUE;
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/**
|
|
Packit |
1e8aac |
* _glade_tsort:
|
|
Packit |
1e8aac |
* @nodes: list of pointers to sort
|
|
Packit |
1e8aac |
* @edges: pointer to the list of #_NodeEdge that conform the dependency
|
|
Packit |
1e8aac |
* graph of @nodes.
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* Topological sorting implementation.
|
|
Packit |
1e8aac |
* After calling this funtion only graph cycles (circular dependencies) are left
|
|
Packit |
1e8aac |
* in @edges list. So if @edges is NULL it means the returned list has all the
|
|
Packit |
1e8aac |
* elements topologically sorted if not it means there are at least one
|
|
Packit |
1e8aac |
* circular dependency.
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* L ← Empty list that will contain the sorted elements
|
|
Packit |
1e8aac |
* S ← Set of all nodes with no incoming edges
|
|
Packit |
1e8aac |
* while S is non-empty do
|
|
Packit |
1e8aac |
* remove a node n from S
|
|
Packit |
1e8aac |
* insert n into L
|
|
Packit |
1e8aac |
* for each node m with an edge e from n to m do
|
|
Packit |
1e8aac |
* remove edge e from the graph
|
|
Packit |
1e8aac |
* if m has no other incoming edges then
|
|
Packit |
1e8aac |
* insert m into S
|
|
Packit |
1e8aac |
* return L (a topologically sorted order if graph has no edges)
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* see: http://en.wikipedia.org/wiki/Topological_sorting
|
|
Packit |
1e8aac |
*
|
|
Packit |
1e8aac |
* Returns: a new list sorted by dependency including nodes only present in @edges
|
|
Packit |
1e8aac |
*/
|
|
Packit |
1e8aac |
GList *
|
|
Packit |
1e8aac |
_glade_tsort (GList **nodes, GList **edges)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
GList *sorted_nodes;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* L ← Empty list that will contain the sorted elements */
|
|
Packit |
1e8aac |
sorted_nodes = NULL;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* S ← Set of all nodes with no incoming edges */
|
|
Packit |
1e8aac |
tsort_remove_non_start_nodes (nodes, *edges);
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* while S is non-empty do */
|
|
Packit |
1e8aac |
while (*nodes)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
GList *l, *next;
|
|
Packit |
1e8aac |
gpointer n;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* remove a node n from S */
|
|
Packit |
1e8aac |
n = (*nodes)->data;
|
|
Packit |
1e8aac |
*nodes = g_list_delete_link (*nodes, *nodes);
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* insert n into L */
|
|
Packit |
1e8aac |
/*if (!glade_widget_get_parent (n)) this would be a specific optimization */
|
|
Packit |
1e8aac |
sorted_nodes = g_list_prepend (sorted_nodes, n);
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* for each node m ... */
|
|
Packit |
1e8aac |
for (l = *edges; l; l = next)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
_NodeEdge *edge = l->data;
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
next = g_list_next (l);
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* ... with an edge e from n to m do */
|
|
Packit |
1e8aac |
if (edge->predecessor == n)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
/* remove edge e from the graph */
|
|
Packit |
1e8aac |
*edges = g_list_delete_link (*edges, l);
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* if m has no other incoming edges then */
|
|
Packit |
1e8aac |
if (tsort_node_has_no_incoming_edge (edge->successor, *edges))
|
|
Packit |
1e8aac |
/* insert m into S */
|
|
Packit |
1e8aac |
*nodes = g_list_prepend (*nodes, edge->successor);
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
g_slice_free (_NodeEdge, edge);
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* if graph has edges then return error (graph has at least one cycle) */
|
|
Packit |
1e8aac |
#if 0 /* We rather not return NULL, caller must check if edge */
|
|
Packit |
1e8aac |
if (*edges)
|
|
Packit |
1e8aac |
{
|
|
Packit |
1e8aac |
g_list_free (sorted_nodes);
|
|
Packit |
1e8aac |
_node_edge_list_free (*edges);
|
|
Packit |
1e8aac |
*edges = NULL;
|
|
Packit |
1e8aac |
return NULL;
|
|
Packit |
1e8aac |
}
|
|
Packit |
1e8aac |
#endif
|
|
Packit |
1e8aac |
|
|
Packit |
1e8aac |
/* return L (a topologically sorted order if edge is NULL) */
|
|
Packit |
1e8aac |
return g_list_reverse (sorted_nodes);
|
|
Packit |
1e8aac |
}
|