Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?

L

lcz

Guest
lcz Asks: Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?
I know the following problem is famous:

  • For a given degree sequence $L$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $L$.

This algorithm is sometimes helpful when we gather experimental evidence for conjectures (or as part of a proof).

There are many such articles, but the implementation of algorithms seems very few. I recently saw the following article, which provides the software gradpart.


But because the code was written around 1995, it is difficult for today's compilers to make it (due to the constant updating of the C++ standard).

I read the author's description and it looks like it can quickly generate all nonisomorphic graphs by a given degree sequence.

enter image description here

In this example you can see a degree-partition with 50 vertices. Here we have 2 vertices of degree 1, 10 vertices of degree 2, 8 vertices of degree 3,... . Because of the use of the homomorphism-principle, during the generation we may obtain situations, where the operating group is trivial. So we get the possibility to describe large sets of pairwise non-isomorphic solutions implicitly. In this way in the shown example, we computed 34824038400 graphs in about 25 seconds and are also able to store these graphs with a very small amount of space.
Click to expand...

I know nauty is great, but it seems not to offer this feature (except for generating regular graphs). Especially for cases with a slightly higher number of vertices (e.g. more than 15 vertices)

It is not clear if there is an alternative math software, or if there is a later version of gradpart for using it today. If there is an updated version of the software gradpart, we would love to see it play a role in the discovery of theorems.

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
Click to expand...
 
You must log in or register to reply here.

Unreplied Threads

Encoding of categorical variables to reduce the effect of erroneous labels

aby Asks: Encoding of categorical variables to reduce the effect of erroneous labels
I have a structured dataset containing (nominal) categorical variables encoded as labels, let's say a feature includes labels from 1 to 20. Some of the labels in that feature could just be errors, that should not be present in the dataset and are not known priorly.

I wonder if there is an encoding method for that feature, such that the effect of erroneous labels will be mitigated. One-hot encoding of the labels before a ML task will create a dimension for each label, that could lead noisy labels to have a more dominating effect on the dataset.

In case of feature hashing, it's not that easy to determine the number of output features for each variable, therefore I think it wouldn't be reasonable to proceed with it.

Would a compression method such as PCA after having one-hot matrix (sparse) work well in this case? The labels would be represented by continuous values, although this could lead to an information loss for the correct labels besides noisy labels. But eventually noisy labels will not take up a dimension in the dataset, which is better.

I also believe that applying Fourier compression on one-hot matrices considering them as black and white images would be overcomplicated and nonsense for a tabular feature that frequencies do not matter.

What approach should I follow?

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
Click to expand...

How can I do a train test split for an unbalanced panel data set in Python?

Andrew Asks: How can I do a train test split for an unbalanced panel data set in Python?
I have an unbalanced, panel pandas data frame.

I would like to split this data into a training set and a testing set. Python's train_test_split method will not work because it does a random split, and so, it will likely places observations from t + 1 into the training set, and observations from t into the test set.

Which, of course, makes no sense, because the future cannot predict the past.

TimeSeriesSplit will also not work because this function does not take into consideration the panel dimension of my data set.

Is there an easy way to do a train test split on unbalanced panel data sets? This split should (1) take into consideration the panel dimension of the data set, and (2) place earlier observations in the training set and later observations in the testing set.

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
Click to expand...

[Solved] Extracting the Data from Shape File for Data Comparison

  • Mathan GIS
  • Geography
  • Replies: 0
Mathan GIS Asks: Extracting the Data from Shape File for Data Comparison
I have 2 shape files called Existing.shp and Updated.shp with following columns ObjectID,DateTime,X,Y,Location,AOIName,CreatedBy,EditedBy

Existing.shp will be in the Web applications and Updated.shp will be udated once in 10 days from various persons. I have to compare the data with Existing.shp and Updated.shp to identify the duplicate data.

Means Comparing Existing.shp to Updated.shp and remove the duplicate data in Updated.shp, Because Existing.shp is clean and processed by the application.

Steps:

  1. Download the Existing.shp from the Application and Store it in my local folder [D:\DataCompare\Existing.shp].

2.Receive the Updated.shp from various persons and store it in[D:\DataCompare\Updated.shp].

3.Compare Existing.shp and Updated.shp and Remove Duplicate Data in Updated.shp

4.Insert the new Data to Existing.shp and Upload to Application.

Environment:


  1. Visual Studio 2017 Community/C#/Windows Desktop Forms


  2. Installed ESRI.ArcGISRunTime

Query:

1.How to read the data in C# from the Existing.shp and Updated.shp like CreatedBy,Date.

If Possible Code Snippets please.

  1. How to load in store it in C#/Dictionary with specific Coulmns. So I can Compare with Date/CreatedBy

Once the data are loaded in Dictionary, I can perform other conditions.

I tried :

// Open the shapefile ShapefileFeatureTable myShapefile = await ShapefileFeatureTable.OpenAsync(filepath);

// Create a feature layer to display the shapefile FeatureLayer newFeatureLayer = new FeatureLayer(myShapefile);

But I am unable to access the data Row wise. Am I doing right?

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your response here to help other visitors like you. Thank you, solveforum.
Click to expand...

[Solved] How to interpret GPSDestBearing and GPSImgDirection?

msm1089 Asks: How to interpret GPSDestBearing and GPSImgDirection?
I need to take some photos capturing the GPS coords and direction of camera. I'm using an iPhone 8+ and this is the relevant output I get from Acute Photo EXIF Viewer:

Code: 
EXIF GPS Tags
GPSDestBearing:74041/49085
GPSDestBearingRef:M
GPSImgDirection:74041/49085
GPSImgDirectionRef:M

I have searched for about an hour to find a way to convert the bearing/direction into degrees, and every source said the numbers should be between 0-359.99 (i.e. degrees from N, clockwise). So what does 74041/49085 mean and how can it be converted into degrees?

I understand the Ref tags have M for Magnetic North. I need the direction using North the same way that Google Maps does, which is True North. Assuming I can get the direction as degrees from Magnetic North, how would I convert them to degrees from True North?

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your response here to help other visitors like you. Thank you, solveforum.
Click to expand...

I don't understand ions. Do they have a taste?

  • олеся
  • Chemistry
  • Replies: 0
олеся Asks: I don't understand ions. Do they have a taste?

  1. Do ions define the taste of the compound they form? Blood tastes metallic because hemoglobin contains ions of iron, but like... I'm sure it doesn't always work like that


  2. Do they have physical properties like taste when they're on their own? Say I dissolve NaCl in water, then it's just Na+ and Cl- floating around, they're not really a compound anymore, are they? But we would feel the taste

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
Click to expand...

Why do we treat particles as standing waves in QP?

  • QuantumGenius
  • Physics
  • Replies: 0
QuantumGenius Asks: Why do we treat particles as standing waves in QP?
The Quantum Physics course I am taking starts with the Classical Wave Equation and a statement that we treat quantum particles as standing waves.

The explanation they give is that most of the time particles are bound by some kind of potential and that the solution for the Particle in a Box problem is a standing wave.

The way I understood it is that it comes naturally from the Classical Wave Equation, that it is the only solution with such boundary conditions. But then I looked at a guitar string in slow motion and it didn't behave like a standing wave! After some googling I found out that its behavior is called a pulse.

enter image description here

Now I am at a loss. Why do we only consider standing waves and discard other solutions? Are there some restrictions that should be applied that I am not aware of?

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
Click to expand...

QFT in frw spacetime

  • Obama2020
  • Physics
  • Replies: 0
Obama2020 Asks: QFT in frw spacetime
The metric for frw spacetime is $ds^2$ = $a(n)^2(dn^2 - dx^2)$ where $dn$ is the conformal time differential form. The Klein Gordon equation in curved spacetime is $(\frac{1}{g^{1/2}}\partial_{\mu}(g^{1/2}g^{\mu\nu}\partial_{\nu}) + m^2)\phi = 0$

From this one can obtain the Klein Gordon equation for frw spacetime

$\ddot{\phi} + 2\frac{\dot{a}}{a}\dot{\phi} - \Delta \phi + m^2a^2\phi = 0$ (mukhanov 64)

How do we derive this equation from the above equation?

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
Click to expand...

Latest posts

Newest Members

Top