GSoC 2008 HyperGraph Algorithm

(Redirected from HyperGraph Algorithm)

Basic Details

Abstract

The purpose of this plan is to design a software and some graph algorithms function to implement and thoroughly test graph algorithms .etc

Work Log

Theory Learning Period

Week of Jun 2 (2008, Jun 2 - Jun 8)
• try to understand the code
week of Jun 16 (2008, Jun 16 - Jun 22)
• reading OpenCog framework and structure
• building the concept of algorithm framework

Coding Period

week of Jun 23 (2008, Jun 23 - Jun 30)
• building algorithm framework
week of Jul 1 (2008, Jul 1- Jul 7)
• coding the "transformer" for HyperGrap to transfor it to common Graph
week of Jul 8 (2008, Jul 8- Jul 15)
• coding the algorithm for hypergraph
week of Jul 21 (2008, Jul 21- Jul 26)
• I have been working on the implementation

Of transformer, the hypergraph-to-commongraph wrapper which connects the AtomTable to the BGL. First take some time to understand the code of \opencog\src\atomspace ,especiallly the AtomTable.cc Atom.cc and HandleEntry.cc. Nowday I understanded the stucture of graphs and how to store it. tI am tring to do something like the example on the link for the BGL wrapper functions.

week of Jul 27 (2008, Jul 27- Aug1 )
• The main job we do is still the transfermor and the graph algorithm.

I plan to finish it this week.

week of Aug2 (2008, Aug2- Aug8 )

Sorry, I fogot something.Here is the new one. First part, I will introduce the input parameters ,general transaction way and the output of the graph structure.the second part will tell more details about the functions in the transformer ,the input, the output and the process. First part: there are 7 kind of input parameters: (1). Transform::getGraphset(Type type, bool subclass) const

(2). Transform::getGraphset(Type type, Type targetTyp,bool subclass, bool

```    targetSubclass) const
```

(3). Transform::getGrahpset(Handle handle, Type type, bool subclass) const

(4). Transform::getGrahpset(const std::vector<Handle>& handles,

```                                    Type* types,
bool* subclasses,
Arity arity,
Type type,
bool subclass) const
```

(5). Transform::getGrahpset(const char* name, Type type, bool subclass)const

(6). Transform::getGrahpset (const char* targetName, Type targetType,Type type, bool subclass) const (7). Transform::getGrahpset(const char** names, Type* types, bool* subclasses, Arity arity,Type type, bool subclass) const

general transaction way depends on the input parameters.and there three different transaction ways (1). it is the special case of looking for an specific atom（#ifdef USE_ATOM_HASH_SET） (2). #ifndef PUT_OUTGOING_SET_IN_LINKS (3). #ifdef USE_STD_VECTOR_FOR_OUTGOING The 2ed and 3th way contains the choice for Incoming and the Outgoing. Regarding the weight of the link, use Truthvalue as keyword. Attentionvalue will be sent to the information of common graph link.it's just a kind of information

Regarding the process of convert.In my opinion there are two ways.

How to choose the way ,I consider by two aspects. One is communication between the BGL and the AtomTable,the converted graph should be converted back to hypergraph easily and agile.In addition,there are no difference between converted graph and common graph ,thus we can use the source of BGL and other source.

Regarding the structure of the converted graph after converted.we mustn't lose any information and try our best to be the same as BGL.

ALSO desigh a algorithm a algorithm about minimum spanning tree.

Step 1,estimate the graph G whether has the node whose indgree is one. If there is no this kind of node,jump to step 3; else there exists the node which indgree is one,then output the node and the link to tree.

Step 2,delete the node and the link in the graph also the number of nodes N - 1 and the number of the links M -1 .then goto step 1.

Step 3, delete the link whose wight is the biggest. of.if (M>N-1)then goto step 1, if (M=N-1) then output the whole graph to t. else (M<N-1) then output error.

week of Aug9 (2008, Aug9- Aug15 )

Hypergraph model

l1 = {A1, l2, 14} weight w1 l2 = {A2, A3, A4} w2 l4 = {A7, l5,l6} w4 l5 = {A5, A6} w5 l6 = {A8, A9} w6 In my algorithm , the function Transform::createdummynode(handle ,*p ) get the adjacency list about A1 firstly.

A1 can reach every node of hypergraph,even Ai (2..9) can do it. Ai (2..9) can reach A1 from A1 by the character of undirected graph. Only A1 can reach but Ai (2..9) can’t reach A1 in my algorithm.I am still working on it My questions is following: The incoming set of l_1 is {l2 , l4} and outgoing set of l_1 is {A1 ,l2 , l4}, right? Can you tell me?

I have finished the connection between Ai and Aj(i,j is 1..9),when the hypergraph convert to graph,becomes to Completed graph Now my difficulty is: Dummy node B1 set on L2 Dummy node B2 set on L4 Dummy node B3 set on L5 Dummy node B4 set on L6

Experiment Period

I have finished the transformer which can convert hypergraph to graph.Also I finished a minimum-cost spanning trees algorithm .Also I design a algorithm to Convert minimum-cost spanning trees (MST) to minimum-cost spanning hypertrees (MSHT).So now I can convert hypergraph to graph,using the graph to create the minimum-cost spanning trees and finally convert back to minimum-cost spanning hypertrees (MSHT).However, there are still little bugs in my code,but I think the algorithm are good and I am still debugging.