A number of people have asked about graph theory in sympy in the past. Our feeling is that with the high quality of NetworkX, it doesn't make sense to reinvent graph theory in sympy. Maybe talk to the NetworkX folks about doing a GSoC with them?
On Mon, Mar 18, 2013 at 2:06 AM, Rajat Kapoor <[email protected]> wrote: > About me > > Hi, my name is Rajat Kapoor and I'm currently pursuing Engg. in Electrical > and Electronics along with M.S. in Mathematics in BITS Pilani Goa. > > I'm from India, and have sheer interest in computer programming as well as > Mathematics. Few of my favorite areas in Mathematics include Optimization > Techniques and Graph Theory > > Contact: [email protected] , rajat100493(skype), rajatkapoor(github) > > Programming Skills > > I've done coding in several high-level languages (C, C++,Java, C#, Python). > My most preferred among all these is C#, mostly because of the powerful IDE > options available but when it comes to cross platform development, I prefer > Python because of its simplicity. I have completed a few intermediate level > virtual courses in Python at college and have had guidance from a helpful > lot of seniors with regard to a few informal projects in python. Apart from > this I have amateur programming skills in web technologies including HTML, > CSS, XML, PHP. Other areas of interest include Image Processing(using > SimpleCV and OpenCV). I also have a very basic knowledge of GUI based > programming in Java as well as python(using PyQt and wxWidgets). I have a > negligible experience with git but I've learnt the concept well and have > started using it lately. > > Project Idea: > > Becasue of my avid interest in the above mentioned areas I propose the idea > of working on ONE of the following projects, which seems viable as well as > pretty apt to be merged into sympy > > Addition of a new Optimization module > > OR > > Addition of Graph Theory Module > > Though my peak interest is in developing the above mentioned modules, but > due to its strong dependencies on the matrices module, I'll have to add some > more functionality to the matrices module. > > Optimization Module: > > Features of the optimization module: > > Solving to linear programming problems from the given matrix or polynomial > input: Simplex algorithms along with a few variations(M-method, Two Phase, > Dual Simplex, and Generalised Simplex methods) will be used to solve such > problems > > Recognition of special cases(degeneracy, alternative optima, unboundedness, > infeasability) > > Transformation into dual problems: using primal dual relations > > Post optimal analysis: how feasibility and optimality are affected > > Transportation model solving: Starting solution to be obtained via northwest > corner method/ least cost method/vogel approximation method then proceeding > towards optimality using simplex iterations > > Assignment model solving: using Hungarian method. > > Any other ideas relating to the optimization field will also be added > > Graph Theory Module(which i personally prefer more): > > Input of graphs will be taken in form of adjacency list/adjacency matrix/ > incidence matrix. Interconversion between these three forms will be > provided.This module will initially aim to provide the following > functionality: > > Manipulation with degree of vertices, including detection of cut vertices, > formation of line graphs, finding closure, eccentricity,girth of a graph > > Simple graph operations like join, subtract, union, etc will be added > > Isomorphic graph detection will be implemented, by using some of the > functions in the already existing matrices module. Extra functions required > will be added to the matrices module itself. > > Functionality relating to the regularity as well as planarity(Tarjan's > algorithm) of graphs will also be added. > > Cycles: number of cycles and the cycles itself will be found out. Detection > of cycles in the graph will be done using Tarjan's algorithm or any other > algorithm that can be implemented with ease. > > Trees: all functions regarding no of nodes, root node, nodes at seperate > levels, etc. Trees will be recognized by cycle detection process. Minimum > spanning tree finding functionality will be added using Krusal's or Prim's > algorithm. > > Hamiltonian graphs: methods of detection will be implemented using Dirac's, > Ore's definition or Bondy-Chvátal theorem or by finding a cut vertex. > > Eulerian graphs : Checking the “even-ness” of degree of all vertices. Fleury > algorothm (implemented using Tarjan's algorithm to detect bridges) or > Hierholzer's algorithm to find the eulerian cycle. > > Special classes of graphs viz. Complete graphs, bipartite graphs, > multipartite graphs and hypercubes will also be pre-defined > > I have a very clear idea on how to implement the ideas stated above. These > functions will be first implemented for simple, undirected graphs and then > will be extended to multigraphs, directed graphs in due course of time. > Moreover, other suggested functionality will also be added. > > Main Question: Please give me advice on which module do you think will be > more useful for integrating with sympy, OPTIMIZATION or GRAPH THEORY. This > would help me focus the efforts on the preferred module before the GSOC > official dates so i can get a headstart.(I'll be working on graph theory > module anyways, if you agree to add its functionality in sympy). > > Although I prefer working on the above mentioned ideas,but I am open to > working on your suggested ideas too due to my familiarity with sympy. > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at http://groups.google.com/group/sympy?hl=en. > For more options, visit https://groups.google.com/groups/opt_out. > > -- Brian E. Granger Cal Poly State University, San Luis Obispo [email protected] and [email protected] -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
