Subscribe to The Madman Scribblings        RSS Feed
-----

GrapheNet (rewrite)

Icon 2 Comments
I've been tinkering with a redesign of GrapheNet implementation
In do doing so I rewrote the core of GrapheNet in Nemerle
(~370 Lines Of Code, spread over 4 class and 1 module.)
This redesign allows for a more fluent style of coding, when using it.

Since Nemerle is based on .Net, it can interoperate with the other .net languages (like vb.net,c#)




Core Types

GrapheNet is built around 4 core types.

Graph(Of N,E) A graph
Node(of N,E) A node.
Edge(Of N,E) An Edge between nodes.
Path(Of N,E) The Path between Nodes, following edges.
+Module of Extension Methods.

Type Parameters
N -- Type for the Node Values.
E -- Type for the Edge Values.



Initialisers

Graph(Of String,Integer)( Bi As Boolean)
Graph(Of String,Integer)( Bi As Boolean, Node As IEnumerable(Of Node(Of String,Integer))
Note: The library uses generic parameters, so the types of the Node Values and Edge Values, can be anything. I'll be use String and Integer.

Dim g As New Graph(Of String,Integer)(False) ' Edges are directional.


Note: Bi-Directional Edge has not be implemented yet.

Add A Node

g.Add("A")
g.Add("B").Add("C") ' fluent style.



Adding an Edge
g["A"].AddEdgeTo("B",2).AddEdgeTo("C",4) ' A->B A->C  (Not A->B B->C )


Note: The fluent style above is left-most node dominant.
So it defines two edge.
A -> B
A -> C

g["B"].AddEdgeTo("C",8)



Removing a Node

g["A"].Remove()


Removing an Edge
g{"A","B").Remove()






Edges To & From a node

Dim ef As IEnumerable(Of Edge(Of String,Integer)) = g2["A"].Edges_From
Dim et As IEnumerable(Of Edge(Of String,Integer)) ==g2["A"].Edges_To





GrapheNet.Exts

.FindPaths
Input: G As Graph(Of N,E)
Input: Start As Node(Of N,E)
Input: Finis As Node(Of N,E)
Output: IEnumerable(Of Route(Of N,E))

Finds all of the paths between 2 nodes.
Example
Dim Routes = g.FindPaths(g2("A"),(g2("C"))
Console.WriteLine("{0} Paths Found.",r.Count());
ForEach( p in Routes )
 Dim x =  p.Edges.Sum(Function(e) e.Value)
 Console.WriteLine("{0} {1}",x,p)
Next


The GrapheNet Library also allows you to write the path search like this.
Dim Routes = g("A").PathsTo(g("C"))




.ToAdjancy(Of N,E)(g As: Graph(Of N,E))
Input: Graph(Of N,E)
Outputs: 2D Boolean Array

.ToAdjancyValue(Of N,E)( g As Graph(Of N,E))
Input: Graph(Of N,E)
Output: 2D Array of Type E

Advanced Stuff.
Spoiler



The Cool Example
' Create a new graph with 4 nodes (with String Value), the Edge value is of type Integer. 
Dim g2 As New Graph(Of String,Integer)(False,{"A","B","C","D"})
g2["A","B"]=2
g2["A","C"]=4
g2["B","C"]=8


4 lines of code!



Missing Features & Future

Improved Exception Messages
Bi-Direction Edges
Current thought are;-When adding an Edge it automatically adds one in reciprocal direction. The doubles the edge count though.
Dis-Allow Reflexivity Edges that start and finish on the same node.
Add Overload for FindPaths that use N rather the Node(Of N,E)
XML Documentation.


Download
~ 9Kb Download. Attached File  (Nem)GrapheNet.zip (8.19K)
Number of downloads: 45
~29Kb Decompressed.

Download and try GrapheNet in your code project.
If you create a good extension method, let me know.
I'd also appreciate your comments and suggestions

2 Comments On This Entry

Page 1 of 1

AdamSpeight2008 Icon

03 May 2011 - 08:23 PM
Added BiDirectional Nodes
Added SelfReflextivity
Added a Few more overloads

Re-factored the code base to under 300 LoC.
0

AdamSpeight2008 Icon

04 May 2011 - 07:57 PM
0
Page 1 of 1