Progressive graph

Name

Progressive graph -- 

Synopsis


#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);

Description

Details

GTS_GNODE_SPLIT_CLASS()

#define     GTS_GNODE_SPLIT_CLASS(klass)

klass :


GTS_GNODE_SPLIT()

#define     GTS_GNODE_SPLIT(obj)

obj :


GTS_IS_GNODE_SPLIT()

#define     GTS_IS_GNODE_SPLIT(obj)

obj :


GTS_GNODE_SPLIT_N1()

#define GTS_GNODE_SPLIT_N1(ns) (GTS_IS_GNODE_SPLIT ((ns)->n1) ? GTS_GNODE_SPLIT ((ns)->n1)->n : GTS_GNODE ((ns)->n1))

ns :


GTS_GNODE_SPLIT_N2()

#define GTS_GNODE_SPLIT_N2(ns) (GTS_IS_GNODE_SPLIT ((ns)->n2) ? GTS_GNODE_SPLIT ((ns)->n2)->n : GTS_GNODE ((ns)->n2))

ns :


struct GtsGNodeSplitClass

struct GtsGNodeSplitClass {

  GtsObjectClass parent_class;
};


struct GtsGNodeSplit

struct GtsGNodeSplit {

  GtsObject object;

  GtsGNode * n;
  GtsObject * n1;
  GtsObject * n2;
};


gts_gnode_split_class ()

GtsGNodeSplitClass* gts_gnode_split_class   (void);

Returns :

the GtsGNodeSplitClass.


gts_gnode_split_new ()

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 :

a GtsGNodeSplitClass.

n :

a GtsGNode.

n1 :

a GtsGNodeSplit or GtsGNode.

n2 :

a GtsGNodeSplit or GtsGNode.

Returns :

the new GtsGNodeSplit.


gts_gnode_split_collapse ()

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 :

a GtsGNodeSplit.

g :

a GtsGraph.

klass :

a GtsWGEdgeClass.


gts_gnode_split_expand ()

void        gts_gnode_split_expand          (GtsGNodeSplit *ns,
                                             GtsGraph *g);

Expands the node split ns adding the new nodes to g.

ns :

a GtsGNodeSplit.

g :

a GtsGraph.


GTS_PGRAPH_CLASS()

#define     GTS_PGRAPH_CLASS(klass)

klass :


GTS_PGRAPH()

#define     GTS_PGRAPH(obj)

obj :


GTS_IS_PGRAPH()

#define     GTS_IS_PGRAPH(obj)

obj :


struct GtsPGraphClass

struct GtsPGraphClass {

  GtsObjectClass parent_class;
};


struct GtsPGraph

struct GtsPGraph {

  GtsObject object;

  GtsGraph * g;
  GPtrArray * split;
  GArray * levels;
  GtsGNodeSplitClass * split_class;
  GtsWGEdgeClass * edge_class;
  guint pos, min, level;
};


gts_pgraph_class ()

GtsPGraphClass* gts_pgraph_class            (void);

Returns :

the GtsPGraphClass.


gts_pgraph_new ()

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 :

a GtsPGraphClass.

g :

a GtsGraph.

split_class :

a GtsGNodeSplitClass.

node_class :

a GtsWGNodeClass.

edge_class :

a GtsWGEdgeClass.

min :

the minimum number of nodes.

Returns :

the new GtsPGraph containing the multilevel representation of g.


gts_pgraph_add_node ()

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 NULL if all the GtsGNodeSplit have already been expanded.


gts_pgraph_remove_node ()

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.


gts_pgraph_down ()

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.


gts_pgraph_set_node_number ()

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.


gts_pgraph_get_node_number ()

guint       gts_pgraph_get_node_number      (GtsPGraph *pg);

pg :

a GtsPGraph.

Returns :

the current number of nodes of pg.


gts_pgraph_max_node_number ()

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.


gts_pgraph_min_node_number ()

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.


gts_pgraph_foreach_node ()

void        gts_pgraph_foreach_node         (GtsPGraph *pg,
                                             GtsFunc func,
                                             gpointer data);

pg :

func :

data :