GTS Library Reference Manual |
---|
#include <gts.h> #define GTS_GNODE_SPLIT_CLASS (klass) #define GTS_GNODE_SPLIT (obj) #define GTS_IS_GNODE_SPLIT (obj) #define GTS_GNODE_SPLIT_N1 (ns) #define GTS_GNODE_SPLIT_N2 (ns) struct GtsGNodeSplitClass; struct GtsGNodeSplit; GtsGNodeSplitClass* gts_gnode_split_class (void); GtsGNodeSplit* gts_gnode_split_new (GtsGNodeSplitClass *klass, GtsGNode *n, GtsObject *n1, GtsObject *n2); void gts_gnode_split_collapse (GtsGNodeSplit *ns, GtsGraph *g, GtsWGEdgeClass *klass); void gts_gnode_split_expand (GtsGNodeSplit *ns, GtsGraph *g); #define GTS_PGRAPH_CLASS (klass) #define GTS_PGRAPH (obj) #define GTS_IS_PGRAPH (obj) struct GtsPGraphClass; struct GtsPGraph; GtsPGraphClass* gts_pgraph_class (void); GtsPGraph* gts_pgraph_new (GtsPGraphClass *klass, GtsGraph *g, GtsGNodeSplitClass *split_class, GtsWGNodeClass *node_class, GtsWGEdgeClass *edge_class,guint min); GtsGNodeSplit* gts_pgraph_add_node (GtsPGraph *pg); GtsGNodeSplit* gts_pgraph_remove_node (GtsPGraph *pg);gboolean gts_pgraph_down (GtsPGraph *pg, GtsFunc func,gpointer data); void gts_pgraph_set_node_number (GtsPGraph *pg,guint n);guint gts_pgraph_get_node_number (GtsPGraph *pg);guint gts_pgraph_max_node_number (GtsPGraph *pg);guint gts_pgraph_min_node_number (GtsPGraph *pg); void gts_pgraph_foreach_node (GtsPGraph *pg, GtsFunc func,gpointer data);
#define GTS_GNODE_SPLIT_N1(ns) (GTS_IS_GNODE_SPLIT ((ns)->n1) ? GTS_GNODE_SPLIT ((ns)->n1)->n : GTS_GNODE ((ns)->n1))
ns : |
|
#define GTS_GNODE_SPLIT_N2(ns) (GTS_IS_GNODE_SPLIT ((ns)->n2) ? GTS_GNODE_SPLIT ((ns)->n2)->n : GTS_GNODE ((ns)->n2))
ns : |
|
struct GtsGNodeSplit { GtsObject object; GtsGNode * n; GtsObject * n1; GtsObject * n2; };
GtsGNodeSplitClass* gts_gnode_split_class (void);
Returns : | the GtsGNodeSplitClass. |
GtsGNodeSplit* gts_gnode_split_new (GtsGNodeSplitClass *klass, GtsGNode *n, GtsObject *n1, GtsObject *n2);
Creates a new GtsGNodeSplit which would collapse n1 and n2 into n. The collapse itself is not performed.
klass : | |
n : | a GtsGNode. |
n1 : | a GtsGNodeSplit or GtsGNode. |
n2 : | a GtsGNodeSplit or GtsGNode. |
Returns : | the new GtsGNodeSplit. |
void gts_gnode_split_collapse (GtsGNodeSplit *ns, GtsGraph *g, GtsWGEdgeClass *klass);
Collapses the node split ns. Any new edge created during the process will be of class klass.
ns : | |
g : | a GtsGraph. |
klass : |
void gts_gnode_split_expand (GtsGNodeSplit *ns, GtsGraph *g);
Expands the node split ns adding the new nodes to g.
ns : | |
g : | a GtsGraph. |
struct GtsPGraph { GtsObject object; GtsGraph * g; GPtrArray * split; GArray * levels; GtsGNodeSplitClass * split_class; GtsWGEdgeClass * edge_class; guint pos, min, level; };
GtsPGraph* gts_pgraph_new (GtsPGraphClass *klass, GtsGraph *g, GtsGNodeSplitClass *split_class, GtsWGNodeClass *node_class, GtsWGEdgeClass *edge_class,guint min);
Creates a new multilevel approximation of graph g. At each level a maximal matching is created using the Heavy Edge Matching (HEM) technique of Karypis and Kumar (1997). The newly created nodes are of type node_class and their weight is set to the sum of the weights of their children. The newly created edges are of type edge_class and their weight is set to the sum of the weight of the collapsed edges. The last level is reached when the maximal matching obtained would lead to a graph with less than min nodes.
klass : | |
g : | a GtsGraph. |
split_class : | |
node_class : | |
edge_class : | |
min : | the minimum number of nodes. |
Returns : | the new GtsPGraph containing the multilevel representation of g. |
GtsGNodeSplit* gts_pgraph_add_node (GtsPGraph *pg);
Adds one node to the multilevel graph pg by expanding the next available GtsGNodeSplit.
pg : | a GtsPGraph. |
Returns : | the expanded GtsGNodeSplit or |
GtsGNodeSplit* gts_pgraph_remove_node (GtsPGraph *pg);
Removes one node from the multilevel graph pg by collapsing the first available GtsGNodeSplit.
pg : | a GtsPGraph. |
Returns : | the collapsed GtsGNodeSplit or NULL if all the GtsGNodeSplit have already been collapsed. |
gboolean gts_pgraph_down (GtsPGraph *pg, GtsFunc func,gpointer data);
Performs the required number of expansions to go from the current level to the level immediately below.
If func is not NULL, it is called after each GtsGNodeSplit has been expanded.
pg : | a GtsPGraph. |
func : | a GtsFunc or NULL. |
data : | user data to pass to func. |
Returns : | FALSE if it is not possible to go down one level, TRUE otherwise. |
void gts_pgraph_set_node_number (GtsPGraph *pg,guint n);
Performs the required number of collapses or expansions to set the number of nodes of pg to n.
pg : | a GtsPGraph. |
n : | a number of nodes. |
guint gts_pgraph_get_node_number (GtsPGraph *pg);
pg : | a GtsPGraph. |
Returns : | the current number of nodes of pg. |
guint gts_pgraph_max_node_number (GtsPGraph *pg);
pg : | a GtsPGraph. |
Returns : | the maximum number of nodes of pg i.e. the number of nodes if all the GtsGNodeSplit were expanded. |
guint gts_pgraph_min_node_number (GtsPGraph *pg);
pg : | a GtsPGraph. |
Returns : | the minimum number of nodes of pg i.e. the number of nodes if all the GtsGNodeSplit were collapsed. |
<<< Weighted graph | Graph partitioning >>> |