GSoC 2008 HyperGraph Algorithm

From OpenCog
Jump to: navigation, search

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

Contributors

Mentors

About graph algorithms

Work Log

Theory Learning Period

Week of May 19 (2008, May 19 - May 25)
  • Read up on OpenCog
Week of May 26 (2008, May 26 - Jun 1)
  • reading BGL
  • reading documents
Week of Jun 2 (2008, Jun 2 - Jun 8)
  • download open-sourced code
    • try to understand the code
week of Jun 9 (2008, Jun 9 - Jun 15)
  • reading conceptual AtomTable
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.

Though truthvalue has three kind of value,I consider it the same kind when I deal with it.However,We can distinguish the differences between them in the information of common graph. When I transfer attentionvalue, it consider as information sending to the common link.The data structure is adjacency list. There are few changes about the node,we only add a label and a value.which show whether it is a dummy node. Ben’s idea is that Let's say that link A points to link B in the Atom graph Let's say that link B has type T Let's say, next, that we insert a "dummy node" N_B in the middle of link B,thus splitting link B into two dummy links B1 and B2 Then I would say: -- B1 and B2 don't need truth values -- N_B should be assigned the truth value of B. Another consideration is delete the link A and add two new links A1 &A2 point to the nodes B,because there lots of node operations for common graph.

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.

(1)First way, Let's say that link A points to link B in the Atom graph Let's say, next, that we insert a "dummy node" B0 in the middle of link ,thus splitting link B into two dummy links B1 and B2 B, We put weight value in node B1 to make sure the weight of B1 and B2 are 0.at the same time, B1 and B2 are considered as normal link whose weight are 0.Then regarding to express the weight of the new link B,the we must have a judgement, when the new link pass the node B0 ,the new link B have a value.Thus,if we do some operations about links , we have to do a judgement for every node.In my opinion, I don't think it's a good idea to convert by this way,though the result of the graph have advantage that the node is less. (2) Second way ,there is another way. Let's say that link A points to link B .I create two new links from the node of link A to the two nodes of link B.The two links are link A1 and link A2.Then I delete the link A.Of course,the disadvantage of this way is that the number of links will be more. In my opinion, when the hypergraph is converted to common graph and input to the BGL, there is no difference between the converted graphics and the common graph. So I can use the source of BGL freely. Regarding the communication between the BGL and the AtomTable,if the information only transfer from Atomtable to BGL, I think the second way of converting is better.However if the information also transfer from BGL to Atomtable , Then I think the first way is better.

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.