See the bottom of https://github.com/sympy/sympy/wiki/GSoC-2013-Ideas. If you have some more examples, add them there (also if you know of good numerical libraries to direct people to).
Aaron Meurer On Mon, Mar 18, 2013 at 6:26 PM, Aaron Meurer <[email protected]> wrote: > This comes up often enough that we ought to add a note about it to the > ideas page. > > Aaron Meurer > > On Mon, Mar 18, 2013 at 1:59 PM, Brian Granger <[email protected]> wrote: >> 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. >> >> -- 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.
