Created
November 17, 2011 19:01
-
-
Save kylelemons/1374097 to your computer and use it in GitHub Desktop.
A fun little graph demo
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "fmt" | |
| "sync" | |
| ) | |
| type WaitList []*sync.WaitGroup | |
| func (l WaitList) Done() { | |
| for _, wg := range l { | |
| wg.Done() | |
| } | |
| } | |
| type Message string | |
| type Vertex chan Message | |
| func (v Vertex) Start(name string, adjacent []Vertex, wl WaitList) { | |
| defer wl.Done() | |
| for msg := range v { | |
| fmt.Println(name, "<-", msg) | |
| for _, n := range adjacent { | |
| n <- Message(name) + " <- " + msg | |
| } | |
| } | |
| } | |
| func main() { | |
| var done sync.WaitGroup | |
| // Define the graph | |
| vertices := []string{"a", "b", "c", "d"} | |
| edges := []struct{v1, v2 string}{ | |
| {"a", "b"}, | |
| {"a", "c"}, | |
| {"b", "d"}, | |
| {"c", "d"}, | |
| } | |
| // Create the graph | |
| vmap := make(map[string]Vertex) | |
| emap := make(map[string][]Vertex) | |
| wmap := make(map[string]*sync.WaitGroup) | |
| lmap := make(map[string]WaitList) | |
| for _, vname := range vertices { | |
| vmap[vname] = make(Vertex) | |
| wmap[vname] = new(sync.WaitGroup) | |
| } | |
| for _, edge := range edges { | |
| emap[edge.v1] = append(emap[edge.v1], vmap[edge.v2]) | |
| lmap[edge.v1] = append(lmap[edge.v1], wmap[edge.v2]) | |
| wmap[edge.v2].Add(1) | |
| // uncomment for bidirectional edges | |
| //emap[edge.v2] = append(emap[edge.v2], vmap[edge.v1]) | |
| //lmap[edge.v1] = append(emap[edge.v1], wmap[edge.v2]) | |
| } | |
| // Make sure the "head" vertex doesn't immediately exit | |
| wmap[vertices[0]].Add(1) | |
| // Start the graph | |
| for _, vname := range vertices { | |
| go vmap[vname].Start(vname, emap[vname], lmap[vname]) | |
| done.Add(1) | |
| go func(vname string) { | |
| wmap[vname].Wait() | |
| close(vmap[vname]) | |
| done.Done() | |
| }(vname) | |
| } | |
| // Send a message | |
| vmap[vertices[0]] <- "Hello!" | |
| wmap[vertices[0]].Done() | |
| // Close and wait for completion | |
| done.Wait() | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment